Nusrat_Ullah

Mo's Implementation

Sep 28th, 2020
876
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct info
  4. {
  5.     int lo,hi,ps;
  6. };
  7. int zz,wq1[30003],nt[1000003],re1[200003];
  8. info wq2[200003];
  9. bool unq(info z,info x)
  10. {
  11.     int a,s;
  12.     a=z.lo/zz, s=x.lo/zz;
  13.     if(a==s) return (a&1)?z.hi>x.hi:z.hi<x.hi;
  14.     return z.lo<x.lo;
  15. }
  16. int main()
  17. {
  18.     int g,t,y,lo,hi,re;
  19.     scanf("%d",&t);
  20.     for(g=0;g<t;g++)
  21.         scanf("%d",&wq1[g]);
  22.     zz=int(sqrt(t+0.00)+1);
  23.     scanf("%d",&y);
  24.     for(g=0;g<y;g++){
  25.         scanf("%d %d",&wq2[g].lo,&wq2[g].hi);
  26.         wq2[g].lo--, wq2[g].hi--;
  27.         wq2[g].ps=g;
  28.     }
  29.     sort(wq2,wq2+y,unq);
  30.  
  31.     for(g=lo=re=0,hi=-1;g<y;g++){
  32.         while(lo<wq2[g].lo){
  33.             nt[wq1[lo]]--;
  34.             if(!nt[wq1[lo]])re--;
  35.             lo++;
  36.         }
  37.         while(lo>wq2[g].lo){
  38.             lo--;
  39.             if(!nt[wq1[lo]])re++;
  40.             nt[wq1[lo]]++;
  41.         }
  42.         while(hi<wq2[g].hi){
  43.             hi++;
  44.             if(!nt[wq1[hi]])re++;
  45.             nt[wq1[hi]]++;
  46.         }
  47.         while(hi>wq2[g].hi){
  48.             nt[wq1[hi]]--;
  49.             if(!nt[wq1[hi]])re--;
  50.             hi--;
  51.         }
  52.         re1[wq2[g].ps]=re;
  53.     }
  54.     for(g=0;g<y;g++)printf("%d\n",re1[g]);
  55.     return 0;
  56. }
  57.  
RAW Paste Data