• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

gmusya Feb 14th, 2020 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <math.h>
4. #include <string>
5. #include <unordered_map>
6.
7. using namespace std;
8.
9. struct chunk {
10.     unordered_map <int, int> cnt;
11.     vector <int> val;
12.     int size;
13.     int next;
14. };
15.
16. int n, q, X;
17. vector <int> a;
18. vector <chunk> sqrt_dec;
19.
20. void build_sqrt_dec() {
21.     X = ceil(sqrt(n));
22.     sqrt_dec.resize(X);
23.     for (int i = 0; i < X; i++) {
24.         for (int j = 0; j < X && i * X + j < n; j++) {
25.             sqrt_dec[i].cnt[a[i * X + j]]++;
26.             sqrt_dec[i].val.push_back(a[i * X + j]);
27.         }
28.         sqrt_dec[i].size = sqrt_dec[i].val.size();
29.         sqrt_dec[i].next = i + 1;
30.     }
31.     sqrt_dec[X - 1].next = -1;
32. }
33.
34. int query(int l, int r, int k) {
35.     int cur_pos = 0, i = 0, ans = 0;
36.     while (cur_pos + sqrt_dec[i].size <= l) {
37.         cur_pos += sqrt_dec[i].size;
38.         i = sqrt_dec[i].next;
39.     }
40.     if (cur_pos + sqrt_dec[i].size > r) {
41.         for (int j = l - cur_pos; j <= r - cur_pos; j++)
42.             ans += (sqrt_dec[i].val[j] == k);
43.         return ans;
44.     }
45.     for (int j = l - cur_pos; j < sqrt_dec[i].size; j++)
46.         ans += (sqrt_dec[i].val[j] == k);
47.     cur_pos += sqrt_dec[i].size;
48.     i = sqrt_dec[i].next;
49.     while (cur_pos + sqrt_dec[i].size <= r) {
50.         ans += sqrt_dec[i].cnt[k];
51.         cur_pos += sqrt_dec[i].size;
52.         i = sqrt_dec[i].next;
53.     }
54.     for (int j = 0; j <= r - cur_pos; j++)
55.         ans += (sqrt_dec[i].val[j] == k);
56.     return ans;
57. }
58.
59. void split(int i) {
60.     chunk old_chunk, new_chunk;
61.     for (int j = 0; j < sqrt_dec[i].size / 2; j++) {
62.         old_chunk.val.push_back(sqrt_dec[i].val[j]);
63.         old_chunk.cnt[sqrt_dec[i].val[j]]++;
64.     }
65.     for (int j = sqrt_dec[i].size / 2; j < sqrt_dec[i].size; j++) {
66.         new_chunk.val.push_back(sqrt_dec[i].val[j]);
67.         new_chunk.cnt[sqrt_dec[i].val[j]]++;
68.     }
69.     old_chunk.size = sqrt_dec[i].size / 2;
70.     new_chunk.size = sqrt_dec[i].size - sqrt_dec[i].size / 2;
71.     new_chunk.next = sqrt_dec[i].next;
72.     old_chunk.next = sqrt_dec.size();
73.     sqrt_dec[i] = old_chunk;
74.     sqrt_dec.push_back(new_chunk);
75. }
76.
77. void erase_and_insert(int pos_l, int pos_r) {
78.     int i = 0, cur_pos = 0;
79.     while (cur_pos + sqrt_dec[i].size <= pos_l) {
80.         cur_pos += sqrt_dec[i].size;
81.         i = sqrt_dec[i].next;
82.     }
83.     int cur_pos_for_l = cur_pos;
84.     int cur_i_for_l = i;
85.     while (cur_pos + sqrt_dec[i].size <= pos_r) {
86.         cur_pos += sqrt_dec[i].size;
87.         i = sqrt_dec[i].next;
88.     }
89.     int cur_pos_for_r = cur_pos;
90.     int cur_i_for_r = i;
91.     int val = sqrt_dec[cur_i_for_r].val[pos_r - cur_pos_for_r];
92.     sqrt_dec[cur_i_for_r].size--;
93.     for (int j = pos_r - cur_pos_for_r; j < sqrt_dec[cur_i_for_r].size; j++)
94.         sqrt_dec[cur_i_for_r].val[j] = sqrt_dec[cur_i_for_r].val[j + 1];
95.     sqrt_dec[cur_i_for_r].val.pop_back();
96.     sqrt_dec[cur_i_for_r].cnt[val]--;
97.     sqrt_dec[cur_i_for_l].size++;
98.     sqrt_dec[cur_i_for_l].val.push_back(0);
99.     for (int j = sqrt_dec[cur_i_for_l].size - 1; j > pos_l - cur_pos_for_l; j--)
100.         sqrt_dec[cur_i_for_l].val[j] = sqrt_dec[cur_i_for_l].val[j - 1];
101.     sqrt_dec[cur_i_for_l].val[pos_l - cur_pos_for_l] = val;
102.     sqrt_dec[cur_i_for_l].cnt[val]++;
103.     if (sqrt_dec[cur_i_for_l].size > 2 * sqrt_dec.size())
104.         split(cur_i_for_l);
105. }
106.
107. int main() {
108.     ios::sync_with_stdio(false);
109.     cin.tie(0);
110.     cin >> n;
111.     a.resize(n);
112.     for (int i = 0; i < n; i++)
113.         cin >> a[i];
114.     build_sqrt_dec();
115.     cin >> q;
116.     int last_ans = 0;
118.     for (int i = 0; i < q; i++) {
119.         int type;
120.         cin >> type;
121.         if (type == 1) {
122.             int _l, _r, l, r;
123.             cin >> _l >> _r;
124.             l = ((_l + last_ans - 1) % n);
125.             r = ((_r + last_ans - 1) % n);
126.             if (l > r)
127.                 swap(l, r);
128.             if (l != r)
129.                 erase_and_insert(l, r);
130.         }
131.         if (type == 2) {
132.             int _l, _r, _k, l, r, k;
133.             cin >> _l >> _r >> _k;
134.             l = ((_l + last_ans - 1) % n);
135.             r = ((_r + last_ans - 1) % n);
136.             k = ((_k + last_ans - 1) % n) + 1;
137.             if (l > r)
138.                 swap(l, r);
139.             last_ans = query(l, r, k);