MinhNGUYEN2k4

Untitled

Sep 18th, 2021
662
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 500005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19.  
  20. using namespace std;
  21.  
  22. typedef long double ld;
  23. const int inf = 1e10;
  24. const int minf = -1e10;
  25.  
  26. int n, m, bsize;
  27. int a[N];
  28.  
  29. void readfile()
  30. {
  31.     ios_base::sync_with_stdio(false);
  32.     cin.tie(0);cout.tie(0);
  33.     if (fopen(Task".inp","r"))
  34.     {
  35.         freopen(Task".inp","r",stdin);
  36.         //freopen(Task".out","w",stdout);
  37.     }
  38.     cin >> n >> m;
  39.     for(int i=1; i<=n; i++) cin >> a[i];
  40. }
  41.  
  42. void compress(){
  43.     vector<int> b(a+1,a+1+n);
  44.     sort(all(b));
  45.     b.erase(unique(all(b)),b.end());
  46.     for(int i=1; i<=n; i++){
  47.         int k = lower_bound(all(b),a[i])-b.begin();
  48.         a[i] = b[k];
  49.     }
  50. }
  51.  
  52. struct query{
  53.     int l, r;
  54.     int idx;
  55.     bool operator < (const query& a){
  56.         if ((l-1)/bsize != (a.l-1)/bsize) return (l-1)/bsize < (a.l-1)/bsize;
  57.         return r < a.r;
  58.     }
  59. };
  60. query Q[N];
  61.  
  62. int nho[N];
  63. int ans=0;
  64. int res[N];
  65.  
  66. void add(int pos){
  67.     nho[a[pos]]++;
  68.     if (nho[a[pos]]==2) ans++;
  69.     if (nho[a[pos]]==3) ans--;
  70. }
  71.  
  72. void del(int pos){
  73.     nho[a[pos]]--;
  74.     if (nho[a[pos]]==2) ans++;
  75.     if (nho[a[pos]]==1) ans--;
  76. }
  77.  
  78. void proc()
  79. {
  80.     compress();
  81.     bsize = sqrt(n)+1;
  82.     for(int i=1; i<=m; i++){
  83.         cin >> Q[i].l >> Q[i].r;
  84.         Q[i].idx = i;
  85.     }
  86.     sort(Q+1,Q+1+m);
  87.     int l=0, r=0;
  88.     for(int i=1; i<=m; i++){
  89.         int u = Q[i].l;
  90.         int v = Q[i].r;
  91.         int id = Q[i].idx;
  92.         while (l > u) add(--l);
  93.         while (l < u) del(l++);
  94.         while (r < v) add(++r);
  95.         while (v < r) del(r--);
  96.         res[id] = ans;
  97.     }
  98.     for(int i=1; i<=m; i++) cout << res[i] << '\n';
  99. }
  100.  
  101. signed main()
  102. {
  103.     readfile();
  104.     proc();
  105.     return 0;
  106. }
  107.  
RAW Paste Data