Advertisement
tiom4eg

count diff numbers on segments

Aug 24th, 2022 (edited)
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. // tiom4eg's precompiler options
  3. // POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
  4. // IO settings
  5. #define fastIO ios_base::sync_with_stdio(false); cin.tie(0)
  6. // Quick types
  7. #define ll long long
  8. #define ld double
  9. #define ull unsigned long long
  10. #define pii pair <int, int>
  11. #define pll pair <ll, ll>
  12. #define vi vector <int>
  13. #define mi vector <vector <int> >
  14. // Quick functions
  15. #define endl "\n"
  16. #define F first
  17. #define S second
  18. #define all(a) a.begin(), a.end()
  19. #define sz(a) a.size()
  20. #define pb push_back
  21. #define mp make_pair
  22. #define fint(n) int n; cin >> n
  23. #define fstr(s) string s; cin >> s
  24. #define farr(a, n) int a[n]; for (int pog = 0; pog < n; ++pog) cin >> a[pog]
  25. // Quick fors
  26. #define FOR(i, a, b) for (int i = a; i < b; ++i)
  27. #define RFOR(i, a, b) for (int i = a; i >= b; --i)
  28. // Pragmas
  29. #pragma GCC optimize("O3,unroll-loops") // let the chaos begin!
  30. #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
  31. #pragma GCC comment(linker, "/stack:200000000")
  32. // POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
  33. using namespace std;
  34. #include <ext/pb_ds/assoc_container.hpp>
  35. using namespace __gnu_pbds;
  36.  
  37. struct splitmix64 {
  38.     size_t operator()(size_t x) const {
  39.         static const size_t fixed = chrono::steady_clock::now().time_since_epoch().count();
  40.         x += 0x9e3779b97f4a7c15 + fixed;
  41.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  42.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  43.         return x ^ (x >> 31);
  44.     }
  45. };
  46.  
  47. int R = 1;
  48.  
  49. struct segtree {
  50.     vi cnt;
  51.     void init() { cnt.resize(2 * R); }
  52.     void inc(int p) {
  53.         p += R;
  54.         while (p) cnt[p]++, p >>= 1;
  55.     }
  56.     void dec(int p) {
  57.         p += R;
  58.         while (p) cnt[p]--, p >>= 1;
  59.     }
  60.     int rsq(int l, int r) {
  61.         int res = 0;
  62.         l += R, r += R;
  63.         while (l < r) {
  64.             if (l & 1) res += cnt[l];
  65.             if (!(r & 1)) res += cnt[r];
  66.             l = (l + 1) >> 1, r = (r - 1) >> 1;
  67.         }
  68.         if (l == r) res += cnt[l];
  69.         return res;
  70.     }
  71. };
  72.  
  73. int main() {
  74.     fastIO;
  75.     int n; cin >> n;
  76.     while (R < n) R <<= 1;
  77.     int a[n]; FOR(i, 0, n) cin >> a[i];
  78.     segtree t;
  79.     t.init();
  80.     gp_hash_table <int, int, splitmix64> pos;
  81.     int q; cin >> q;
  82.     vector <pair <int, pii> > qry(q);
  83.     FOR(i, 0, q) {
  84.         int l, r; cin >> l >> r, l--, r--;
  85.         qry[i] = {i, {l, r}};
  86.     }
  87.     stable_sort(all(qry), [](const auto& p1, const auto& p2){ return p1.S.S < p2.S.S; });
  88.     int ans[q]; FOR(i, 0, q) ans[i] = 0;
  89.     int p = 0;
  90.     FOR(i, 0, n) {
  91.         if (pos.find(a[i]) != pos.end()) t.dec(pos[a[i]]);
  92.         pos[a[i]] = i;
  93.         t.inc(pos[a[i]]);
  94.         while (p < q && qry[p].S.S == i) ans[qry[p].F] = t.rsq(qry[p].S.F, qry[p].S.S), p++;
  95.     }
  96.     FOR(i, 0, q) cout << ans[i] << endl;
  97. }
  98.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement