fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,q,a[300005],ans[300005],bit[300005];
  5. map <int,int> mp;
  6. vector <pair<int,int>> ve[300005];
  7. void UPDATE(int i, int v)
  8. {
  9.     while (i<=n) bit[i]+=v,i+=i&(-i);
  10.     return;
  11. }
  12. int GET(int l, int r)
  13. {
  14.     l--;
  15.     int resl=0,resr=0;
  16.     while (l>0) resl+=bit[l],l-=l&(-l);
  17.     while (r>0) resr+=bit[r],r-=r&(-r);
  18.     return resr-resl;
  19. }
  20. signed main()
  21. {
  22.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  23.     cin>>n>>q;
  24.     for (int i=1;i<=n;i++) cin>>a[i];
  25.     for (int i=1;i<=q;i++) 
  26.     {
  27.         int l,r;
  28.         cin>>l>>r;
  29.         ve[r].push_back({l,i});
  30.     }
  31.     for (int i=1;i<=n;i++)
  32.     {
  33.         if (!mp[a[i]]) mp[a[i]]=i,UPDATE(i,1);
  34.         else UPDATE(i,1),UPDATE(mp[a[i]],-1),mp[a[i]]=i;
  35.         for (pair <int,int> p : ve[i])
  36.         {
  37.             int l=p.first,idx=p.second;
  38.             ans[idx]=GET(l,i);
  39.         }
  40.     }
  41.     for (int i=1;i<=q;i++) cout<<ans[i]<<'\n';
  42.     return 0;
  43. }
Success #stdin #stdout 0.01s 11288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OiPCIf
language:
C++14 (gcc 8.3)
created:
1 day 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!