SHARE
TWEET

TWOARR Tester

a guest Feb 17th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> pii;
  7.  
  8. #define F first
  9. #define S second
  10.  
  11. const int MAXN = 2e5 + 10;
  12. const int XX = 2e5 * 20 * 10;
  13.  
  14. int n, A[MAXN], B[MAXN], q;
  15. int root[XX], tl[XX], tr[XX], sz;
  16. ll smPers[XX], sm[MAXN<<2];
  17.  
  18. int plantPers(int b, int e){
  19.     int id = sz++;
  20.     if (e - b == 1){
  21.         smPers[id] = B[b];
  22.         return id;
  23.     }
  24.    
  25.     int mid = b+e>>1;
  26.     tl[id] = plantPers(b, mid);
  27.     tr[id] = plantPers(mid, e);
  28.     smPers[id] = smPers[tl[id]] + smPers[tr[id]];
  29.     return id;
  30. }
  31.  
  32. int updPers(int id, int b, int e, int pos, int val){
  33.     int newId = sz++;
  34.     if (e - b == 1){
  35.         smPers[newId] = val;
  36.         return newId;
  37.     }
  38.  
  39.     int mid = b + e >> 1;
  40.     tl[newId] = tl[id];
  41.     tr[newId] = tr[id];
  42.     if (pos < mid)
  43.         tl[newId] = updPers(tl[newId], b, mid, pos, val);
  44.     else
  45.         tr[newId] = updPers(tr[newId], mid, e, pos, val);
  46.     smPers[newId] = smPers[tl[newId]] + smPers[tr[newId]];
  47.     return newId;
  48. }
  49.  
  50. ll getPers(int id, int b, int e, int l, int r){
  51.     if (l <= b && e <= r) return smPers[id];
  52.     if (r <= b || e <= l) return 0;
  53.  
  54.     int mid = b + e >> 1;
  55.     return getPers(tl[id], b, mid, l, r) + getPers(tr[id], mid, e, l, r);
  56. }
  57.  
  58. int lzL[MAXN<<2], lzRoot[MAXN<<2];
  59.  
  60. void plant(int v, int b, int e){
  61.     lzL[v] = -1;
  62.     if (e - b == 1){
  63.         sm[v] = A[b];
  64.         return;
  65.     }
  66.  
  67.     int mid = b + e >> 1;
  68.     plant(v<<1, b, mid);
  69.     plant(v<<1^1, mid, e);
  70.     sm[v] = sm[v<<1] + sm[v<<1^1];
  71. }
  72.  
  73. void pushDown(int v, int b, int e, int mid){
  74.     if (lzL[v] == -1) return;
  75.  
  76.     lzL[v<<1] = lzL[v];
  77.     sm[v<<1] = getPers(lzRoot[v], 0, n, lzL[v], lzL[v] + (mid - b));
  78.     lzRoot[v<<1] = lzRoot[v<<1^1] = lzRoot[v];
  79.  
  80.     lzL[v<<1^1] = lzL[v] + (mid - b);
  81.     sm[v<<1^1] = getPers(lzRoot[v], 0, n, lzL[v<<1^1], lzL[v<<1^1] + (e - mid));
  82.  
  83.     lzL[v] = -1;
  84. }
  85.  
  86. int curRoot;
  87. void upd(int v, int b, int e, int l, int r, int beg){
  88.     if (l <= b && e <= r){
  89.         beg += (b - l);
  90.         sm[v] = getPers(root[curRoot], 0, n, beg, beg + (e-b));
  91.         lzL[v] = beg;
  92.         lzRoot[v] = root[curRoot];
  93.         return;
  94.     }
  95.     if (r <= b || e <= l) return;
  96.  
  97.     int mid = b + e >> 1;
  98.     pushDown(v, b, e, mid);
  99.     upd(v<<1, b, mid, l, r, beg);
  100.     upd(v<<1^1, mid, e, l, r, beg);
  101.     sm[v] = sm[v<<1] + sm[v<<1^1];
  102. }
  103.  
  104. ll get(int v, int b, int e, int l, int r){
  105.     if (l <= b && e <= r) return sm[v];
  106.     if (r <= b || e <= l) return 0;
  107.  
  108.     int mid = b + e >> 1;
  109.     pushDown(v, b, e, mid);
  110.     return get(v<<1, b, mid, l, r) + get(v<<1^1, mid, e, l, r);
  111. }
  112.  
  113. int main(){
  114.     ios::sync_with_stdio(false);
  115.     cin.tie(0);
  116.     cin >> n >> q;
  117.     for (int i = 0; i < n; i++) cin >> A[i];
  118.     for (int i = 0; i < n; i++) cin >> B[i];
  119.  
  120.     root[0] = plantPers(0, n);
  121.     plant(1, 0, n);
  122.  
  123.     while (q--){
  124.         int tp; cin >> tp;
  125.         if (tp == 1){
  126.             int pos, val; cin >> pos >> val, pos--;
  127.             root[curRoot+1] = updPers(root[curRoot], 0, n, pos, val);
  128.             curRoot++;
  129.         }
  130.         else if (tp == 2){
  131.             int l1, r1, l2; cin >> l1 >> r1 >> l2, l1--, l2--;
  132.             upd(1, 0, n, l1, r1, l2);
  133.         }
  134.         else{
  135.             int l, r; cin >> l >> r, l--;
  136.             cout << get(1, 0, n, l, r) << "\n";
  137.         }
  138.     }
  139.     return 0;
  140. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top