need help in [this](https://cses.fi/problemset/task/1735/) 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 .↵
<br>↵
↵
<spoiler summary="my code">↵
↵
~~~~~↵
/*↵
“The only way that we can live is if we grow.↵
The only way we can grow is if we change. ↵
The only way we can change is if we learn.↵
The only way we can learn is if we are exposed.↵
And the only way that we are exposed is if we throw ourselves into the open.”↵
*************************************** ************************ **********************************↵
*/↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
↵
//---------------------mishra ka idea------------------↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
↵
↵
#define int long long↵
#define double long double↵
#define pb push_back↵
#define pf push_front↵
#define pii pair<int,int>↵
#define vi vector<int>↵
#define vii vector<pii>↵
#define all(a) (a).begin(),(a).end()↵
#define rall(a) (a).rbegin(),(a).rend()↵
#define x first↵
#define y second↵
#define endl '\n'↵
#define sz(x) (int)(x).size()↵
//------------------------mishra ka idea-------------------↵
↵
//-------------------------alsi hu mai-----------------------↵
#define fo(i,l,u) for(i=l;i<u;i++)↵
#define rfo(i,l,u) for(i=l;i>=u;i--)↵
#define allfo(s) for(auto it=(s).begin();it!=(s).end();it++)↵
#define _init(b) memset(b,-1,sizeof(b))↵
#define _init0(b) memset(b,0,sizeof(b))↵
#define MOD 1000000007↵
#define hell 998244353↵
#define output(x) cout << (x ? "YES" : "NO")<<endl;↵
#define Output(x) cout << (x ? "Yes" : "No")<<endl;↵
//-------------------------alsi hu mai-----------------------↵
↵
↵
↵
//--------------------het se uthaya---------------------↵
#define MOD2 (998244353)↵
#define MOD3 (1000000009)↵
#define PI acos(-1)↵
#define eps (1e-8)↵
#define INF (1e18) ↵
↵
↵
↵
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}↵
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}↵
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}↵
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}↵
ifstream cinn("in.txt");ofstream coutt("out.txt");↵
int poww(const int &a,int b,const int &m=MOD){if(b==0)return 1;int x=poww(a,b/2,m);x=x*x%m;if(b&1)x=x*a%m;return x;} ↵
↵
//--------------------het se uthaya-------------------------------------------------------------------↵
↵
↵
int gcd(int a, int b) {if(a>b)swap(a,b) ; if (a == 0) return b; return gcd(b % a, a); } ↵
bool mod(double a,double b) {return a/b - floor(a/b);}↵
↵
//---------------------------aab code dekho bahut template dekh liya---------------------------------↵
↵
↵
↵
struct segtree{↵
vi tree,laz,laz1,change1,change;↵
int n,base;↵
void began(int z){↵
int x,i;↵
n=z;↵
↵
//cout<<" tree till "<<n<<" "<<2*n<<endl;//initialise everythin with zero↵
fo(i,0,2*n+5){↵
tree.pb(0);↵
laz.pb(0);↵
laz1.pb(0);↵
change1.pb(0);↵
change.pb(0);↵
}↵
// cout<<tree.size()<<" "<<laz.size()<<endl;↵
}↵
}↵
//laz is for increment query↵
//laz1 is for update query↵
↵
void lazy_up(int p,int l,int r){↵
if(l>r)return ;↵
if(change[p]!=0){↵
// cout<<" prop>"<<l<<" "<<r<<" "<<p;↵
tree[p]+=laz[p]*(r-l+1);↵
if(l!=r){↵
//cout<<" "<<2*p<<" "<<2*p+1;↵
laz[2*p]+=laz[p];↵
laz[2*p+1]+=laz[p];↵
laz1[2*p]=0;↵
laz1[2*p+1]=0;↵
change[2*p]=1;↵
change[2*p+1]=1;↵
change1[2*p]=0;↵
change1[2*p+1]=0;↵
}↵
laz[p]=0;↵
laz1[p]=0;↵
change[p]=0;↵
change1[p]=0;↵
// cout<<endl;↵
}↵
}↵
↵
void lazy_up1(int p,int l,int r){↵
if(l>r)return ;↵
if(change1[p]!=0){↵
// cout<<" prop>"<<l<<" "<<r<<" "<<p;↵
tree[p]=laz1[p]*(r-l+1);↵
if(l!=r){↵
//cout<<" "<<2*p<<" "<<2*p+1;↵
laz1[2*p]=laz1[p];↵
laz1[2*p+1]=laz1[p];↵
laz[2*p]=0;↵
laz[2*p+1]=0;↵
change[2*p]=0;↵
change[2*p+1]=0;↵
change1[2*p]=1;↵
change1[2*p+1]=1;↵
↵
}↵
laz[p]=0;↵
laz1[p]=0;↵
change[p]=0;↵
change1[p]=0;↵
// cout<<endl;↵
}↵
}↵
↵
↵
int query(int p,int l,int r,int a,int b){↵
if(l>r)return 0;↵
lazy_up1(p,l,r , l , r );↵
lazy_up(p,l,r);↵
// cout<<" in pos "<<p<<" l,r="<<l<<" "<<r<<" val "<<tree[p]<<endl , l , r );↵
↵
if(l>=a && r<=b){↵
// cout<<"Q "<<l<<" "<<r<<" "<<tree[p]<<" "<<p<<endl;↵
return tree[p];↵
}↵
else if(r<a || l>b)return 0;↵
int mid=(l+r)/2;↵
int a1,b1;↵
// cout<<"query seg "<<l<<" "<<mid<<" "<<r<<endl;↵
a1=query(2*p ,l,mid,a, , mid , a , b);↵
b1=query(2*p+1, , mid+1,r,a,b);↵
//cout<<a1<<" "<<b1<<endl;; , r , a , b);↵
↵
tree[p]=(tree[2*p]+tree[2*p+1]);↵
return a1+b1;↵
↵
}↵
↵
void update1(int p,int l,int r,int a,int b,int val){↵
lazy_up1(p,l,r , l , r );↵
lazy_up(p,l,r , l , r );↵
↵
// cout<<p<<" "<<l<<" "<<r<<" "<<pos<<" "<<val<<endl;↵
↵
if(l>=a && r<=b){↵
tree[p]=val*(r-l+1);↵
↵
// cout<<l<<" "<<r<<" "<<tree[p]<<" "<<p<<" upd"<<endl;;↵
↵
if(l!=r){↵
laz1[2*p]=val;↵
laz1[2*p+1]=val;↵
laz[2*p]=0;↵
laz[2*p+1]=0;↵
change[2*p]=0;↵
change[2*p+1]=0;↵
change1[2*p]=1;↵
change1[2*p+1]=1;↵
}↵
↵
}↵
else if(r<a||l>b){↵
return ;↵
}↵
else{↵
int mid=(l+r)/2;↵
int a1,b1;↵
//cout<<" segments "<<l<<" "<<mid<<" "<<r<<endl;↵
update1(2*p,l,mid,a,b, , l , mid , a , b , val);↵
update1(2*p+1, , mid+1,r,a,b, , r , a , b , val);↵
tree[p]=(tree[2*p]+tree[2*p+1]);↵
//cout<<tree[2*p]<<" "<<tree[2*p+1]<<" "<<2*p<<" "<<2*p+1<<endl;↵
return ;↵
}↵
↵
}↵
↵
↵
void update(int p,int l,int r,int a,int b,int val){↵
lazy_up1(p,l,r , l , r );↵
lazy_up(p,l,r);↵
// cout<<p<<" "<<l<<" "<<r<<" "<<pos<<" "<<val<<endl; , l , r );↵
↵
↵
if(l>=a && r<=b){↵
tree[p]+=val*(r-l+1);↵
↵
// cout<<l<<" "<<r<<" "<<tree[p]<<" "<<p<<" upd"<<endl;;↵
if(l!=r){↵
laz[2*p]+=val;↵
laz[2*p+1]+=val;↵
laz1[2*p]=0;↵
laz1[2*p+1]=0;↵
change[2*p]=1;↵
change[2*p+1]=1;↵
change1[2*p]=0;↵
change1[2*p+1]=0;↵
}↵
↵
}↵
else if(r<a || l>b){↵
return ;↵
}↵
else{↵
int mid=(l+r)/2;↵
int a1,b1;↵
//cout<<" segments "<<l<<" "<<mid<<" "<<r<<endl;↵
update(2*p,l,mid,a,b, , l , mid , a , b , val);↵
update(2*p+1, , mid+1,r,a,b, , r , a , b , val);↵
tree[p]=(tree[2*p]+tree[2*p+1]);↵
//cout<<tree[2*p]<<" "<<tree[2*p+1]<<" "<<2*p<<" "<<2*p+1<<endl;↵
return ;↵
}↵
↵
}↵
↵
↵
↵
int query(int l,int r){↵
// cout<<"---->query "<<l<<" "<<r<<endl;↵
return query(1,1,n,l, , 1 , n , l , r);↵
}↵
↵
void update(int a,int b,int val){↵
// cout<<"--->update "<<p<<" "<<val<<endl;↵
//val--;↵
update(1,1,n,a,b,↵
update(1 , 1 , n , a , b , val);↵
}↵
void update1(int a,int b,int val){↵
update1(1,1,n,a,b, , 1 , n , a, b , val);↵
}↵
↵
};↵
↵
↵
↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
int i,j,x,n,m;↵
cin>>n>>m;↵
segtree tree;↵
tree.began(n);↵
fo(i,1,n+1){↵
cin>>x;↵
tree.update(i,i,x , i , x );↵
}↵
int type,a,b,c;↵
fo(i,0,m){↵
cin>>type;↵
if(type==1){↵
cin>>a>>b>>c;↵
tree.update(a,b, , b , c);↵
}↵
else if(type==2){↵
cin>>a>>b>>c;↵
tree.update1(a,b, , b , c);↵
}↵
else {↵
cin>>a>>b;↵
cout<<tree.query(a, , b)<<endl;↵
}↵
//tree.query(53,81);↵
//cout<<tree.query(22,64)<<endl<<endl;}↵
}↵
}↵
↵
↵
↵
↵
↵
return 0;↵
}↵
↵
//----------------abc tez kar liya iska matlab ye nahi tum legend ho kya pata hagdo aage ------------------↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="test case">↵
↵
~~~~~↵
↵
100 14↵
7 6 4 6 2 9 4 8 10 4 10 3 7 10 2 9 4 1 7 4 5 9 9 7 9 6 5 10 8 4 7 10 5 3 3 1 6 7 6 1 5 7 7 7 7 2 3 5 10 8 4 8 7 5 8 6 8 6 7 9 3 10 6 6 8 1 5 8 5 9 9 5 8 8 4 6 6 3 1 2 1 2 9 2 10 9 9 6 5 7 9 10 5 8 2 7 4 1 4 7↵
2 72 77 5↵
2 56 63 8↵
3 40 51↵
2 42 51 5↵
3 33 35↵
2 31 97 6↵
3 88 90↵
2 38 78 2↵
3 77 82↵
1 70 80 9↵
1 53 81 4↵
1 86 93 4↵
2 12 33 1↵
3 22 64↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="required ans">↵
↵
~~~~~↵
↵
66↵
11↵
18↵
28↵
138↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="my answer">↵
↵
~~~~~↵
↵
66↵
11↵
18↵
28↵
142↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<br> ↵
it would also be help full if you know some blog or toutorial to solve similar problem.↵
thanks in advance guys for helping.↵
<br>↵
↵
<spoiler summary="my code">↵
↵
~~~~~↵
“The only way that we can live is if we grow.↵
The only way we can grow is if we change. ↵
The only way we can change is if we learn.↵
The only way we can learn is if we are exposed.↵
And the only way that we are exposed is if we throw ourselves into the open.”↵
*************************************** ************************ **********************************↵
*/↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
↵
//---------------------mishra ka idea------------------
#include <bits/stdc++.h>↵
using namespace std;↵
↵
↵
↵
#define int long long↵
#define double long double↵
#define pb push_back↵
#define pf push_front↵
#define pii pair<int,int>↵
#define vi vector<int>↵
#define vii vector<pii>↵
#define all(a) (a).begin(),(a).end()↵
#define rall(a) (a).rbegin(),(a).rend()↵
#define x first↵
#define y second↵
#define endl '\n'↵
#define sz(x) (int)(x).size()↵
↵
//-------------------------alsi hu mai-----------------------
#define fo(i,l,u) for(i=l;i<u;i++)↵
#define rfo(i,l,u) for(i=l;i>=u;i--)↵
#define allfo(s) for(auto it=(s).begin();it!=(s).end();it++)↵
#define _init0(b) memset(b,0,sizeof(b))↵
#define MOD 1000000007↵
#define hell 998244353↵
#define output(x) cout << (x ? "YES" : "NO")<<endl;↵
#define Output(x) cout << (x ? "Yes" : "No")<<endl;↵
//-------------------------alsi hu mai-----------------------↵
↵
↵
↵
//--------------------het se uthaya---------------------↵
#define MOD2 (998244353)↵
#define MOD3 (1000000009)↵
#define PI acos(-1)↵
#define eps (1e-8)↵
#define INF (1e18) ↵
↵
↵
↵
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}↵
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}↵
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}↵
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}↵
ifstream cinn("in.txt");ofstream coutt("out.txt");↵
int poww(const int &a,int b,const int &m=MOD){if(b==0)return 1;int x=poww(a,b/2,m);x=x*x%m;if(b&1)x=x*a%m;return x;} ↵
↵
//--------------------het se uthaya-------------------------------------------------------------------↵
↵
↵
int gcd(int a, int b) {if(a>b)swap(a,b) ; if (a == 0) return b; return gcd(b % a, a); } ↵
bool mod(double a,double b) {return a/b - floor(a/b);}↵
↵
//---------------------------aab code dekho bahut template dekh liya---------------------------------↵
↵
↵
struct segtree{↵
vi tree,laz,laz1,change1,change;↵
int n,base;↵
void began(int z){↵
int x,i;↵
n=z;↵
//cout<<" tree till "<<n<<" "<<2*n<<endl;
fo(i,0,2*n+5){↵
tree.pb(0);↵
laz.pb(0);↵
laz1.pb(0);↵
change1.pb(0);↵
change.pb(0);↵
}↵
}
}↵
//laz is for increment query↵
//laz1 is for update query↵
↵
void lazy_up(int p,int l,int r){↵
if(l>r)return ;↵
if(change[p]!=0){↵
tree[p]+=laz[p]*(r-l+1);↵
if(l!=r){↵
laz[2*p]+=laz[p];↵
laz[2*p+1]+=laz[p];↵
laz1[2*p]=0;↵
laz1[2*p+1]=0;↵
change[2*p]=1;↵
change[2*p+1]=1;↵
change1[2*p]=0;↵
change1[2*p+1]=0;↵
}↵
laz[p]=0;↵
laz1[p]=0;↵
change[p]=0;↵
change1[p]=0;↵
}↵
}↵
↵
void lazy_up1(int p,int l,int r){↵
if(l>r)return ;↵
if(change1[p]!=0){↵
tree[p]=laz1[p]*(r-l+1);↵
if(l!=r){↵
laz1[2*p]=laz1[p];↵
laz1[2*p+1]=laz1[p];↵
laz[2*p]=0;↵
laz[2*p+1]=0;↵
change[2*p]=0;↵
change[2*p+1]=0;↵
change1[2*p]=1;↵
change1[2*p+1]=1;↵
↵
}↵
laz[p]=0;↵
laz1[p]=0;↵
change[p]=0;↵
change1[p]=0;↵
}↵
}↵
↵
↵
int query(int p,int l,int r,int a,int b){↵
if(l>r)return 0;↵
lazy_up1(p
lazy_up(p
// cout<<" in pos "<<p<<" l,r="<<l<<" "<<r<<" val "<<tree[p]<<endl
↵
if(l>=a && r<=b){↵
return tree[p];↵
}↵
else if(r<a || l>b)return 0;↵
int mid=(l+r)/2;↵
int a1,b1;↵
a1=query(2*p ,l
b1=query(2*p+1
//cout<<a1<<" "<<b1<<endl;;
↵
tree[p]=(tree[2*p]+tree[2*p+1]);↵
return a1+b1;↵
↵
}↵
↵
void update1(int p,int l,int r,int a,int b,int val){↵
lazy_up1(p
lazy_up(p
↵
↵
if(l>=a && r<=b){↵
tree[p]=val*(r-l+1);↵
↵
↵
if(l!=r){↵
laz1[2*p]=val;↵
laz1[2*p+1]=val;↵
laz[2*p]=0;↵
laz[2*p+1]=0;↵
change[2*p]=0;↵
change[2*p+1]=0;↵
change1[2*p]=1;↵
change1[2*p+1]=1;↵
}↵
↵
}↵
else if(r<a||l>b){↵
return ;↵
}↵
else{↵
int mid=(l+r)/2;↵
int a1,b1;↵
update1(2*p
update1(2*p+1
tree[p]=(tree[2*p]+tree[2*p+1]);↵
return ;↵
}↵
↵
}↵
↵
↵
void update(int p,int l,int r,int a,int b,int val){↵
lazy_up1(p
lazy_up(p
// cout<<p<<" "<<l<<" "<<r<<" "<<pos<<" "<<val<<endl;
↵
↵
if(l>=a && r<=b){↵
tree[p]+=val*(r-l+1);↵
↵
if(l!=r){↵
laz[2*p]+=val;↵
laz[2*p+1]+=val;↵
laz1[2*p]=0;↵
laz1[2*p+1]=0;↵
change[2*p]=1;↵
change[2*p+1]=1;↵
change1[2*p]=0;↵
change1[2*p+1]=0;↵
}↵
↵
}↵
else if(r<a || l>b){↵
return ;↵
}↵
else{↵
int mid=(l+r)/2;↵
int a1,b1;↵
update(2*p
update(2*p+1
tree[p]=(tree[2*p]+tree[2*p+1]);↵
return ;↵
}↵
↵
}↵
↵
↵
↵
int query(int l,int r){↵
return query(1
}↵
↵
void update(int a,int b,int val){↵
//val--;↵
update(1,1,n,a,b,
update(1 , 1 , n , a , b , val);↵
}↵
void update1(int a,int b,int val){↵
update1(1
}↵
↵
};↵
↵
↵
↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
int i,j,x,n,m;↵
cin>>n>>m;↵
segtree tree;↵
tree.began(n);↵
fo(i,1,n+1){↵
cin>>x;↵
tree.update(i
}↵
int type,a,b,c;↵
fo(i,0,m){↵
cin>>type;↵
if(type==1){↵
cin>>a>>b>>c;↵
tree.update(a
}↵
else if(type==2){↵
cin>>a>>b>>c;↵
tree.update1(a
}↵
else {↵
cin>>a>>b;↵
cout<<tree.query(a
//cout<<tree.query(22,64)<<endl<<endl;
}↵
↵
↵
↵
↵
return 0;↵
}↵
↵
↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="test case">↵
↵
~~~~~↵
↵
100 14↵
7 6 4 6 2 9 4 8 10 4 10 3 7 10 2 9 4 1 7 4 5 9 9 7 9 6 5 10 8 4 7 10 5 3 3 1 6 7 6 1 5 7 7 7 7 2 3 5 10 8 4 8 7 5 8 6 8 6 7 9 3 10 6 6 8 1 5 8 5 9 9 5 8 8 4 6 6 3 1 2 1 2 9 2 10 9 9 6 5 7 9 10 5 8 2 7 4 1 4 7↵
2 72 77 5↵
2 56 63 8↵
3 40 51↵
2 42 51 5↵
3 33 35↵
2 31 97 6↵
3 88 90↵
2 38 78 2↵
3 77 82↵
1 70 80 9↵
1 53 81 4↵
1 86 93 4↵
2 12 33 1↵
3 22 64↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="required ans">↵
↵
~~~~~↵
↵
66↵
11↵
18↵
28↵
138↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="my answer">↵
↵
~~~~~↵
↵
66↵
11↵
18↵
28↵
142↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<br> ↵
it would also be help full if you know some blog or toutorial to solve similar problem.↵
thanks in advance guys for helping.↵
