fork download
copy 
  1. /**
  2. *    Author : M1nK
  3. *    Device : Laptop
  4. *    Created : 25.10.2025
  5. *    Problem : https://o...content-available-to-author-only...i.info/problem/dquery
  6. **/
  7.  
  8. #include <bits/stdc++.h>
  9.  
  10. // #pragma GCC target ("avx2")
  11. // #pragma GCC optimization ("O3")
  12. // #pragma GCC optimization ("unroll-loops")
  13.  
  14. //  M1nK's Ducky Mask: "Strongest Man In The World"
  15.  
  16. #define task "TASK"
  17.  
  18. #define el '\n'
  19. #define fi first
  20. #define se second
  21. #define pi acos (-1)
  22. #define pb push_back
  23. #define ll long long
  24. #define ld long double
  25. #define pll pair <ll, ll>
  26. #define ull unsigned ll
  27. #define pll2 pair <ll, pll>
  28. #define all(a) a.begin (), a.end ()
  29. #define heap_max(a) priority_queue <a>
  30. #define REP(i, n) for (ll i = 0, _n = (n); i < _n; i++)
  31. #define REPD(i, n) for (ll _n = (n), i = _n - 1; i >= 0; i--)
  32. #define FOR(i, a, b) for (ll i = (a), _b = (b); i <= _b; i++)
  33. #define FOD(i, a, b) for (ll i = (a), _b = (b); i >= _b; i--)
  34. #define heap_min(a) priority_queue <a, vector <a>, greater <a>>
  35. #define FOr(i, a, b, c) for (ll i = (a), _b = (b); i <= _b; i += (c))
  36. #define FOd(i, a, b, c) for (ll i = (a), _b = (b); i >= _b; i -= (c))
  37.  
  38. #define Mirai ios_base:: sync_with_stdio (1 + 1 == 3);
  39. #define Kuriyama cin.tie (nullptr); cout.tie (nullptr);
  40.  
  41. using namespace std;
  42. const ll INF = LLONG_MAX;
  43. const int MOD = 1e9 + 7;
  44. const int minN = 1e3 + 7;
  45. const int maxN = 1e5 + 7;
  46. const int LOG = __lg (maxN) + 1; 
  47.  
  48. template <class X> ll Mask (X s) { return (1LL << s); }
  49. template <class X> ll BitGet (X s, ll i) { return (s >> i) & 1LL; }
  50. template <class X> ll BitCnt (X s) { return __builtin_popcountll (s); }
  51. template <class X, class Y> bool maximize (X &a, Y b) { return (a < b) ? a = b, 1 : 0; }
  52. template <class X, class Y> bool minimize (X &a, Y b) { return (a > b) ? a = b, 1 : 0; }
  53.  
  54. // --------------- M1nK_08 --------------- //
  55.  
  56. ll n, q, l, r;
  57.  
  58. ll a[maxN], root[maxN], pos[maxN * 10];
  59.  
  60. ll total;
  61. ll st[maxN * 100], le[maxN * 100], ri[maxN * 100];
  62. void Upd (ll pos, ll val, ll pre, ll &id, ll l = 1, ll r = n) {
  63.     id = ++total;
  64.     st[id] = st[pre];
  65.     le[id] = le[pre];
  66.     ri[id] = ri[pre];
  67.     if (l == r) { st[id] = val; return; }
  68.     ll mid = (l + r) >> 1;
  69.     if (pos <= mid) Upd (pos, val, le[id], le[id], l, mid);
  70.     else Upd (pos, val, ri[id], ri[id], mid + 1, r);
  71.     st[id] = st[le[id]] + st[ri[id]];
  72. }
  73. ll Sum (ll u, ll v, ll id, ll l = 1, ll r = n) {
  74.     if (r < u || v < l) return 0;
  75.     if (u <= l && r <= v) return st[id];
  76.     ll mid = (l + r) >> 1;
  77.     return Sum (u, v, le[id], l, mid) + Sum (u, v, ri[id], mid + 1, r);
  78. }
  79.  
  80. void Solve () {
  81.     cin >> n;
  82.     FOR (i, 1, n) cin >> a[i];
  83.     FOR (i, 1, n) {
  84.         ll ver = root[i - 1];
  85.         if (pos[a[i]]) Upd (pos[a[i]], 0, ver, ver);
  86.         Upd (i, 1, ver, root[i]);
  87.         pos[a[i]] = i;
  88.     }
  89.  
  90.     cin >> q;
  91.     while (q--) {
  92.         cin >> l >> r;
  93.         cout << Sum (l, r, root[r]) << '\n';
  94.     }
  95. }
  96.  
  97. signed main (void) {
  98.     Mirai Kuriyama;  
  99.     if (fopen (task".INP", "r")) {
  100.         freopen (task".INP", "r", stdin);
  101.         freopen (task".OUT", "w", stdout);
  102.     }
  103.     int t = 1; 
  104.     // cin >> t;
  105.     while (t--) Solve ();
  106.     return 0;
  107. }
  108. // targeties: 1
  109.  
Success #stdin #stdout 0.01s 5680KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/Kl8ILY
language:
C++14 (gcc 8.3)
created:
71 days ago
visibility:
secret

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!