SHARE
TWEET

Segtree2k17

heimdaii Jan 29th, 2018 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 1111 * 1111;
  7. long long a[MAXN];
  8. long long mod;
  9.  
  10. unsigned s;
  11. unsigned getNext(){
  12.     s ^= (s << 13);
  13.     s ^= (s >> 17);
  14.     s ^= (s << 5);
  15.     return s;
  16. }
  17.  
  18. long long addMod(long long a, long long b){
  19.     a += b;
  20.     if(a >= mod)
  21.         a -= mod;
  22.     return a;
  23. }
  24.  
  25.  
  26. long long mulMod(long long a, long long b){
  27.     long long res = 0;
  28.     a %= mod;
  29.     while(b){
  30.         if(b & 1LL) {
  31.             res = addMod(res, a);
  32.         }
  33.         a = addMod(a, a);
  34.         b /= 2;
  35.     }
  36.     return res;
  37. }
  38. int n, numblocks;
  39. long long t[2 * MAXN];
  40. long long BLOCK_SIZE = 1000;
  41. long long bval[1111];
  42. long long sqpre[1111][1111];
  43. long long suff[1111][1111];
  44. long long pref[1111][1111];
  45.  
  46. void build() {
  47.     for (int i = n - 1; i > 0; --i) t[i] =  mulMod( t[i << 1], t[i << 1 | 1]);
  48. }
  49.  
  50. void sqrtbuild() {
  51.     numblocks = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
  52.     for (int i = 0; i < numblocks; i++) bval[i] = 1;
  53.     for(int i = 0; i < numblocks; i++)
  54.         for(int j= 0; j < numblocks; j++)
  55.             suff[i][j] = sqpre[i][j] = pref[i][j] = 1;
  56.            
  57.     for (int i = 0; i < n; i++) {
  58.         bval[i / BLOCK_SIZE] = mulMod(bval[i / BLOCK_SIZE], t[i + n]);
  59.     }
  60.     for (int blockind = 0; blockind < numblocks; blockind++) {
  61.         for (int i = 0; i < BLOCK_SIZE; i++) {
  62.             int ind = blockind * BLOCK_SIZE + i;
  63.             if (ind >= n) continue;
  64.             pref[blockind][i] = t[ind + n];
  65.             if (i > 0)
  66.                 pref[blockind][i] = mulMod(pref[blockind][i], pref[blockind][i - 1]);
  67.         }
  68.         for (int i = BLOCK_SIZE - 1; i >= 0; i--) {
  69.             int ind = blockind * BLOCK_SIZE + i;
  70.             if (ind >= n) continue;
  71.             suff[blockind][i] = t[ind + n];
  72.             if (i != BLOCK_SIZE - 1)
  73.                 suff[blockind][i] = mulMod( suff[blockind][i], suff[blockind][i + 1]);
  74.         }
  75.     }
  76.     for (int i = 0; i < numblocks; i++) {
  77.         sqpre[i][i] = bval[i];
  78.         for (int j = i + 1; j < numblocks; j++) {
  79.             sqpre[i][j] = mulMod(sqpre[i][j - 1], bval[j]);
  80.         }
  81.     }
  82. }
  83.  
  84.  
  85. inline long long segment_tree_query(int l, int r) {
  86.     r++;
  87.     long long res = 1;
  88.     for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  89.         if (l & 1) res = mulMod(res, t[l++]);
  90.         if (r & 1) res = mulMod(res, t[--r]);
  91.     }
  92.     return res;
  93. }
  94.  
  95. inline long long query(int l, int r) {
  96.     int leftq = l / BLOCK_SIZE, rightq = r / BLOCK_SIZE;
  97.     if (leftq == rightq) {
  98.         return segment_tree_query(l, r);
  99.     }
  100.     long long ans = 1;
  101.     ans = suff[leftq][l % BLOCK_SIZE];
  102.     ans = mulMod(ans, pref[rightq][r % BLOCK_SIZE]);
  103.     if (leftq + 1 > rightq - 1)
  104.         return ans;
  105.     ans = mulMod(ans, sqpre[leftq + 1][rightq - 1]);
  106.     return ans;
  107. }
  108.  
  109.  
  110. int main() {
  111. #ifdef LOCAL
  112.     freopen("input.txt", "r", stdin);
  113.     freopen("output.txt", "w", stdout);
  114. #endif // LOCAL
  115.  
  116.     unsigned m, seed ;
  117.     cin >> n >> m >> mod >> seed;
  118.     s = seed;
  119.     for(int i = 0; i < n; i++){
  120.         a[i] = getNext();
  121.     }
  122.  
  123.     BLOCK_SIZE = sqrt(n) + 2;
  124.     for (int i = 0; i < 2 * MAXN; i++) t[i] = 1;
  125.     for (int i = 0; i < n; i++) t[i + n] = a[i];
  126.     build();
  127.     sqrtbuild();
  128.  
  129.  
  130.     long long ans = 0;
  131.     unsigned left = 0;
  132.     unsigned right = 0;
  133.     for(int i = 0; i < m; i++){
  134.         left = getNext() % n;
  135.         right = getNext() % n;
  136.         if(left > right) swap(left, right);
  137.  
  138.         long long result = query(left, right) % mod;
  139.         ans = (ans + result) % mod;
  140.     }
  141.  
  142.     cout << ans;
  143.  
  144.     return 0;
  145. }
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