SHOW:
|
|
- or go back to the newest paste.
| 1 | #include<bits/stdc++.h> | |
| 2 | using namespace std; | |
| 3 | ||
| 4 | ||
| 5 | template<typename T> | |
| 6 | class persistent_segtree | |
| 7 | {
| |
| 8 | public: | |
| 9 | ||
| 10 | int n, m; | |
| 11 | vector<int> root, lc, rc; | |
| 12 | vector<T> st; | |
| 13 | int FREE_ID = 0; | |
| 14 | ||
| 15 | persistent_segtree() {}
| |
| 16 | ||
| 17 | persistent_segtree(int n_, int m_, T val = T()) | |
| 18 | {
| |
| 19 | n = n_; | |
| 20 | m = m_; | |
| 21 | FREE_ID = 0; | |
| 22 | root.resize(n + 2); | |
| 23 | st.resize(m + 2, val); | |
| 24 | lc.resize(m + 2); | |
| 25 | rc.resize(m + 2); | |
| 26 | } | |
| 27 | ||
| 28 | T merge(T a, T b) | |
| 29 | {
| |
| 30 | T res = a + b; | |
| 31 | return res; | |
| 32 | } | |
| 33 | ||
| 34 | int build(int l, int r) // create one dummy tree | |
| 35 | {
| |
| 36 | int node = ++FREE_ID; | |
| 37 | if (l == r) | |
| 38 | {
| |
| 39 | return node; | |
| 40 | } | |
| 41 | int mid = (l + r) >> 1; | |
| 42 | lc[node] = build(l, mid); | |
| 43 | rc[node] = build(mid + 1, r); | |
| 44 | return node; | |
| 45 | } | |
| 46 | ||
| 47 | int update(int prev, int ss, int se, int pos, int val) | |
| 48 | {
| |
| 49 | int node = ++FREE_ID; | |
| 50 | if (ss == se) | |
| 51 | {
| |
| 52 | st[node] = val; | |
| 53 | return node; | |
| 54 | } | |
| 55 | lc[node] = lc[prev]; | |
| 56 | rc[node] = rc[prev]; | |
| 57 | int mid = (ss + se) >> 1; | |
| 58 | if (pos <= mid) | |
| 59 | {
| |
| 60 | lc[node] = update(lc[prev], ss, mid, pos, val); | |
| 61 | } | |
| 62 | else | |
| 63 | {
| |
| 64 | rc[node] = update(rc[prev], mid + 1, se, pos, val); | |
| 65 | } | |
| 66 | st[node] = merge(st[lc[node]], st[rc[node]]); | |
| 67 | return node; | |
| 68 | } | |
| 69 | ||
| 70 | T query(int node, int ss, int se, int qs, int qe) | |
| 71 | {
| |
| 72 | if (qs > se || qe < ss) | |
| 73 | {
| |
| 74 | return T(); | |
| 75 | } | |
| 76 | if (qs <= ss && se <= qe) | |
| 77 | {
| |
| 78 | return st[node]; | |
| 79 | } | |
| 80 | int mid = (ss + se) >> 1; | |
| 81 | T res = merge(query(lc[node], ss, mid, qs, qe), query(rc[node], mid + 1, se, qs, qe)); | |
| 82 | return res; | |
| 83 | } | |
| 84 | ||
| 85 | }; | |
| 86 | ||
| 87 | const int N = 1e5 + 5; | |
| 88 | ||
| 89 | int a[N], val[N]; | |
| 90 | vector<int> adj[N]; | |
| 91 | int n, k, q; | |
| 92 | persistent_segtree<int> obj; | |
| 93 | ||
| 94 | signed main() | |
| 95 | {
| |
| 96 | ios_base::sync_with_stdio(false); | |
| 97 | cin.tie(NULL); cout.tie(NULL); | |
| 98 | ||
| 99 | #ifndef ONLINE_JUDGE | |
| 100 | freopen("input.txt", "r", stdin);
| |
| 101 | freopen("output.txt", "w", stdout);
| |
| 102 | #endif | |
| 103 | ||
| 104 | cin >> n >> k; | |
| 105 | for (int i = 1; i <= n; i++) | |
| 106 | {
| |
| 107 | cin >> a[i]; | |
| 108 | adj[a[i]].push_back(i); | |
| 109 | int sz = adj[a[i]].size(); | |
| 110 | val[i] = 0; | |
| 111 | if (sz > k) | |
| 112 | {
| |
| 113 | val[i] = adj[a[i]][sz - k - 1]; | |
| 114 | } | |
| 115 | } | |
| 116 | ||
| 117 | cin >> q; | |
| 118 | int sz1 = n << 1; | |
| 119 | int sz2 = (log2(n) + 1) * (sz1 + 1); | |
| 120 | sz2 <<= 1; | |
| 121 | obj = persistent_segtree<int> (sz1, sz2); | |
| 122 | obj.root[0] = obj.build(1, n); | |
| 123 | ||
| 124 | for (int i = 1; i <= n; i++) | |
| 125 | {
| |
| 126 | obj.root[i] = obj.update(obj.root[i - 1], 1, n, i, +1); | |
| 127 | if (val[i]) | |
| 128 | {
| |
| 129 | obj.root[i] = obj.update(obj.root[i], 1, n, val[i], 0); | |
| 130 | } | |
| 131 | } | |
| 132 | ||
| 133 | ||
| 134 | int last = 0; | |
| 135 | for (int i = 1; i <= q; i++) | |
| 136 | {
| |
| 137 | int x, y; | |
| 138 | cin >> x >> y; | |
| 139 | int l = ((x + last) % n) + 1; | |
| 140 | int r = ((y + last) % n) + 1; | |
| 141 | if (l > r) | |
| 142 | {
| |
| 143 | swap(l, r); | |
| 144 | } | |
| 145 | last = obj.query(obj.root[r], 1, n, l, r); | |
| 146 | cout << last << endl; | |
| 147 | } | |
| 148 | ||
| 149 | return 0; | |
| 150 | } |
