I’m not able to find any wrong in my code for the question : http://www.spoj.com/problems/LITE/,
this is my code:
using namespace std;
int n,m;
struct tree
{
int flag,sum;
};
tree seg[500000];
int lazy[500000]={0};
void build_tree(int pos,int low,int high)
{
if(low==high)
{
seg[pos].flag=seg[pos].sum=0;
return;
}
int mid=(low+high)/2;
build_tree(2pos+1,low,mid);
build_tree(2pos+2,mid+1,high);
seg[pos].flag=seg[2pos+1].flag||seg[2pos+2].flag;
seg[pos].sum=seg[2pos+1].sum+seg[2pos+2].sum;
}
void update(int pos,int low,int high,int l,int r)
{
if(lazy[pos]==-1)
{
seg[pos].flag^=1;
seg[pos].sum=(high-low+1)*(seg[pos].flag);
if(low!=high)
{
lazy[2*pos+1]=-1;
lazy[2*pos+2]=-1;
}
lazy[pos]=0;
}
if(low>r||high<l)
return;
if(low>=l&&high<=r)
{
seg[pos].flag^=1;
seg[pos].sum=(high-low+1)*(seg[pos].flag);
if(low!=high)
{
lazy[2*pos+1]=-1;
lazy[2*pos+2]=-1;
}
return;
}
int mid=(low+high)/2;
update(2*pos+1,low,mid,l,r);
update(2*pos+2,mid+1,high,l,r);
seg[pos].flag=seg[2*pos+1].flag||seg[2*pos+2].flag;
seg[pos].sum=seg[2*pos+1].sum+seg[2*pos+2].sum;
}
int query(int pos,int low,int high,int l,int r)
{
if(low>r||high<l)
return 0;
if(lazy[pos]==-1)
{
seg[pos].flag^=1;
seg[pos].sum=(high-low+1)(seg[pos].flag);
if(low!=high)
{
lazy[2pos+1]=-1;
lazy[2*pos+2]=-1;
}
lazy[pos]=0;
}
if(low>=l&&high<=r)
return(seg[pos].sum);
int mid=(low+high)/2;
int p1=query(2*pos+1,low,mid,l,r);
int p2=query(2*pos+2,mid+1,high,l,r);
return (p1+p2);
}
int main()
{
cin>>n>>m;
int x,y,z;
build_tree(0,0,n-1);
while(m–)
{
cin>>x>>y>>z;
if(x==0)
{
update(0,0,n-1,y-1,z-1);
}
else
{
cout<<query(0,0,n-1,y-1,z-1)<<endl;
}
//for(int i=0;i<8;i++)
// cout<<i<<" "<<seg[i].flag<<" "<<seg[i].sum<<" lazy "<<lazy[i]<<endl;
}
}
)