DQUERY - D-query

DQUERY

MO’s Algorithm 

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define lowBit(S) (S & (-S))
#define setAll(S, n) (S = (1 << n) - 1)

#define modulo(S, N) ((S) & (N - 1)) // returns S % N, where N is a power of 2
#define isPowerOfTwo(S) (!(S & (S - 1)))
#define nearestPowerOfTwo(S) ((int)pow(2.0, (int)((log((double)S) / log(2.0)) + 0.5)))
#define turnOffLastBit(S) ((S) & (S - 1))
#define turnOnLastZero(S) ((S) | (S + 1))
#define turnOffLastConsecutiveBits(S) ((S) & (S + 1))
#define turnOnLastConsecutiveZeroes(S) ((S) | (S - 1))

#define all(x) (x).begin(), (x).end()
#define unq(x) (x.resize(unique(all(x)) - x.begin()))

#define inf LLONG_MAX
#define mx  200005
#define mod 1000000007
#define block 555
#define A 1111111

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector< pll > vll;
typedef vector<string> vs;
typedef unsigned long long ull;
typedef double D;
typedef long double LD;
//int dx[]= {0,0,-1,1,1,-1,1,-1};
//int dy[]= {-1,1,0,0,1,-1,-1,1};

int cnt[A],a[mx],ans=0,answer[mx];
struct query
{
    int L,R,i;
} q[mx];

bool compare(query x, query y)
{
    if(x.L/block != y.L/block)
    {
        return x.L/block < y.L/block;
    }
    return x.R < y.R;
}

void remove(int i)
{
    cnt[a[i]]--;
    if(cnt[a[i]]==0)
        ans--;
}

void add(int i)
{
    cnt[a[i]]++;
    if(cnt[a[i]]==1)
        ans++;
}

int main()
{
    ll n,m;
    scanf("%lld",&n);
    for(int i=0; i<n; i++)
        scanf("%lld",&a[i]);
    scanf("%lld",&m);
    for(int i=0; i<m; i++)
    {
        scanf("%lld %lld",&q[i].L,&q[i].R);
        q[i].L--;
        q[i].R--;
        q[i].i = i;
    }
    sort(q,q+m,compare);
    int currentL=0,currentR=0;
    for(int j=0; j<m; j++)
    {
        int L = q[j].L, R = q[j].R;
        while(currentL < L)
        {
            remove(currentL);
            currentL++;
        }
        while(currentL > L)
        {
            add(currentL-1);
            currentL--;
        }
        while(currentR <= R)
        {
            add(currentR);
            currentR++;
        }
        while(currentR > R+1)
        {
            remove(currentR-1);
            currentR--;
        }
        answer[q[j].i] = ans;
    }

    for(int i=0; i<m; i++)
        printf("%d\n",answer[i]);
    return 0;
}