fork download
copy 
  1. //Mo's Algorithm WTF lol
  2. #include<stdio.h>
  3. #include<list>
  4. #include<algorithm>
  5. #define gc getchar_unlocked
  6. using namespace std;
  7. int visited[1000001];
  8. int A[30001];
  9. pair < int , pair <int , int > > Q[200000];
  10. int queries[200000];
  11. int fastscan();
  12. inline void printint(int a)
  13. {
  14.     char s[11];
  15.     int t = -1;
  16.     do{
  17.     s[++t] = a % 10 + '0';
  18.     a /= 10;
  19. }while(a > 0);
  20.     while(t >= 0)putchar_unlocked(s[t--]);
  21.     putchar_unlocked('\n');
  22. }
  23. bool cmp(pair < int , pair <int , int > > a , pair < int , pair <int , int > > b);
  24. int main()
  25. {
  26.     int n,i,j=-1,q,qe,qr,L=-1,R=-1,ans=0,k,idx;
  27.     n=fastscan();
  28.     for(i=0;i<n;i++)
  29.         A[i]=fastscan();
  30.     q=fastscan();
  31.     for(i=0;i<q;i++)
  32.     {
  33.         qe=fastscan();
  34.         qr=fastscan();
  35.         Q[i]=make_pair(qe-1,make_pair(qr-1,i));
  36.     }
  37.     sort(Q,Q+q,cmp);
  38.     for(i=0;i<q;i++)
  39.     {
  40.         j=Q[i].first;
  41.         k=Q[i].second.first;
  42.         idx=Q[i].second.second;
  43.         if(L==-1)
  44.         {
  45.             L=j;
  46.             R=k;
  47.             for(int it=j;it<=k;it++)
  48.             {
  49.                 visited[A[it]]++;
  50.                 if(visited[A[it]]==1)
  51.                     ans++;
  52.             }
  53.         }
  54.         while(L<j)
  55.         {
  56.             visited[A[L]]--;
  57.             if(visited[A[L]]==0)
  58.                 ans--;
  59.             L++;
  60.         }
  61.         while(L>j)
  62.         {
  63.             L--;
  64.             visited[A[L]]++;
  65.             if(visited[A[L]]==1)
  66.                 ans++;;
  67.  
  68.         }
  69.         while(R<k)
  70.             {
  71.                 R++;
  72.                 visited[A[R]]++;
  73.                 if(visited[A[R]]==1)
  74.                     ans++;
  75.             }
  76.         while(R>k)
  77.         {
  78.             visited[A[R]]--;
  79.             if(visited[A[R]]==0)
  80.                 ans--;
  81.             R--;
  82.         }
  83.         queries[idx]=ans;
  84.     }
  85.     for(i=0;i<q;i++)
  86.         printint(queries[i]);
  87.     return 0;
  88. }
  89. int fastscan()
  90. {
  91.     register int n=0;
  92.     char ch=gc();
  93.     for(;(ch<48||ch>57);ch=gc())
  94.         ;
  95.     for(;(ch>47&&ch<58);ch=gc())
  96.         n=(n<<3)+(n<<1)+ch-48;
  97.    /* for(;ch>47 && ch<58;ch = gc())
  98.     {
  99.         x = (x<<1) + (x<<3) + ch - 48;
  100.     }*/
  101.     return n;
  102.  
  103. }
  104.  
  105. bool cmp(pair < int , pair <int , int > > a , pair < int , pair <int , int > > b)
  106. {
  107.     if(a.first<b.first)
  108.         return true;
  109.     else if(a.first==b.first)
  110.     {
  111.         if(a.second<b.second)
  112.             return true;
  113.         else
  114.             return false;
  115.     }
  116.     else
  117.         return false;
  118. }
  119.  
Success #stdin #stdout 0s 10296KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/mpSL6G
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!