Recently i learnt segment trees and lazy propogation approach and solved flipping coins problem in the medium section …and i was getting tle with segment trees so i learnt lazy propogation and now i am gettin wa …here is my code
Can u pls tell me where i am wrong!!i have tried to debug it alot…still it gives wa
#include
#include
#include
#define MAX 300000
using namespace std;
int tree[MAX];
int lazy[MAX];
/*void build_tree(int a,int b,int node)
{
if(a>b)
return;
if(a==b)
{
tree[node]=0;
return;
}
build_tree(a,(a+b)/2,2*node);
build_tree((a+b)/2+1,b,2*node+1);
tree[node]= tree[2*node]+tree[2*node+1];
}*/
void update_tree(int a,int b,int i,int j,int node)
{
int x;
if(lazy[node]!=(-1))
{
tree[node]=lazy[node];
if(a!=b)
{
x=(a+b)/2;
lazy[node*2]= x-a+1-tree[node*2];
lazy[node*2+1]=b-x-tree[node*2+1];
}
lazy[node]=(-1);
}
if((a>b)||(i>b)||(a>j))
return;
if((a>=i)&&(b<=j))
{
tree[node]=b-a+1-tree[node];
if(a!=b)
{
x=(a+b)/2;
lazy[node*2]= x-a+1-tree[node*2];
lazy[node*2+1]=b-x-tree[node*2+1];
}
return;
}
update_tree(a,(a+b)/2,i,j,node*2);
update_tree(1+(a+b)/2,b,i,j,node*2+1);
tree[node]=tree[node*2]+tree[node*2+1];
}
int query_tree(int a,int b,int i,int j,int node)
{
if((a>b)||(i>b)||(a>j))
return 0;
int x;
if(lazy[node]!=(-1))
{
tree[node]=lazy[node];
if(a!=b)
{
x=(a+b)/2;
lazy[node*2]= x-a+1-tree[node*2];
lazy[node*2+1]=b-x-tree[node*2+1];
}
lazy[node]=-1;
}
if((a>=i)&&(b<=j))
return tree[node];
int q1=query_tree(a,(a+b)/2,i,j,node*2);
int q2=query_tree(1+(a+b)/2,b,i,j,node*2+1);
int res=q1+q2;
return res;
}
int main()
{
int n,q;
scanf("%d %d",&n,&q);
//build_tree(0,n-1,1);
memset(tree,0,sizeof tree);
memset(lazy,-1,sizeof lazy);
while(q–)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
if(a==0)
update_tree(0,n-1,b,c,1);
else
printf("%d \n",query_tree(0,n-1,b,c,1));
}
}