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;
  117.     vector <int> answer;
  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);
  140.             answer.push_back(last_ans);
  141.         }
  142.     }
  143.     for (auto now : answer)
  144.         cout << now << '\n';
  145.     return 0;
  146. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top