fork download 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "icebear"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 1e5 + 5;
  38. const int S = 200;
  39. int n, q, a[N], cnt[N], ft[N];
  40. ll pref[N / S + 5][N];
  41.  
  42. void update(int x, int val) {
  43.     assert(x > 0);
  44.     for(; x <= n; x += x & -x) ft[x] += val;
  45. }
  46.  
  47. int get(int x) {
  48.     int ans = 0;
  49.     for(; x; x -= x & -x) ans += ft[x];
  50.     return ans;
  51. }
  52.  
  53. void init(void) {
  54.     cin >> n >> q;
  55.     REP(i, n) cin >> a[i];
  56. }
  57.  
  58. void process(void) {
  59.     for(int B = 0; B < n; B += S) {
  60.         FOR(i, B, min(n, B + S) - 1)
  61.             cnt[a[i]]++;
  62.         FOR(i, 1, n) cnt[i] += cnt[i - 1];
  63.         FOR(i, 0, B - 1) pref[B / S][i] = cnt[a[i] - 1];
  64.         FOR(i, B + S, n - 1) pref[B / S][i] = cnt[n] - cnt[a[i]];
  65.         FOR(i, B, min(n, B + S) - 1) {
  66.             FOR(j, B, i - 1) {
  67.                 if (a[j] > a[i]) pref[B / S][i]++;
  68.             }
  69.         }
  70.  
  71.         FOR(i, 1, n - 1) pref[B / S][i] += pref[B / S][i - 1];
  72.         FOR(i, B, min(n, B + S) - 1) cnt[a[i]] = 0;
  73.     }
  74.  
  75.     int l, r;
  76.     ll last_ans = 0;
  77.     while(q--) {
  78.         cin >> l >> r;
  79.         l = (l + last_ans) % n;
  80.         r = (r + last_ans) % n;
  81.         if (l > r) swap(l, r);
  82.  
  83.         ll ans = 0;
  84.         int blockL = (l + S - 1) / S;
  85.         int blockR = r / S;
  86.  
  87.         if (blockL >= blockR) {
  88.             FORR(i, r, l) {
  89.                 ans += get(a[i] - 1);
  90.                 update(a[i], +1);
  91.             }
  92.             cout << (last_ans = ans) << '\n';
  93.             FORR(i, r, l) update(a[i], -1);
  94.             continue;
  95.         }
  96.         FOR(i, blockL, blockR - 1) ans += pref[i][r] - (l == 0 ? 0 : pref[i][l - 1]);
  97.         FORR(i, r, blockR * S) {
  98.             update(a[i], +1);
  99.             ans += get(a[i] - 1);
  100.         }
  101.         FORR(i, blockL * S - 1, l) {
  102.             update(a[i], +1);
  103.             ans += get(a[i] - 1);
  104.         }
  105.         cout << (last_ans = ans) << '\n';
  106.  
  107.         FOR(i, l, blockL * S - 1) update(a[i], -1);
  108.         FOR(i, blockR * S, r) update(a[i], -1);
  109.     }
  110. }
  111.  
  112. int main() {
  113.     ios_base::sync_with_stdio(0);
  114.     cin.tie(0); cout.tie(0);
  115.     if (fopen(task".inp", "r")) {
  116.         freopen(task".inp", "r", stdin);
  117.         freopen(task".out", "w", stdout);
  118.     }
  119.     int tc = 1;
  120. //     cin >> tc;
  121.     while(tc--) {
  122.         init();
  123.         process();
  124.     }
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/92wCgT
language:
C++14 (gcc 8.3)
created:
2 days 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!