/* RANGE ASSIGNMENT + RANGE SUM QUERIES + ITERATIVE */
using namespace std;
#include <bits/stdc++.h>
struct SegLzy{
typedef long long ll;
#define _ j*2
#define __ j*2+1
vector<ll> S,L; int n,h;
SegLzy(vector<int> ar){
n=ar.size(); h=32-__builtin_clz(n);
S.assign(2*n,0); L.assign(n,0);
for(int i=0;i<n;i++)S[n+i]=ar[i];
for(int j=n-1;j>0;j--)S[j]=S[_]+S[__];
}
inline void Push(int l,int r) {
ll s=h,k=1<<(h-1);
for(l+=n,r+=n-1;s>0;--s,k/=2){
for(int j=l>>s;j<=r>>s;++j)if(L[j]){
S[_] =L[j]*k;if(_ <n)L[_] =L[j];
S[__]=L[j]*k;if(__<n)L[__]=L[j];
L[j] = 0;
}
}
}
void Updt(int l,int r,int v){
ll s=l+n,e=r-1+n,k=1,j,c;
for(l+=n,r+=n;l<r;l/=2,r/=2,k*=2) {
if(l&1){S[l]=v*k;if(l<n)L[l]=v;l++;}
if(r&1){--r;S[r]=v*k;if(r<n)L[r]=v;}
}
j=s;c=2;while((j/=2)>0)
S[j]=(!L[j])?S[_]+S[__]:L[j]*c,c*=2;
j=e;c=2;while((j/=2)>0)
S[j]=(!L[j])?S[_]+S[__]:L[j]*c,c*=2;
}
long long Kqry(int l,int r,ll res=0){
Push(l,l+1);Push(r-1,r);
for(l+=n,r+=n;l<r;l/=2,r/=2){
if(l&1)res+=S[l++];
if(r&1)res+=S[--r];
}return res;
}
};
int main(){
vector<int> a = {1,2,3,4,5,6,7,8,9,10};
SegLzy S1(a);
cout << S1.Kqry(0,10) << endl;
S1.Updt(0,5,5);
cout << S1.Kqry(0,5) << endl;
S1.Updt(0,4,3);
cout << S1.Kqry(0,5) << endl;
}
//------------------------------------------------------------------------------
// struct SegLzy{
// vector<int> S,L; ll n,h;
// SegLzy(vector<int> ar){
// n=ar.size(); h=32-__builtin_clz(n);
// S.assign(2*n,0); L.assign(n,0);
// for(int i=0;i<n;i++)S[n+i]=ar[i];
// for(int j=n-1;j>0;j--)S[j]=S[2*j]+S[2*j+1];
// }
// void calc(int p, int k) {
// if (L[p] == 0) S[p] = S[p<<1] + S[p<<1|1];
// else S[p] = L[p] * k;
// }
// void apply(int p, int value, int k) {
// S[p] = value * k;
// if (p < n) L[p] = value;
// }
// void build(int l, int r) {
// int k = 2;
// for (l += n, r += n-1; l > 1; k <<= 1) {
// l >>= 1, r >>= 1;
// for (int i = r; i >= l; --i) calc(i, k);
// }
// }
// void push(int l, int r) {
// int s = h, k = 1 << (h-1);
// for (l += n, r += n-1; s > 0; --s, k >>= 1)
// for (int i = l >> s; i <= r >> s; ++i) if (L[i] != 0) {
// apply(i<<1, L[i], k);
// apply(i<<1|1, L[i], k);
// L[i] = 0;
// }
// }
// void modify(int l, int r, int value) {
// if (value == 0) return;
// push(l, l + 1);
// push(r - 1, r);
// int l0 = l, r0 = r, k = 1;
// for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) {
// if (l&1) apply(l++, value, k);
// if (r&1) apply(--r, value, k);
// }
// build(l0, l0 + 1);
// build(r0 - 1, r0);
// }
// int query(int l, int r) {
// push(l, l + 1);
// push(r - 1, r);
// int res = 0;
// for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
// if (l&1) res += S[l++];
// if (r&1) res += S[--r];
// }
// return res;
// }
// };
// int main(){
// vector<int> a = {1,2,3,4,5,6,7,8,9,10};
// SegLzy S1(a);
// cout << S1.query(0,10) << endl;
// S1.modify(0,5,5);
// cout << S1.query(0,5) << endl;
// S1.modify(0,4,3);
// cout << S1.query(0,5) << endl;
// }
CgkJCQkvKiBSQU5HRSBBU1NJR05NRU5UICsgUkFOR0UgU1VNIFFVRVJJRVMgKyBJVEVSQVRJVkUgKi8KCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KCnN0cnVjdCBTZWdMenl7CiAgICB0eXBlZGVmIGxvbmcgbG9uZyBsbDsKICAgICNkZWZpbmUgXyAgaioyCiAgICAjZGVmaW5lIF9fIGoqMisxCgogICAgdmVjdG9yPGxsPiBTLEw7IGludCBuLGg7CgogICAgU2VnTHp5KHZlY3RvcjxpbnQ+IGFyKXsKICAgICAgICBuPWFyLnNpemUoKTsgaD0zMi1fX2J1aWx0aW5fY2x6KG4pOwogICAgICAgIFMuYXNzaWduKDIqbiwwKTsgTC5hc3NpZ24obiwwKTsKICAgICAgICBmb3IoaW50IGk9MDtpPG47aSsrKVNbbitpXT1hcltpXTsKICAgICAgICBmb3IoaW50IGo9bi0xO2o+MDtqLS0pU1tqXT1TW19dK1NbX19dOyAgCiAgICB9CiAgICBpbmxpbmUgdm9pZCBQdXNoKGludCBsLGludCByKSB7CiAgICAgICAgbGwgcz1oLGs9MTw8KGgtMSk7CiAgICAgICAgZm9yKGwrPW4scis9bi0xO3M+MDstLXMsay89Mil7CiAgICAgICAgICAgIGZvcihpbnQgaj1sPj5zO2o8PXI+PnM7KytqKWlmKExbal0pewogICAgICAgICAgICAgICAgU1tfXSA9TFtqXSprO2lmKF8gPG4pTFtfXSA9TFtqXTsKICAgICAgICAgICAgICAgIFNbX19dPUxbal0qaztpZihfXzxuKUxbX19dPUxbal07CiAgICAgICAgICAgICAgICBMW2pdID0gMDsKICAgICAgICAgICAgfQogICAgICAgIH0gICAgICAKICAgIH0KICAgIHZvaWQgVXBkdChpbnQgbCxpbnQgcixpbnQgdil7CiAgICAgICAgbGwgcz1sK24sZT1yLTErbixrPTEsaixjOwogICAgICAgIGZvcihsKz1uLHIrPW47bDxyO2wvPTIsci89MixrKj0yKSB7CiAgICAgICAgICAgIGlmKGwmMSl7U1tsXT12Kms7aWYobDxuKUxbbF09djtsKys7fQogICAgICAgICAgICBpZihyJjEpey0tcjtTW3JdPXYqaztpZihyPG4pTFtyXT12O30KICAgICAgICB9CiAgICAgICAgaj1zO2M9Mjt3aGlsZSgoai89Mik+MCkKICAgICAgICBTW2pdPSghTFtqXSk/U1tfXStTW19fXTpMW2pdKmMsYyo9MjsKICAgICAgICBqPWU7Yz0yO3doaWxlKChqLz0yKT4wKQogICAgICAgIFNbal09KCFMW2pdKT9TW19dK1NbX19dOkxbal0qYyxjKj0yOwogICAgfQogICAgbG9uZyBsb25nIEtxcnkoaW50IGwsaW50IHIsbGwgcmVzPTApewogICAgICAgIFB1c2gobCxsKzEpO1B1c2goci0xLHIpOwogICAgICAgIGZvcihsKz1uLHIrPW47bDxyO2wvPTIsci89Mil7CiAgICAgICAgICAgIGlmKGwmMSlyZXMrPVNbbCsrXTsKICAgICAgICAgICAgaWYociYxKXJlcys9U1stLXJdOwogICAgICAgIH1yZXR1cm4gcmVzOwogICAgfQp9OwoKaW50IG1haW4oKXsKICAgIHZlY3RvcjxpbnQ+IGEgPSB7MSwyLDMsNCw1LDYsNyw4LDksMTB9OwogICAgU2VnTHp5IFMxKGEpOwogICAgY291dCA8PCBTMS5LcXJ5KDAsMTApIDw8IGVuZGw7CiAgICBTMS5VcGR0KDAsNSw1KTsKICAgIGNvdXQgPDwgUzEuS3FyeSgwLDUpIDw8IGVuZGw7CiAgICBTMS5VcGR0KDAsNCwzKTsKICAgIGNvdXQgPDwgUzEuS3FyeSgwLDUpIDw8IGVuZGw7Cn0KCi8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCi8vIHN0cnVjdCBTZWdMenl7CiAgICAKLy8gICAgIHZlY3RvcjxpbnQ+IFMsTDsgbGwgbixoOwoKLy8gICAgIFNlZ0x6eSh2ZWN0b3I8aW50PiBhcil7Ci8vICAgICAgICAgbj1hci5zaXplKCk7IGg9MzItX19idWlsdGluX2NseihuKTsKLy8gICAgICAgICBTLmFzc2lnbigyKm4sMCk7IEwuYXNzaWduKG4sMCk7Ci8vICAgICAgICAgZm9yKGludCBpPTA7aTxuO2krKylTW24raV09YXJbaV07Ci8vICAgICAgICAgZm9yKGludCBqPW4tMTtqPjA7ai0tKVNbal09U1syKmpdK1NbMipqKzFdOyAgCi8vICAgICB9CgovLyAgICAgdm9pZCBjYWxjKGludCBwLCBpbnQgaykgewovLyAgICAgICAgIGlmIChMW3BdID09IDApIFNbcF0gPSBTW3A8PDFdICsgU1twPDwxfDFdOwovLyAgICAgICAgIGVsc2UgU1twXSA9IExbcF0gKiBrOwovLyAgICAgfQoKLy8gICAgIHZvaWQgYXBwbHkoaW50IHAsIGludCB2YWx1ZSwgaW50IGspIHsKLy8gICAgICAgICBTW3BdID0gdmFsdWUgKiBrOwovLyAgICAgICAgIGlmIChwIDwgbikgTFtwXSA9IHZhbHVlOwovLyAgICAgfQoKLy8gICAgIHZvaWQgYnVpbGQoaW50IGwsIGludCByKSB7Ci8vICAgICAgICAgaW50IGsgPSAyOwovLyAgICAgICAgIGZvciAobCArPSBuLCByICs9IG4tMTsgbCA+IDE7IGsgPDw9IDEpIHsKLy8gICAgICAgICAgICAgbCA+Pj0gMSwgciA+Pj0gMTsKLy8gICAgICAgICAgICAgZm9yIChpbnQgaSA9IHI7IGkgPj0gbDsgLS1pKSBjYWxjKGksIGspOwovLyAgICAgICAgIH0KLy8gICAgIH0KCi8vICAgICB2b2lkIHB1c2goaW50IGwsIGludCByKSB7Ci8vICAgICAgICAgaW50IHMgPSBoLCBrID0gMSA8PCAoaC0xKTsKLy8gICAgICAgICBmb3IgKGwgKz0gbiwgciArPSBuLTE7IHMgPiAwOyAtLXMsIGsgPj49IDEpCi8vICAgICAgICAgICAgIGZvciAoaW50IGkgPSBsID4+IHM7IGkgPD0gciA+PiBzOyArK2kpIGlmIChMW2ldICE9IDApIHsKLy8gICAgICAgICAgICAgICAgIGFwcGx5KGk8PDEsIExbaV0sIGspOwovLyAgICAgICAgICAgICAgICAgYXBwbHkoaTw8MXwxLCBMW2ldLCBrKTsKLy8gICAgICAgICAgICAgICAgIExbaV0gPSAwOwovLyAgICAgICAgICAgICB9Ci8vICAgICB9CgovLyAgICAgdm9pZCBtb2RpZnkoaW50IGwsIGludCByLCBpbnQgdmFsdWUpIHsKLy8gICAgICAgICBpZiAodmFsdWUgPT0gMCkgcmV0dXJuOwovLyAgICAgICAgIHB1c2gobCwgbCArIDEpOwovLyAgICAgICAgIHB1c2gociAtIDEsIHIpOwovLyAgICAgICAgIGludCBsMCA9IGwsIHIwID0gciwgayA9IDE7Ci8vICAgICAgICAgZm9yIChsICs9IG4sIHIgKz0gbjsgbCA8IHI7IGwgPj49IDEsIHIgPj49IDEsIGsgPDw9IDEpIHsKLy8gICAgICAgICAgICAgaWYgKGwmMSkgYXBwbHkobCsrLCB2YWx1ZSwgayk7Ci8vICAgICAgICAgICAgIGlmIChyJjEpIGFwcGx5KC0tciwgdmFsdWUsIGspOwovLyAgICAgICAgIH0KLy8gICAgICAgICBidWlsZChsMCwgbDAgKyAxKTsKLy8gICAgICAgICBidWlsZChyMCAtIDEsIHIwKTsKLy8gICAgIH0KCi8vICAgICBpbnQgcXVlcnkoaW50IGwsIGludCByKSB7Ci8vICAgICAgICAgcHVzaChsLCBsICsgMSk7Ci8vICAgICAgICAgcHVzaChyIC0gMSwgcik7Ci8vICAgICAgICAgaW50IHJlcyA9IDA7Ci8vICAgICAgICAgZm9yIChsICs9IG4sIHIgKz0gbjsgbCA8IHI7IGwgPj49IDEsIHIgPj49IDEpIHsKLy8gICAgICAgICAgICAgaWYgKGwmMSkgcmVzICs9IFNbbCsrXTsKLy8gICAgICAgICAgICAgaWYgKHImMSkgcmVzICs9IFNbLS1yXTsKLy8gICAgICAgICB9Ci8vICAgICAgICAgcmV0dXJuIHJlczsKLy8gICAgIH0KLy8gfTsKCi8vIGludCBtYWluKCl7Ci8vICAgICB2ZWN0b3I8aW50PiBhID0gezEsMiwzLDQsNSw2LDcsOCw5LDEwfTsKLy8gICAgIFNlZ0x6eSBTMShhKTsKLy8gICAgIGNvdXQgPDwgUzEucXVlcnkoMCwxMCkgPDwgZW5kbDsKLy8gICAgIFMxLm1vZGlmeSgwLDUsNSk7Ci8vICAgICBjb3V0IDw8IFMxLnF1ZXJ5KDAsNSkgPDwgZW5kbDsKLy8gICAgIFMxLm1vZGlmeSgwLDQsMyk7Ci8vICAgICBjb3V0IDw8IFMxLnF1ZXJ5KDAsNSkgPDwgZW5kbDsKLy8gfQo=