fork download 
  1. #pragma GCC optimize("O3","unroll-loops", "inline-functions", "Ofast", "-funroll-loops")
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define FOR(i, a, b)        for (int i = (a), _b = (b); i <= _b; ++i)
  7. #define FORD(i, a, b)       for (int i = (a), _b = (b); i >= _b; --i)
  8. #define REP(i, n)           for (int i = (0), _n = (n); i < _n; ++i)
  9. #define el                  cout << '\n'
  10.  
  11. //--FastIO-------------------------------------------------------------------------------------
  12.  
  13. static constexpr int SIZE = 1 << 16;
  14. char buffer[SIZE];
  15. int cpos = SIZE, clen = SIZE;
  16.  
  17. inline int InChar()
  18. {
  19.     if (cpos == clen)
  20.     {
  21.         clen = (int) fread(buffer, 1, SIZE, stdin);
  22.         if (clen == 0) return EOF;
  23.         cpos = 0;
  24.     }
  25.     return buffer[cpos++];
  26. }
  27.  
  28. inline int ReadInt()
  29. {
  30.     int x = 0, p = 1;
  31.     char c = InChar();
  32.     while (c != EOF && !isdigit(c) && c != '-') c = InChar();
  33.     if (c == '-') p = -1, c = InChar();
  34.     while (c != EOF && isdigit(c)) x = x * 10 + (c - 48), c = InChar();
  35.     return x * p;
  36. }
  37.  
  38. constexpr int MAXN = 1e5 + 2, BLOCK_SZ = 400;
  39. int n, q;
  40. int a[MAXN];
  41. long long inv[min(600, MAXN / BLOCK_SZ) + 1][min(600, MAXN / BLOCK_SZ) + 1];
  42.  
  43. void load_input(void)
  44. {
  45.     n = ReadInt();
  46.     q = ReadInt();
  47.     FOR(i, 1, n) a[i] = ReadInt();
  48. }
  49.  
  50. int BIT[MAXN];
  51. void add_point(int id, int val)
  52. {
  53.     for (; id > 0; id -= id & -id) BIT[id] += val;
  54. }
  55.  
  56. int sum_suffix(int id)
  57. {
  58.     int res = 0;
  59.     for (; id > 0 && id <= n; id += id & -id) res += BIT[id];
  60.     return res;
  61. }
  62.  
  63. int sub_inv_pref[MAXN], sub_inv_suff[MAXN];
  64. int cnt[min(600, MAXN / BLOCK_SZ) + 1][MAXN];
  65. pair <int, int> blk_sorted[MAXN];
  66.  
  67. void prepare(void)
  68. {
  69.     int num_block = n / BLOCK_SZ;
  70.     FOR(i, 1, n) cnt[i / BLOCK_SZ][a[i]]++;
  71.     REP(id, num_block + 1)
  72.     {
  73.         FOR(x, 1, n) cnt[id][x] += cnt[id][x - 1];
  74.         if (id) FOR(x, 1, n) cnt[id][x] += cnt[id - 1][x];
  75.  
  76.         int start = max(1, id * BLOCK_SZ), end = min(n, (id + 1) * BLOCK_SZ - 1);
  77.  
  78.         FOR(i, start, end) blk_sorted[i] = make_pair(a[i], i);
  79.         sort(blk_sorted + start, blk_sorted + end + 1);
  80.  
  81.         add_point(a[start], 1);
  82.         FOR(i, start + 1, end)
  83.         {
  84.             sub_inv_pref[i] = sub_inv_pref[i - 1] + sum_suffix(a[i] + 1);
  85.             add_point(a[i], 1);
  86.         }
  87.         FOR(i, start, end) add_point(a[i], -1);
  88.  
  89.         add_point(a[end], 1);
  90.         FORD(i, end - 1, start)
  91.         {
  92.             sub_inv_suff[i] = sub_inv_suff[i + 1] + end - i - sum_suffix(a[i]);
  93.             add_point(a[i], 1);
  94.         }
  95.         FOR(i, start, end) add_point(a[i], -1);
  96.     }
  97.  
  98.     REP(id, num_block + 1)
  99.     {
  100.         long long d = 0, tmp = 0;
  101.  
  102.         int start = max(1, id * BLOCK_SZ);
  103.         int cur_id = id, step = id ? 0 : 1;
  104.         FOR(i, start, n)
  105.         {
  106.             ++step;
  107.             if (step > BLOCK_SZ)
  108.             {
  109.                 step = 1;
  110.                 ++cur_id;
  111.                 tmp += sub_inv_pref[i - 1];
  112.             }
  113.  
  114.             int pre_id = cur_id - 1;
  115.  
  116.             if (id <= pre_id)
  117.                 d += (cnt[pre_id][n] - cnt[pre_id][a[i]]) - (id ? (cnt[id - 1][n] - cnt[id - 1][a[i]]) : 0);
  118.  
  119.             inv[id][cur_id] = d + tmp + sub_inv_pref[i];
  120.         }
  121.     }
  122. }
  123.  
  124. int small_arr[BLOCK_SZ * 2 + 5];
  125. int small_temp[BLOCK_SZ * 2 + 5];
  126.  
  127. long long merge_sort(int l, int r) {
  128.     if (l >= r) return 0;
  129.     int mid = l + (r - l) / 2;
  130.     long long res = merge_sort(l, mid) + merge_sort(mid + 1, r);
  131.     int i = l, j = mid + 1, k = l;
  132.     while (i <= mid && j <= r) {
  133.         if (small_arr[i] <= small_arr[j]) small_temp[k++] = small_arr[i++];
  134.         else {
  135.             small_temp[k++] = small_arr[j++];
  136.             res += (mid - i + 1);
  137.         }
  138.     }
  139.     while (i <= mid) small_temp[k++] = small_arr[i++];
  140.     while (j <= r) small_temp[k++] = small_arr[j++];
  141.     FOR(p, l, r) small_arr[p] = small_temp[p];
  142.     return res;
  143. }
  144.  
  145. int arr[BLOCK_SZ + 2];
  146. long long calc(int l, int r)
  147. {
  148.     int id_l = l / BLOCK_SZ, id_r = r / BLOCK_SZ;
  149.     if (id_r - id_l < 2)
  150.     {
  151.         int len = r - l + 1;
  152.         FOR(i, 0, len - 1) small_arr[i] = a[l + i];
  153.         return merge_sort(0, len - 1);
  154.     }
  155.  
  156.     long long res = sub_inv_suff[l] + inv[id_l + 1][id_r - 1] + sub_inv_pref[r];
  157.     int sz = 0;
  158.     FOR(i, max(l, id_r * BLOCK_SZ), min(n, (id_r + 1) * BLOCK_SZ - 1))
  159.     {
  160.         auto [val, idx] = blk_sorted[i];
  161.         if (idx > r) continue;
  162.  
  163.         arr[++sz] = val;
  164.         res += (cnt[id_r - 1][n] - cnt[id_r - 1][val]) - (cnt[id_l][n] - cnt[id_l][val]);
  165.     }
  166.  
  167.     int ptr = 1;
  168.     FOR(i, max(1, id_l * BLOCK_SZ), min((id_l + 1) * BLOCK_SZ - 1, r))    
  169.     {
  170.         auto [val, idx] = blk_sorted[i];
  171.         if (idx < l) continue;
  172.  
  173.         while (ptr <= sz && arr[ptr] < val) ++ptr;
  174.         res += ptr - 1;
  175.         res += (cnt[id_r - 1][val - 1] - cnt[id_l][val - 1]);
  176.     }
  177.  
  178.     return res;
  179. }
  180.  
  181. void process(void)
  182. {
  183.     prepare();
  184.  
  185.     // cout << calc(1, 8); exit(0);
  186.  
  187.     ostringstream oss;
  188.     long long last = 0;
  189.     while (q--)
  190.     {
  191.         int l, r; 
  192.         l = ReadInt();
  193.         r = ReadInt();
  194.         l = (last + l) % n + 1;
  195.         r = (last + r) % n + 1;
  196.         if (l > r) swap(l, r);
  197.         // cerr << l << ' ' << r << '\n';
  198.  
  199.         oss << (last = calc(l, r)) << '\n';
  200.     }
  201.     cout << oss.str();
  202. }
  203.  
  204. signed main(void)
  205. {   
  206.     int testcase = 1;
  207.     while (testcase--)
  208.     {
  209.         load_input();
  210.         process();
  211.     }
  212.  
  213.     cerr << "Done!";
  214.     return 0;
  215. }
  216.  
  217.  
  218.  
  219.  
Success #stdin #stdout #stderr 0s 7708KB
comments (?)
stdin 
9 5
4 9 3 5 6 1 7 8 2
2 3
9 7
8 4
6 3
1 1
stdout 
0
11
8
3
0
stderr 
Done!
https://ideone.com/EIJ1LY
Truy vấn nghịch đảo 3 / https://m...content-available-to-author-only...j.com/problem/503
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!