Mo's Implementation

#include<bits/stdc++.h>
using namespace std;
struct info
{
    int lo,hi,ps;
};
int zz,wq1[30003],nt[1000003],re1[200003];
info wq2[200003];
bool unq(info z,info x)
{
    int a,s;
    a=z.lo/zz, s=x.lo/zz;
    if(a==s) return (a&1)?z.hi>x.hi:z.hi<x.hi;
    return z.lo<x.lo;
}
int main()
{
    int g,t,y,lo,hi,re;
    scanf("%d",&t);
    for(g=0;g<t;g++)
        scanf("%d",&wq1[g]);
    zz=int(sqrt(t+0.00)+1);
    scanf("%d",&y);
    for(g=0;g<y;g++){
        scanf("%d %d",&wq2[g].lo,&wq2[g].hi);
        wq2[g].lo--, wq2[g].hi--;
        wq2[g].ps=g;
    }
    sort(wq2,wq2+y,unq);

    for(g=lo=re=0,hi=-1;g<y;g++){
        while(lo<wq2[g].lo){
            nt[wq1[lo]]--;
            if(!nt[wq1[lo]])re--;
            lo++;
        }
        while(lo>wq2[g].lo){
            lo--;
            if(!nt[wq1[lo]])re++;
            nt[wq1[lo]]++;
        }
        while(hi<wq2[g].hi){
            hi++;
            if(!nt[wq1[hi]])re++;
            nt[wq1[hi]]++;
        }
        while(hi>wq2[g].hi){
            nt[wq1[hi]]--;
            if(!nt[wq1[hi]])re--;
            hi--;
        }
        re1[wq2[g].ps]=re;
    }
    for(g=0;g<y;g++)printf("%d\n",re1[g]);
    return 0;
}