Distinct Integers in Range

Revision en2, by alwaysGREEEN, 2019-04-29 16:20:29

Hey Guys ! I am solving this problem

(https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/distinct-integers-in-range-66eca44b/description/)

on Hackerearth which ultimately boils down to finding distinct integers in a range from L to R. I am having a hard time understanding how the bitset class is used with segment trees to find the solution. I am posting one of the accepted solutions. Can anyone please explain the logic.

#include<bits/stdc++.h>
using namespace std;
bitset<5001> seg_a[400001],seg_b[400001],rst;
int a[100005],b[100005];
void built_a(int node,int start,int end){
	if(start==end){
		seg_a[node].set(a[start]);
		return;
	}
	int mid=(start+end)/2;
	built_a(2*node,start,mid);
	built_a(2*node+1,mid+1,end);
	seg_a[node]=(seg_a[2*node]|seg_a[2*node+1]);
}
void built_b(int node,int start,int end){
	if(start==end){
		seg_b[node].set(b[start]);
		return;
	}
	int mid=(start+end)/2;
	built_b(2*node,start,mid);
	built_b(2*node+1,mid+1,end);
	seg_b[node]=(seg_b[2*node]|seg_b[2*node+1]);
}
bitset<5001> query_a(int node,int start,int end,int L,int R){
	if(R<start||end<L)return rst;
	if(start>=L && end<=R)return seg_a[node];
	int mid=(start+end)/2;
	return query_a(2*node,start,mid,L,R)|query_a(2*node+1,mid+1,end,L,R);
}
bitset<5001> query_b(int node,int start,int end,int L,int R){
	if(R<start||end<L)return rst;
	if(start>=L && end<=R)return seg_b[node];
	int mid=(start+end)/2;
	return (query_b(2*node,start,mid,L,R)|query_b(2*node+1,mid+1,end,L,R));
}
int main(){
	int n;cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>b[i];
	
	built_a(1,0,n-1);
	built_b(1,0,n-1);
	
	cout<<seg_a[1].
	int q;cin>>q;
	int L1,R1,L2,R2;
	while(q--){
		cin>>L1>>R1>>L2>>R2;
		int ans=(query_a(1,0,n-1,L1-1,R1-1)|query_b(1,0,n-1,L2-1,R2-1)).count();
		cout<<ans<<"\n";
	}
	return 0;
}
Tags #hackerearth, #segment tree, #bitset

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English alwaysGREEEN 2019-04-29 16:20:29 18
en1 English alwaysGREEEN 2019-04-29 16:12:08 1963 Initial revision (published)