In this HackerEarth Distinct Integer in Range problem solution You are given two arrays A and B each of length N. Now you is given Q queries. In each query, you are given two pairs of ranges i.e. a range [a,b] in array A and range [c,d] in the array B. For each query, you need to count distinct elements in the array which is formed by combining elements of both the ranges in the query.

## HackerEarth Distinct Integers in Range problem solution.

```#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "\n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int a[100001];
int b[100001];
bitset<5001>tree1[400001] , tree2[400001];
void build(int node,int i,int j){
if(i > j)
return;
if(i == j){
tree1[node].set(a[i]);
tree2[node].set(b[i]);
return;
}
int mid = (i + j) / 2;
build(2 * node , i , mid);
build(2 * node + 1 , mid + 1 , j);
tree1[node] = tree1[2 * node] | tree1[2 * node + 1];
tree2[node] = tree2[2 * node] | tree2[2 * node + 1];
}

bitset<5001>query1(int node,int i,int j,int l,int r){
if(i > j || i > r || j < l)
return 0;
if(i >= l && j <= r)
return tree1[node];
int mid = (i + j) / 2;
return query1(2 * node , i , mid , l , r) | query1(2 * node + 1 , mid + 1 , j , l , r);
}

bitset<5001>query2(int node,int i,int j,int l,int r){
if(i > j || i > r || j < l)
return 0;
if(i >= l && j <= r)
return tree2[node];
int mid = (i + j) / 2;
return query2(2 * node , i , mid , l , r) | query2(2 * node + 1 , mid + 1 , j , l , r);
}

int main()
{
ios_base::sync_with_stdio(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
cin >> b[i];
}
build(1 , 1 , n);
int q;
cin >> q;
while(q--){
int a , b , c , d;
cin >> a >> b >> c >> d;
cout << (query1(1 , 1 , n , a , b) | query2(1 , 1 , n , c , d)).count() << endl;
}
}```

### Second solution

```#include <bits/stdc++.h>

using namespace std;

const int N = 1E5 + 5;
const int M = 5E3 + 5;
int a[N];
int b[N];
bitset<M> rst;
bitset<M> segt_a[4 * N];
bitset<M> segt_b[4 * N];

void build_a(int node, int start, int end) {
if(start == end) {
segt_a[node].set(a[start]);
return;
}
int mid = (start + end) >> 1;
build_a(node << 1, start, mid);
build_a((node << 1) + 1, mid + 1, end);
segt_a[node] = segt_a[node << 1] | segt_a[(node << 1) + 1];
return;
}

void build_b(int node, int start, int end) {
if(start == end) {
segt_b[node].set(b[start]);
return;
}
int mid = (start + end) >> 1;
build_b(node << 1, start, mid);
build_b((node << 1) + 1, mid + 1, end);
segt_b[node] = segt_b[node << 1] | segt_b[(node << 1) + 1];
return;
}

bitset<M> query_a(int node, int start, int end, int L, int R) {
if(start > R || end < L)
return rst;
if(start >= L && end <= R)
return segt_a[node];
int mid = (start + end) >> 1;
return query_a(node << 1, start, mid, L, R) | query_a((node << 1) + 1, mid + 1, end, L, R);
}

bitset<M> query_b(int node, int start, int end, int L, int R) {
if(start > R || end < L)
return rst;
if(start >= L && end <= R)
return segt_b[node];
int mid = (start + end) >> 1;
return query_b(node << 1, start, mid, L, R) | query_b((node << 1) + 1, mid + 1, end, L, R);
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> a[i];
for(int i = 1; i <= n; i ++)
cin >> b[i];
build_a(1, 1, n);
build_b(1, 1, n);
int q;
cin >> q;
int L1, R1, L2, R2;
while(q --) {
cin >> L1 >> R1 >> L2 >> R2;
int ans = (query_a(1, 1, n, L1, R1) | query_b(1, 1, n, L2, R2)).count();
cout << ans << '\n';
}
return 0;
}```