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
#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()
#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++)
struct segtree{
vi tree,laz,laz1,change1,change;
int n,base;
void began(int z){
int x,i;
n=z;
//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);
}
}
//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 , l , r );
lazy_up(p , l , r );
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 , mid , a , b);
b1=query(2*p+1 , mid+1 , 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 );
lazy_up(p , l , r );
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 , l , mid , a , b , val);
update1(2*p+1 , mid+1 , r , a , b , val);
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 , l , r );
lazy_up(p , l , r );
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 , l , mid , a , b , val);
update(2*p+1 , mid+1 , r , a , b , val);
tree[p]=(tree[2*p]+tree[2*p+1]);
return ;
}
}
int query(int l,int r){
return query(1 , 1 , n , l , r);
}
void update(int a,int b,int val){
update(1 , 1 , n , a , b , val);
}
void update1(int a,int b,int val){
update1(1 , 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 );
}
int type,a,b,c;
fo(i,0,m){
cin>>type;
if(type==1){
cin>>a>>b>>c;
tree.update(a , b , c);
}
else if(type==2){
cin>>a>>b>>c;
tree.update1(a , b , c);
}
else {
cin>>a>>b;
cout<<tree.query(a , b)<<endl;
}
}
return 0;
}
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
required ans
66
11
18
28
138
my answer
66
11
18
28
142
it would also be help full if you know some blog or toutorial to solve similar problem. thanks in advance guys for helping.
