fork download
copy 
  1.  
  2. 				/* RANGE ASSIGNMENT + RANGE SUM QUERIES + ITERATIVE */
  3.  
  4.  
  5. using namespace std;
  6. #include <bits/stdc++.h>
  7.  
  8. struct SegLzy{
  9.     typedef long long ll;
  10.     #define _  j*2
  11.     #define __ j*2+1
  12.  
  13.     vector<ll> S,L; int n,h;
  14.  
  15.     SegLzy(vector<int> ar){
  16.         n=ar.size(); h=32-__builtin_clz(n);
  17.         S.assign(2*n,0); L.assign(n,0);
  18.         for(int i=0;i<n;i++)S[n+i]=ar[i];
  19.         for(int j=n-1;j>0;j--)S[j]=S[_]+S[__];  
  20.     }
  21.     inline void Push(int l,int r) {
  22.         ll s=h,k=1<<(h-1);
  23.         for(l+=n,r+=n-1;s>0;--s,k/=2){
  24.             for(int j=l>>s;j<=r>>s;++j)if(L[j]){
  25.                 S[_] =L[j]*k;if(_ <n)L[_] =L[j];
  26.                 S[__]=L[j]*k;if(__<n)L[__]=L[j];
  27.                 L[j] = 0;
  28.             }
  29.         }      
  30.     }
  31.     void Updt(int l,int r,int v){
  32.         ll s=l+n,e=r-1+n,k=1,j,c;
  33.         for(l+=n,r+=n;l<r;l/=2,r/=2,k*=2) {
  34.             if(l&1){S[l]=v*k;if(l<n)L[l]=v;l++;}
  35.             if(r&1){--r;S[r]=v*k;if(r<n)L[r]=v;}
  36.         }
  37.         j=s;c=2;while((j/=2)>0)
  38.         S[j]=(!L[j])?S[_]+S[__]:L[j]*c,c*=2;
  39.         j=e;c=2;while((j/=2)>0)
  40.         S[j]=(!L[j])?S[_]+S[__]:L[j]*c,c*=2;
  41.     }
  42.     long long Kqry(int l,int r,ll res=0){
  43.         Push(l,l+1);Push(r-1,r);
  44.         for(l+=n,r+=n;l<r;l/=2,r/=2){
  45.             if(l&1)res+=S[l++];
  46.             if(r&1)res+=S[--r];
  47.         }return res;
  48.     }
  49. };
  50.  
  51. int main(){
  52.     vector<int> a = {1,2,3,4,5,6,7,8,9,10};
  53.     SegLzy S1(a);
  54.     cout << S1.Kqry(0,10) << endl;
  55.     S1.Updt(0,5,5);
  56.     cout << S1.Kqry(0,5) << endl;
  57.     S1.Updt(0,4,3);
  58.     cout << S1.Kqry(0,5) << endl;
  59. }
  60.  
  61. //------------------------------------------------------------------------------
  62. // struct SegLzy{
  63.  
  64. //     vector<int> S,L; ll n,h;
  65.  
  66. //     SegLzy(vector<int> ar){
  67. //         n=ar.size(); h=32-__builtin_clz(n);
  68. //         S.assign(2*n,0); L.assign(n,0);
  69. //         for(int i=0;i<n;i++)S[n+i]=ar[i];
  70. //         for(int j=n-1;j>0;j--)S[j]=S[2*j]+S[2*j+1];  
  71. //     }
  72.  
  73. //     void calc(int p, int k) {
  74. //         if (L[p] == 0) S[p] = S[p<<1] + S[p<<1|1];
  75. //         else S[p] = L[p] * k;
  76. //     }
  77.  
  78. //     void apply(int p, int value, int k) {
  79. //         S[p] = value * k;
  80. //         if (p < n) L[p] = value;
  81. //     }
  82.  
  83. //     void build(int l, int r) {
  84. //         int k = 2;
  85. //         for (l += n, r += n-1; l > 1; k <<= 1) {
  86. //             l >>= 1, r >>= 1;
  87. //             for (int i = r; i >= l; --i) calc(i, k);
  88. //         }
  89. //     }
  90.  
  91. //     void push(int l, int r) {
  92. //         int s = h, k = 1 << (h-1);
  93. //         for (l += n, r += n-1; s > 0; --s, k >>= 1)
  94. //             for (int i = l >> s; i <= r >> s; ++i) if (L[i] != 0) {
  95. //                 apply(i<<1, L[i], k);
  96. //                 apply(i<<1|1, L[i], k);
  97. //                 L[i] = 0;
  98. //             }
  99. //     }
  100.  
  101. //     void modify(int l, int r, int value) {
  102. //         if (value == 0) return;
  103. //         push(l, l + 1);
  104. //         push(r - 1, r);
  105. //         int l0 = l, r0 = r, k = 1;
  106. //         for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) {
  107. //             if (l&1) apply(l++, value, k);
  108. //             if (r&1) apply(--r, value, k);
  109. //         }
  110. //         build(l0, l0 + 1);
  111. //         build(r0 - 1, r0);
  112. //     }
  113.  
  114. //     int query(int l, int r) {
  115. //         push(l, l + 1);
  116. //         push(r - 1, r);
  117. //         int res = 0;
  118. //         for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  119. //             if (l&1) res += S[l++];
  120. //             if (r&1) res += S[--r];
  121. //         }
  122. //         return res;
  123. //     }
  124. // };
  125.  
  126. // int main(){
  127. //     vector<int> a = {1,2,3,4,5,6,7,8,9,10};
  128. //     SegLzy S1(a);
  129. //     cout << S1.query(0,10) << endl;
  130. //     S1.modify(0,5,5);
  131. //     cout << S1.query(0,5) << endl;
  132. //     S1.modify(0,4,3);
  133. //     cout << S1.query(0,5) << endl;
  134. // }
  135.  
Success #stdin #stdout 0s 4480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
55
25
17
https://ideone.com/QU5gY1
RANGE ASSIGNMENT + RANGE SUM QUERIES + ITERATIVE
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!