fork download 
  1.     #include<bits/stdc++.h>
  2.     using namespace std;
  3.  
  4.     const int N = 2e5 + 5;
  5.     const int VAL = 1e6 + 5;
  6.     int n , q , S , ans;
  7.     int a[N] , cnt[VAL] , res[N];
  8.     int L = 1 , R = 0;
  9.  
  10.     struct query{
  11.         int l , r , id;
  12.     } qu[N];
  13.  
  14.     void MO(int i)
  15.     {
  16.         while(L < qu[i].l)
  17.         {
  18.             cnt[a[L]]--;
  19.             if(cnt[a[L]] == 0)
  20.                 ans--;
  21.             L++;
  22.         }
  23.         while(L > qu[i].l)
  24.         {
  25.             L--;
  26.             if(cnt[a[L]] == 0)
  27.                 ans++;
  28.             cnt[a[L]]++;
  29.         }
  30.         while(R < qu[i].r)
  31.         {
  32.             R++;
  33.             if(cnt[a[R]] == 0)
  34.                 ans++;
  35.             cnt[a[R]]++;
  36.  
  37.         }
  38.         while(R > qu[i].r)
  39.         {
  40.             cnt[a[R]]--;
  41.             if(cnt[a[R]] == 0)
  42.                 ans--;
  43.             R--;
  44.         }
  45.     }
  46.  
  47.     bool cmp(query a , query b)
  48.     {
  49.         if(a.l / S == b.l / S)
  50.             return a.r < b.r;
  51.         return a.l < b.l;
  52.     }
  53.  
  54.     main()
  55.     {
  56.         ios::sync_with_stdio(0);
  57.         cin.tie(0);
  58.         cin >> n;
  59.          S = sqrt(n);
  60.         for(int i = 1 ; i <= n ; i++)
  61.             cin >> a[i];
  62.         cin >> q;
  63.         for(int i = 1 ; i <= q ; i++)
  64.         {
  65.             cin >> qu[i].l >> qu[i].r;
  66.             qu[i].id = i;
  67.         }
  68.         sort(qu + 1 , qu + 1 + q , cmp);
  69.  
  70.         for(int i = 1 ; i <= q ; i++)
  71.         {
  72.             MO(i);
  73.             res[qu[i].id] = ans;
  74.         }
  75.         for(int i = 1 ; i <= q ; i++)
  76.             cout << res[i] << "\n";
  77.     }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/mpXQD3
language:
C++14 (gcc 8.3)
created:
283 days 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!