SHARE
TWEET

CodeForces_sqrtTree

heimdaii Jan 29th, 2018 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. long long mod;
  8.  
  9. typedef long long ll;
  10.  
  11. long long addMod(long long a, long long b){
  12.     a += b;
  13.     if(a >= mod)
  14.         a -= mod;
  15.     return a;
  16. }
  17.  
  18. long long op(long long a, long long b){
  19.     long long res = 0;
  20.     a %= mod;
  21.     while(b){
  22.         if(b & 1LL) {
  23.             res = addMod(res, a);
  24.         }
  25.         a = addMod(a, a);
  26.         b /= 2;
  27.     }
  28.     return res;
  29. }
  30. inline int log2Up(int n) {
  31.     int res = 0;
  32.     while ((1 << res) < n) {
  33.         res++;
  34.     }
  35.     return res;
  36. }
  37.  
  38. class SqrtTree {
  39.     private:
  40.         int n, lg;
  41.         vector<long long> v;
  42.         vector<int> clz;
  43.         vector<int> layers;
  44.         vector<int> onLayer;
  45.         vector< vector<long long> > pref;
  46.         vector< vector<long long> > suf;
  47.         vector< vector<long long> > between;
  48.        
  49.         void build(int layer, int lBound, int rBound) {
  50.             if (layer >= (int)layers.size()) {
  51.                 return;
  52.             }
  53.             int bSzLog = (layers[layer]+1) >> 1;
  54.             int bCntLog = layers[layer] >> 1;
  55.             int bSz = 1 << bSzLog;
  56.             int bCnt = 0;
  57.             for (int l = lBound; l < rBound; l += bSz) {
  58.                 bCnt++;
  59.                 int r = min(l + bSz, rBound);
  60.                 pref[layer][l] = v[l];
  61.                 for (int i = l+1; i < r; i++) {
  62.                     pref[layer][i] = op(pref[layer][i-1], v[i]);
  63.                 }
  64.                 suf[layer][r-1] = v[r-1];
  65.                 for (int i = r-2; i >= l; i--) {
  66.                     suf[layer][i] = op(v[i], suf[layer][i+1]);
  67.                 }
  68.                 build(layer+1, l, r);
  69.             }
  70.             for (int i = 0; i < bCnt; i++) {
  71.                 long long ans = 0;
  72.                 for (int j = i; j < bCnt; j++) {
  73.                     long long add = suf[layer][lBound + (j << bSzLog)];
  74.                     ans = (i == j) ? add : op(ans, add);
  75.                     between[layer][lBound + (i << bCntLog) + j] = ans;
  76.                 }
  77.             }
  78.         }
  79.     public:
  80.         inline long long query(int l, int r) {
  81.             if (l == r) {
  82.                 return v[l];
  83.             }
  84.             if (l + 1 == r) {
  85.                 return op(v[l], v[r]);
  86.             }
  87.             int layer = onLayer[clz[l ^ r]];
  88.             int bSzLog = (layers[layer]+1) >> 1;
  89.             int bCntLog = layers[layer] >> 1;
  90.             int lBound = (l >> layers[layer]) << layers[layer];
  91.             int lBlock = ((l - lBound) >> bSzLog) + 1;
  92.             int rBlock = ((r - lBound) >> bSzLog) - 1;
  93.             long long ans = suf[layer][l];
  94.             if (lBlock <= rBlock) {
  95.                 ans = op(ans, between[layer][lBound + (lBlock << bCntLog) + rBlock]);
  96.             }
  97.             ans = op(ans, pref[layer][r]);
  98.             return ans;
  99.         }
  100.        
  101.         SqrtTree(const vector<long long>& v)
  102.             : n((int)v.size()), lg(log2Up(n)), v(v), clz(1 << lg), onLayer(lg+1) {
  103.             clz[0] = 0;
  104.             for (int i = 1; i < (int)clz.size(); i++) {
  105.                 clz[i] = clz[i >> 1] + 1;
  106.             }
  107.             int tlg = lg;
  108.             while (tlg > 1) {
  109.                 onLayer[tlg] = (int)layers.size();
  110.                 layers.push_back(tlg);
  111.                 tlg = (tlg+1) >> 1;
  112.             }
  113.             for (int i = lg-1; i >= 0; i--) {
  114.                 onLayer[i] = max(onLayer[i], onLayer[i+1]);
  115.             }
  116.             pref.assign(layers.size(), vector<long long>(n));
  117.             suf.assign(layers.size(), vector<long long>(n));
  118.             between.assign(layers.size(), vector<long long>((int)(1 << lg)));
  119.             build(0, 0, n);
  120.         }
  121. };
  122.  
  123.  
  124.  
  125.  
  126. unsigned s;
  127. unsigned getNext(){
  128.     s ^= (s << 13);
  129.     s ^= (s >> 17);
  130.     s ^= (s << 5);
  131.     return s;
  132. }
  133.  
  134.  
  135.  
  136.  
  137. int n;
  138.  
  139.  
  140.  
  141.  
  142. int main() {
  143. #ifdef LOCAL
  144.     freopen("input.txt", "r", stdin);
  145.     freopen("output.txt", "w", stdout);
  146. #endif // LOCAL
  147.  
  148.     unsigned m, seed ;
  149.     cin >> n >> m >> mod >> seed;
  150.     s = seed;
  151.     vector<ll> a(n);
  152.     for(int i = 0; i < n; i++){
  153.         a[i] = getNext();
  154.     }
  155.  
  156.     SqrtTree st = SqrtTree(a);
  157.  
  158.  
  159.     long long ans = 0;
  160.     unsigned left = 0;
  161.     unsigned right = 0;
  162.     for(unsigned i = 0; i < m; i++){
  163.         left = getNext() % n;
  164.         right = getNext() % n;
  165.         if(left > right) swap(left, right);
  166.  
  167.         long long result = st.query(left, right) % mod;
  168.         ans = (ans + result) % mod;
  169.     }
  170.  
  171.     cout << ans;
  172.  
  173.     return 0;
  174. }
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