fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. // #define int long long
  4. const int maxn = 1e6 + 5;
  5. const int mod = 1e9 + 7;
  6. // const int oo = 1e18 + 5;
  7. typedef pair<int, int> ii;
  8. typedef pair<int, pair<int, int>> iii;
  9. #define fi first
  10. #define se second
  11. #define read(_a, n)              \
  12.     for (int i = 1; i <= n; i++) \
  13.     cin >> _a[i]
  14. #define For(i, _a, _b) for (int i = _a; i <= _b; i++)
  15. #define fastIO                        \
  16.     ios_base::sync_with_stdio(false); \
  17.     cin.tie(0);                       \
  18.     cout.tie(0);
  19. #define File(_x, _y)    \
  20.     if (fopen(_x, "r")) \
  21.     freopen(_x, "r", stdin), freopen(_y, "w", stdout)
  22. #define file "main"
  23. #define bit(x, i) ((x >> i) & 1)
  24. #define bat(x, i) (x(1 << i))
  25.  
  26. int n, m, block, res;
  27. int cnt[maxn], ans[maxn], t;
  28. int a[maxn];
  29. set<int> s;
  30.  
  31. struct query
  32. {
  33.     int l;int r;int k;
  34.     int id;
  35. } q[maxn];
  36.  
  37. bool cmp(query a, query b)
  38. {
  39.     int pa = a.r / block, pb = b.r / block;
  40.     if (pa != pb) return pa < pb;
  41.     if (pa % 2 == 0) return a.l < b.l;
  42.     else return a.l > b.l;
  43. }
  44.  
  45. vector<int> b;
  46.  
  47. int T[maxn];
  48. int N = 3e5;
  49. void update(int p, int v)
  50. {
  51.     while(p <= N) T[p] += v, p += p&(-p);
  52. }
  53.  
  54. int get(int p) 
  55. {
  56.     int res = 0;
  57.     while(p > 0) res += T[p], p -= p&(-p);
  58.     return res;
  59. }
  60.  
  61. void chuyen(int l, int r, int l1, int r1)
  62. {
  63.     while (l < l1) // [l, r] -> [l+1, r]
  64.     {
  65.         int v = a[l++];
  66.         if(cnt[v] == 2) res--;
  67.         if(cnt[v] == 3) res++;
  68.         cnt[v]--;
  69.     }
  70.     while (r > r1) // [l, r] -> [l, r-1]
  71.     {
  72.         int v = a[r--];
  73.         if(cnt[v] == 2) res--;
  74.         if(cnt[v] == 3) res++;
  75.         cnt[v]--;
  76.     }
  77.     while (l > l1) //[l, r] -> [l-1, r]
  78.     {
  79.         int v = a[--l];
  80.         if(cnt[v] == 2) res--;
  81.         if(cnt[v] == 1) res++;
  82.         cnt[v]++;
  83.     }
  84.     while (r < r1) //[l, r] -> [l, r+1]
  85.     {
  86.         int v = a[++r];
  87.         if(cnt[v] == 2) res--;
  88.         if(cnt[v] == 1) res++;
  89.         cnt[v]++;
  90.     }
  91. }
  92.  
  93. void nenso()
  94. {
  95.     for (int i : s)
  96.         b.push_back(i);
  97.     sort(b.begin(), b.end());
  98.     for (int i = 1; i <= n; i++)
  99.         a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
  100. }
  101.  
  102. int32_t main()
  103. {
  104.     fastIO;
  105.     File(file ".inp", file ".out");
  106.  
  107.     cin >> n >> t;
  108.     while(block * block < n) block++;
  109.  
  110.     for(int i = 1; i <= n; i++) cin >> a[i], s.insert(a[i]);
  111.     nenso();
  112.     for(int i = 1; i <= t; i++)
  113.     {
  114.         cin >> q[i].l >> q[i].r;
  115.         q[i].id = i;
  116.     }
  117.     sort(q+1, q+t+1, cmp);
  118.     for(int i = 1; i <= t; i++)
  119.     {
  120.         chuyen(q[i-1].l, q[i-1].r, q[i].l, q[i].r);
  121.         ans[q[i].id] = res;
  122.     }
  123.     for(int i = 1; i <= t; i++) cout << ans[i] << "\n";
  124. }
  125.  
Success #stdin #stdout 0.01s 7720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IOQ8kT
language:
C++14 (clang 8.0)
created:
4 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!