fork download
copy 
  1. /*Author: KawakiMeido*/
  2. #include <bits/stdc++.h>
  3. #define pb push_back
  4. #define endl "\n"
  5. #define ll long long
  6. #define pii pair<int,int>
  7. #define fi first
  8. #define se second
  9.  
  10. using namespace std;
  11.  
  12. /*Constants*/
  13. const int N = 2e5+10;
  14. const int INF = 1e9+7;
  15. const long long LLINF = 1e18+3;
  16.  
  17. /*TestCases*/
  18. int test=1;
  19. void solve();
  20. void TestCases(bool v){
  21.     if (v) cin >> test;
  22.     while(test--) solve();
  23. }
  24.  
  25. /*Global Variables*/
  26. int n,q;
  27. int IT[N*4];
  28. int ans[N];
  29. int a[N];
  30. map<int,int> mp;
  31. vector<pair<pii,int>> v;
  32.  
  33. void update(int idx, int l, int r, int x, int val){
  34.     if (x < l || r < x) return;
  35.     if (l == r){
  36.         IT[idx] = val;
  37.         return;
  38.     }
  39.     int mid = (l+r)/2;
  40.     update(idx*2,l,mid,x,val);
  41.     update(idx*2+1,mid+1,r,x,val);
  42.     IT[idx] = IT[idx*2] + IT[idx*2+1];
  43. }
  44.  
  45. int query(int idx, int l, int r, int x, int y){
  46.     if (y < l || r < x) return 0;
  47.     if (x <= l && r <= y) return IT[idx];
  48.     int mid = (l+r)/2;
  49.     return query(idx*2,l,mid,x,y) + query(idx*2+1,mid+1,r,x,y);
  50. }
  51.  
  52. /*Solution*/
  53. void solve(){
  54.     cin >> n >> q;
  55.     for (int i=1; i<=n; i++){
  56.         cin >> a[i];
  57.     }
  58.     for (int i=1; i<=q; i++){
  59.         int l,r;
  60.         cin >> l >> r;
  61.         v.push_back({{r,l},i});
  62.     }
  63.     v.push_back({{INF,INF},INF});
  64.     int idx = 0;
  65.     sort(v.begin(),v.end());
  66. //    for (int i=1; i<=100; i++){
  67. //        cout << query(1,1,n,i,i) << " ";
  68. //    }
  69.     for (int i=1; i<=n; i++){
  70.         if (mp.find(a[i]) != mp.end()){
  71.             update(1,1,n,mp[a[i]],0);
  72.         }
  73.         mp[a[i]] = i;
  74.         update(1,1,n,i,1);
  75.         while(v[idx].fi.fi<=i){
  76.             int l = v[idx].fi.se;
  77.             int r = v[idx].fi.fi;
  78.             int bruh = v[idx].se;
  79. //            cout << bruh << " " << l << " " << r << endl;
  80.             ++idx;
  81.             ans[bruh] = query(1,1,n,l,r);
  82.         }
  83.     }
  84. //    cout << endl;
  85.     for (int i=1; i<=q; i++){
  86.         cout << ans[i] << endl;
  87.     }
  88. //    for (int i=1; i<=100; i++){
  89. //        cout << query(1,1,n,i,i) << " ";
  90. //    }
  91. //    cout << endl;
  92. }
  93.  
  94. /*Driver Code*/
  95. int main(){
  96.     ios_base::sync_with_stdio(0);
  97.     cin.tie(0);
  98.  
  99.     TestCases(0);
  100.  
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lP6ZBI
language:
C++14 (gcc 8.3)
created:
12 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!