HackerEarth Distinct Integers in Range solution

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;
}