HDU-3397-Sequence operation


HDU-3397-Sequence operation
http://acm.hdu.edu.cn/showproblem.php?pid=3397
セグメントツリー、区間の複数の操作
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define N 100010
struct cam
{
	int x;
	int y;
	int len;
	int cover;
}list[N*5];
int num[N];
int maxlen,curlen,r;
void updateinfo(int k)
{
	if(list[k<<1].cover==list[k<<1|1].cover)
	list[k].cover=list[k<<1].cover;
	else
	list[k].cover=-1;
}
void build(int k,int x,int y)
{
	list[k].x=x;
	list[k].y=y;
	list[k].len=(y-x+1);
	if(x==y)
	{
		list[k].cover=num[x];
		return;
	}
	int mid=(x+y)/2;
	build(k<<1,x,mid);
	build(k<<1|1,mid+1,y);
	updateinfo(k);  // 
}
void lazy(int k)
{
    list[k<<1].cover=list[k].cover;
	list[k<<1|1].cover=list[k].cover;
	list[k].cover=-1;
}
void update(int k,int x,int y,int val)
{
	if(list[k].cover==val)
	return;
	if(x==list[k].x&&list[k].y==y)
	{
		list[k].cover=val;
		return;
	}
	if(list[k].cover!=-1)
	lazy(k);
	int mid=(list[k].x+list[k].y)/2;
	if(x>mid)
	update(k<<1|1,x,y,val);
	else if(y<=mid)
	update(k<<1,x,y,val);
	else
	{
		update(k<<1,x,mid,val);
		update(k<<1|1,mid+1,y,val);
	}
}
void updatexor(int k,int x,int y)
{
	if(x==list[k].x&&list[k].y==y&&list[k].cover!=-1)
	{
		list[k].cover^=1;
		return;
	}
	if(list[k].cover!=-1)
	lazy(k);
	int mid=(list[k].x+list[k].y)/2;
	if(x>mid)
	updatexor(k<<1|1,x,y);
	else if(y<=mid)
	updatexor(k<<1,x,y);
	else
	{
		updatexor(k<<1,x,mid);
		updatexor(k<<1|1,mid+1,y);
	}
}
int query(int k,int x,int y)
{
	if(list[k].x==x&&list[k].y==y&&list[k].cover!=-1)
	{
		if(list[k].cover==0)
		return 0;
		else
		return list[k].len;
	}
	if(list[k].cover!=-1)
	lazy(k);
	int mid=(list[k].x+list[k].y)/2;
	if(x>mid)
	return query(k<<1|1,x,y);
	else if(y<=mid)
	return query(k<<1,x,y);
	else
	return query(k<<1,x,mid)+query(k<<1|1,mid+1,y);
}
void querymaxlen(int k,int x,int y)
{
	if(list[k].cover==0)
	return;
	if(x==list[k].x&&list[k].y==y&&list[k].cover==1)
	{
		if(x==r+1)
		curlen+=list[k].len;
		else
		curlen=list[k].len;
		if(curlen>maxlen)
		maxlen=curlen;
		r=list[k].y;
		return;
	}
	if(list[k].cover!=-1)
	lazy(k);
	int mid=(list[k].x+list[k].y)/2;
	if(x>mid)
	return querymaxlen(k<<1|1,x,y);
	else if(y<=mid)
	return querymaxlen(k<<1,x,y);
	else
	{
		querymaxlen(k<<1,x,mid);
		querymaxlen(k<<1|1,mid+1,y);
	}
}
int main()
{
	int i,n,m,t,op,a,b;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
		scanf("%d",&num[i]);
		build(1,0,n-1);
		while(m--)
		{
			scanf("%d%d%d",&op,&a,&b);
			if(op==0)
			update(1,a,b,0);
			else if(op==1)
			update(1,a,b,1);
			else if(op==2)
			updatexor(1,a,b);
			else if(op==3)
			printf("%d
",query(1,a,b)); else if(op==4) { maxlen=curlen=r=0; querymaxlen(1,a,b); printf("%d
",maxlen); } } } return 0; }