fork download
copy 
  1. //author: NgTh Thao Duyen ~~~
  2. //link submit: https://o...content-available-to-author-only...i.info/problem/dquery
  3. //date: 07.09.25
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. #define ll long long 
  7. const ll maxn = 1e6;
  8.  
  9. struct query{
  10.     ll l,r,idx;
  11. };
  12. query q[maxn+5];
  13. ll block;
  14.  
  15. bool cmp(query x, query y)
  16. {
  17.     if(x.l / block != y.l / block)return x.l / block < y.l / block;
  18.     return x.r < y.r;
  19. }
  20. ll a[maxn+5],n,k,dis,cnt[maxn+5],ans[maxn+5];
  21.  
  22. void add(ll pos)
  23. {
  24.     dis+=(++cnt[a[pos]]==1);
  25. }
  26.  
  27. void rem(ll pos)
  28. {
  29.     dis-=(--cnt[a[pos]]==0);
  30. }
  31. int main()
  32. {
  33.     ios_base::sync_with_stdio(0); cin.tie(0);
  34.     //freopen("task.inp","r",stdin);
  35.     cin>>n;
  36.     for(ll i=1; i<=n; i++)cin>>a[i];
  37.     cin>>k;
  38.     for(ll i=1; i<=k; i++)
  39.     {
  40.         cin>>q[i].l>>q[i].r;
  41.         q[i].idx = i;
  42.     }
  43.     block = sqrtl(n);
  44.     sort(q+1,q+k+1,cmp);
  45.     ll curl = 1, curr = 0;
  46.     for (int i = 1; i <= k; i++) {
  47.         ll L = q[i].l, R = q[i].r;
  48.         while (curl > L) add(--curl);
  49.         while (curr < R) add(++curr);
  50.         while (curl < L) rem(curl++);
  51.         while (curr > R) rem(curr--);
  52.         ans[q[i].idx] = dis;
  53.     }
  54.     for (ll i = 1; i <= k; i++) cout << ans[i] << "\n";
  55.  
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0.01s 5788KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xB6oxx
language:
C++ (gcc 8.3)
created:
4 hours 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!