### arham_doshi's blog

By arham_doshi, history, 4 weeks ago, ,

need help in this question. question ask you to implement two types of lazy trees one for update and one for sum. I did all I could but i am unable to find the bug. please help me .

my code
test case
required ans

it would also be help full if you know some blog or toutorial to solve similar problem. thanks in advance guys for helping.

• -25

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).
 » 4 weeks ago, # |   +25 So Your code contains a lot of hindi comments which makes it irritating to read You use different spacing techniques (3 spaces in main, 2 spaces in segtree). You don't add any spaces after ,,|,& et. You have weird blank lines. You have like a million debugging lines. You are using weird loop defines. ...You could have removed useless stuff and run a formatting tool on your code to make it somewhat readable. Why should total strangers help you if you can't even do that? What are you expecting by throwing this pile of ugly code at people? You even have a testcase which your code doesn't work on I think you should debug by yourself. And why is this blog at +4? I'd argue such stuff should be forbidden on cf at best.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 really sorry about it . It is nice feedback i will see it in furture. thing about debugging myself is i tried it for 2 hrs a lot of debugging but i am not getting a tiny bug. when i print the query (in which i am getting wrong ans ) after after every operation it is giving write ans. a soon as comment it again the ans is worng . it is frustrating man and the blog is my last resort.
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   +7 i tried it for 2 hrs ~~ Rookie numbers make that 5 times more~~So I skimmed through your code:Your probably should change 2*n to 4*nYou store everything as int but sum can overflow i guessSometimes add update can be stacked on top of set update and you are always stacking it into add updates 3 3 0 0 0 2 1 2 1 1 1 2 1 3 1 1 Your code prints one because in the second query you add 1 to sum lazy, which is in fact overwritten by set lazy(from query 1). Instead you should have added 1 to set lazy so the operation becomes "set to two".Keeping two lazy tags can mess with order instead I suggest storing one tag, and it's type.Here's a short implementation of this idea I am really bored#include using namespace std; const int maxn = 1<<18; using ll = long long; struct ctx {//store info about lazy updates //0 - no update //1 - set update //2 - add update int upd_type = 0; ll val = 0; }; ctx merge(ctx a, ctx b) {//we assume b happened after a and we're stacking b on top of a if(b.upd_type == 2)//in case b is add update we stack it on the previous update keeping it's type or setting it to 2 if it was 0 return {a.upd_type ? a.upd_type : 2, a.val + b.val}; return b.upd_type ? b : a;//if b is 0 we keep a, if b is 1 we overwrite the previous updates } struct node {//stores sum and lazy info ll val = 0; ctx lazy; }; node merge(node a, node b) {//empty lazy and sum = sum of children a.val += b.val; a.lazy = ctx(); return a; } node tree[4 * maxn]; void push(int v, int l, int r) { if(tree[v].lazy.upd_type == 2)//the lazy is an add update tree[v].val += tree[v].lazy.val * (r - l + 1); if(tree[v].lazy.upd_type == 1)//the lazy is a set update tree[v].val = tree[v].lazy.val * (r - l + 1); if(l != r) {//if the node has children we propagate the lazy for(auto ch : {2*v, 2*v + 1}) tree[ch].lazy = merge(tree[ch].lazy, tree[v].lazy); } tree[v].lazy = ctx();//reset the lazy } void update(int v, int l, int r, int ql, int qr, ctx u) { push(v, l, r);//pushing everywehere if(qr < l || ql > r) return;//out of range => exit if(ql <= l && r <= qr) {//completely in range put lazy tag and immediately push it so that we can update the parent tree[v].lazy = merge(tree[v].lazy, u); push(v, l, r); return; } int mid = (l + r)/2;//going further update(2*v, l, mid, ql, qr, u); update(2*v + 1, mid + 1, r, ql, qr, u); tree[v] = merge(tree[2*v], tree[2*v + 1]);//updating this node's value children are up to date because we always push } node get(int v, int l, int r, int ql, int qr) {//I find node corresponding to range instead of sum, it's more practical and is useful in harder problmes push(v, l, r);//pushing everywehere if(qr < l || ql > r) return node();//out of range return 0 sum if(ql <= l && r <= qr) return tree[v];//completely in range return this node int mid = (l + r)/2; return merge(get(2*v, l, mid, ql, qr), get(2*v + 1, mid + 1, r, ql, qr));//merge something from the left child and something from the right child } int main() { cin.tie(0)->sync_with_stdio(0); int n, q; cin >> n >> q; for(int t, i = 1; i <= n; i++) { cin >> t;//2 - update type, t - value update(1, 1, n, i, i, {2, t});//To not implement build function I interpret initial values as add updates //since we have everything set to 0 we can act like segtree is initialized with them } for(int t, l, r, x; q--;) { cin >> t; if(t < 3) { cin >> l >> r >> x;//t^3 - update type, x - value update(1, 1, n, l, r, {t^3, x});//^3 turns 2 to 1 and 1 to 2 because I use different labels for update types in my ctx class } else { cin >> l >> r; cout << get(1, 1, n, l, r).val << '\n'; } } return 0; } 
•  » » » » 4 weeks ago, # ^ |   0 thank you so much kostia . i it worked . i learned alot from you code. it was superb.
 » 4 weeks ago, # |   +1 It's quite hard to understand your code...So if you want then can look at my code.My approach is quite lengthy , so unable to explain it here. Code#include #define inp 200005 #define check exit(0) #define nl cout< v(inp); ll l,r,t,change; vector st(inp<<2,0); vector> lazy(inp<<2); void build(int si=1,int ss=1,int se=n) { if(ss==se) { st[si]=v[ss]; return; } int mid=(ss+se)/2; build(si*2,ss,mid); build(si*2+1,mid+1,se); st[si]=st[2*si]+st[2*si+1]; } void propogate(int si,int ss,int se) { int tot=se-ss+1; auto p = lazy[si]; lazy[si]={0,0}; if(p.first == 1) { st[si]+=tot*p.second; } else { st[si]=tot*p.second; } if(ss==se) return; if(p.first == 1) { int lc=si*2,rc=si*2+1; if(lazy[lc].first!=0) { lazy[lc]={lazy[lc].first , lazy[lc].second + p.second}; } else { lazy[lc] = p; } if(lazy[rc].first!=0) { lazy[rc]={lazy[rc].first , lazy[rc].second + p.second}; } else { lazy[rc] = p; } } else { int lc=si*2,rc=si*2+1; lazy[lc] = p; lazy[rc] = p; } } void update(int si=1,int ss=1,int se=n) { if( lazy[si].first!=0 ) { propogate(si,ss,se); } if(ss>r || se=l && se<=r) { if(t==1) { lazy[si]={1,change}; } else { lazy[si]={2,change}; } propogate(si,ss,se); return; } int mid=(ss+se)/2; update(si*2,ss,mid); update(si*2+1,mid+1,se); st[si]=st[2*si]+st[2*si+1]; } ll query(int si=1,int ss=1,int se=n) { if (lazy[si].first != 0 ) { propogate(si,ss,se); } if(ss>r || se=l && se<=r) return st[si]; int mid=(ss+se)/2; return ( query(si*2,ss,mid) + query(si*2+1,mid+1,se) ); } int main() { jaldi int q; cin>>n>>q; for(int i=1;i<=n;i++) { cin>>v[i]; } build(); while(q--) { cin>>t; if(t==1 || t==2) { cin>>l>>r>>change; update(); } else { cin>>l>>r; cout<
•  » » 4 weeks ago, # ^ |   0 thanks for the help bro . i will do it like you lets see
•  » » » 4 weeks ago, # ^ |   0 Glad it helped :)
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).