fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define bint __int128
  7. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  8.  
  9. struct waveletTree {
  10.     int lo, hi;
  11.     waveletTree *L, *R;
  12.     int *compare, *prefix, compareSize, prefixSize;
  13.  
  14.     waveletTree() {
  15.         L = R = NULL;
  16.         lo = 1, hi = 0, compareSize = prefixSize = 0;
  17.     }
  18.  
  19.     void init(int *from, int *to, int MIN, int MAX) {
  20.         lo = MIN, hi = MAX;
  21.         if (from >= to) return;
  22.         int mid = (lo + hi) >> 1;
  23.         auto f = [mid](int x) { return x <= mid; };
  24.         compare = new int[to - from + 2], compareSize = 0, compare[compareSize++] = 0;
  25.         prefix = new int[to - from + 2], prefixSize = 0, prefix[prefixSize++] = 0;
  26.         for (auto it = from; it != to; it++) {
  27.             compare[compareSize] = ( compare[compareSize - 1] + f(*it) ), ++compareSize;
  28.             prefix[prefixSize] = ( prefix[prefixSize - 1] + (*it) ), ++prefixSize;
  29.         }
  30.         if (hi == lo) return;
  31.         auto pivot = stable_partition(from, to, f);
  32.         L = new waveletTree(), L->init(from, pivot, lo, mid);
  33.         R = new waveletTree(), R->init(pivot, to, mid + 1, hi);
  34.     }
  35.  
  36.     int kth(int l, int r, int k) {
  37.         if (l > r) return 0;
  38.         if (lo == hi) return lo;
  39.         int inLeft = compare[r] - compare[l - 1], lc = compare[l - 1], rc = compare[r];
  40.         if (k <= inLeft) return this->L->kth(lc + 1, rc, k);
  41.         return this->R->kth(l - lc, r - rc, k - inLeft);
  42.     }
  43.  
  44.     ~waveletTree() { delete L; delete R; }
  45. };
  46.  
  47. struct suffixArray {
  48.     int n;
  49.     vector<int> kthSuffix, lcp, orderOf;
  50.  
  51.     void build(string& s, int limit = 256) {
  52.         n = s.size() + 1; int k = 0, a, b;
  53.         vector<int> c( s.begin(), s.end() + 1 ), t(n), freq( max(n, limit) );
  54.         c.back() = 0, kthSuffix = lcp = orderOf = t, iota( kthSuffix.begin(), kthSuffix.end(), 0 );
  55.  
  56.         for (int p = 0, j = 0; p < n; j = max(1LL, j * 2), limit = p) {
  57.             p = j;
  58.             iota( t.begin(), t.end(), n - j );
  59.             fill( freq.begin(), freq.end(), 0 );
  60.  
  61.             for (int i = 0; i < n; ++i)
  62.                 if (kthSuffix[i] >= j) t[p++] = kthSuffix[i] - j;
  63.  
  64.             for (int i = 0; i < n; ++i) ++freq[ c[i] ];
  65.             for (int i = 1; i < limit; ++i) freq[i] += freq[i - 1];
  66.             for (int i = n; i--;) kthSuffix[ --freq[ c[ t[i] ] ] ] = t[i];
  67.  
  68.             swap(c, t), p = 1, c[ kthSuffix[0] ] = 0;
  69.             for (int i = 1; i < n; ++i) {
  70.                 a = kthSuffix[i - 1], b = kthSuffix[i];
  71.                 c[b] = (t[a] == t[b] and t[a + j] == t[b + j]) ? (p - 1) : (p++);
  72.             }
  73.         }
  74.  
  75.         for (int i = 1; i < n; ++i)
  76.             orderOf[ kthSuffix[i] ] = i;
  77.  
  78.         for (int i = 0, j; i < n - 1; lcp[ orderOf[i++] ] = k)
  79.             for (k and k--, j = kthSuffix[ orderOf[i] - 1 ]; s[i + k] == s[j + k]; k++) {}
  80.     }
  81. };
  82.  
  83. const int N = 200'000, LIMIT = 1000'000'000'000'000;
  84.  
  85. int g[N];
  86.  
  87. void getShitDone() {
  88.     int n;
  89.     cin >> n;
  90.  
  91.     string s;
  92.     cin >> s;
  93.  
  94.     reverse( s.begin(), s.end() );
  95.     suffixArray sf; sf.build(s);
  96.  
  97.     vector<int> a(n);
  98.     for (int i = 0; i < n; ++i) cin >> a[i];
  99.     reverse( a.begin(), a.end() );
  100.     for (int i = n - 2; i >= 0; --i) a[i] += a[i + 1];
  101.  
  102.     for (int i = 0; i < n; ++i) {
  103.         g[i] = -a[ sf.kthSuffix[i + 1] ];
  104.     }
  105.  
  106.     waveletTree solve;
  107.     solve.init( g, g + n, -LIMIT, LIMIT );
  108.  
  109.     vector<int> forward(n), back(n);
  110.     for (int i = 1; i <= n; ++i) {
  111.         if ( sf.lcp[i + 1] == n - sf.kthSuffix[i] ) {
  112.             forward[i - 1] = 1;
  113.         }
  114.         if ( sf.lcp[i] == n - sf.kthSuffix[i] ) {
  115.             back[i - 1] = 1;
  116.         }
  117.     }
  118.  
  119.     vector<int> l(n);
  120.     for (int i = 0, last = 0; i < n; ++i) {
  121.         l[i] = last;
  122.         if (forward[i] == 0) last = i + 1;
  123.     }
  124.     vector<int> r(n);
  125.     for (int i = n - 1, last = n - 1; i >= 0; --i) {
  126.         r[i] = last;
  127.         if (back[i] == 0) last = i - 1;
  128.     }
  129.  
  130.     int q;
  131.     cin >> q;
  132.  
  133.     int ans = 0;
  134.     while (q--) {
  135.         int x, y;
  136.         cin >> x >> y;
  137.  
  138.         int i = (x % n + ans % n + n) % n;
  139.         int k = (y % n + ans % n + n) % n + 1;
  140.         int p = sf.orderOf[n - 1 - i] - 1;
  141.  
  142.         if (k > r[p] - l[p] + 1) {
  143.             ans = 0;
  144.         } else {
  145.             ans = -solve.kth(l[p] + 1, r[p] + 1, k);
  146.         }
  147.  
  148.         cout << ans << '\n';
  149.     }
  150. }
  151.  
  152. signed main() {
  153.     _3bkarm
  154.  
  155.     int ts = 1;
  156. //    cin >> ts;
  157.     while (ts--) {
  158.         getShitDone();
  159.         if (ts != 0) cout << '\n';
  160.     }
  161.  
  162.     return 0;
  163. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rfWZK9
language:
C++ (gcc 8.3)
created:
6 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!