bzoj 1858: 시퀀스 작업 (선분 트 리 구간 정보 통합)

1858: [Scoi 2010] 시퀀스 조작
Time Limit: 10 Sec  Memory Limit: 64 MB
Description
lxhgww 는 최근 에 01 서열 을 받 았 습 니 다. 서열 안에 n 개의 수 를 포함 하고 있 습 니 다. 이 수 는 0 이거 나 1 입 니 다. 현재 이 서열 에 대해 다섯 가지 변환 작업 과 문의 작업 이 있 습 니 다. 0 a b 는 [a, b] 구간 안의 모든 수 를 0 1 a b 로 바 꾸 고 [a, b] 구간 안의 모든 수 를 12 a b 로 바 꾸 었 습 니 다.모든 1 을 0, 3 a b 로 바 꾸 어 [a, b] 구간 내 에 모두 몇 개의 1, 4 a b 가 [a, b] 구간 내 에 최대 몇 개의 연속 적 인 1 이 있 는 지 물 어 보 는 것 에 대해 lxhgww 는 대답 을 해 야 합 니 다. 똑똑 한 프로그래머 들, 당신들 은 그 를 도와 줄 수 있 습 니까?
Input
입력 데이터 의 첫 번 째 줄 은 2 개의 수, n 과 m 를 포함 하고 각각 서열 의 길이 와 조작 수 를 나타 낸다. 두 번 째 줄 은 n 개의 수 를 포함한다. 서열 의 초기 상 태 를 나타 내 는 다음 m 줄 은 줄 당 3 개의 수, op, a, b, (0 < = op < = 4, 0 < = a < = b < = "div =" "style =" font - family: arial, verdana, helvetica, sans - serif; ">
Output
모든 질문 작업 에 대해 한 줄 을 출력 하고 한 줄 을 포함 하여 해당 하 는 답 을 표시 합 니 다.
Sample Input
   10 10
   0 0 0 1 1 0 1 0 1 1
   1 0 2
   3 0 5
   2 2 2
   4 0 4
   0 3 6
   2 3 7
   4 2 8
   1 0 5
   0 5 6
   3 3 9
Sample Output
   5
   2
   6
   5
HINT
30% 의 데이터 에 대해 1 < = n, m < = 1000 대 100% 의 데이터, 1 < = n, m < = 100000
제목 분석: hotel 그 문제 의 강화 판 입 니 다. 여기 서 우 리 는 최 장 연속 1 을 유지 해 야 할 뿐만 아니 라 0 도 유지 해 야 합 니 다. 왜냐하면 그것 은 언제든지 반대 할 수 있 기 때 문 입 니 다. 그리고 한 가지 주의해 야 할 것 은 각종 게 으 름 표시 간 의 커버 와 합병 문제 입 니 다. 예 를 들 어 한 점 은 원래 op = 0 의 게 으 름 표시 (자 나 무 를 모두 0 으로 바 꾸 는 것) 가 있 었 고 그 위 에 op = 2 의 게 으 름 표 시 를 전달 하 는 것 입 니 다.(하위 나 무 를 모두 반대로) 결 과 는 op = 1 의 게 으 름 표시 (모두 1 로 변 함) 와 같은...
CODE：

#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int maxn=100100;

struct data
{
	int llen,rlen,slen;
} ;

struct Tnode
{
	int add;
	data num[2];
	int sum;
} tree[maxn<<2];

int a[maxn];
int n,m;

void Clear(int root,int L,int R,int x)
{
	Tnode *P=tree+root;
	P->sum=(R-L+1)*x;
		
	P->num[x].llen=R-L+1;
	P->num[x].rlen=R-L+1;
	P->num[x].slen=R-L+1;
	
	P->num[!x].llen=0;
	P->num[!x].rlen=0;
	P->num[!x].slen=0;
}

void Work(int root,int L,int R,int id)
{
	int left=root<<1;
	int right=left|1;
	int mid=(L+R)>>1;
	
	int temp=tree[left].num[id].llen;
	tree[root].num[id].llen=temp;
	if ( temp==mid-L+1 ) tree[root].num[id].llen+=tree[right].num[id].llen;
	
	temp=tree[right].num[id].rlen;
	tree[root].num[id].rlen=temp;
	if ( temp==R-mid ) tree[root].num[id].rlen+=tree[left].num[id].rlen;
	
	temp=max( tree[left].num[id].slen,tree[right].num[id].slen );
	temp=max( temp,tree[left].num[id].rlen+tree[right].num[id].llen );
	tree[root].num[id].slen=temp;
}

void Up(int root,int L,int R)
{
	int left=root<<1;
	int right=left|1;
	tree[root].sum=tree[left].sum+tree[right].sum;
	
	Work(root,L,R,0);
	Work(root,L,R,1);
}

void Build(int root,int L,int R)
{
	tree[root].add=0;
	if (L==R)
	{
		Clear(root,L,R,a[L]);
		return;
	}
	
	int left=root<<1;
	int right=left|1;
	int mid=(L+R)>>1;
	
	Build(left,L,mid);
	Build(right,mid+1,R);
	
	Up(root,L,R);
}

void Change(int root,int L,int R,int op)
{
	if (op==1)
	{
		Clear(root,L,R,0);
		tree[root].add=op;
	}
	
	if (op==2)
	{
		Clear(root,L,R,1);
		tree[root].add=op;
	}
	
	if (op==3)
	{
		swap(tree[root].num[0],tree[root].num[1]);
		tree[root].sum=(R-L+1)-tree[root].sum;
		
		if (tree[root].add==1) tree[root].add++;
		else if (tree[root].add==2) tree[root].add--;
			 else if (tree[root].add==3) tree[root].add=0;
			 	  else tree[root].add=3;
	}
}

void Down(int root,int L,int R)
{
	if (!tree[root].add) return;
	
	int left=root<<1;
	int right=left|1;
	int mid=(L+R)>>1;
	
	Change(left,L,mid,tree[root].add);
	Change(right,mid+1,R,tree[root].add);
	
	tree[root].add=0;
}

void Update(int root,int L,int R,int x,int y,int op)
{
	if ( y>1;
	
	Update(left,L,mid,x,y,op);
	Update(right,mid+1,R,x,y,op);
	
	Up(root,L,R);
}

int Query(int root,int L,int R,int x,int y,int op)
{
	if ( y>1;
	
	int vl=Query(left,L,mid,x,y,op);
	int vr=Query(right,mid+1,R,x,y,op);
	
	if (op==4) return vl+vr;
	else
	{
		int temp=max(vl,vr);
		int tl=max(x,mid-tree[left].num[1].rlen+1);
		int tr=min(y,mid+tree[right].num[1].llen);
		temp=max(temp,tr-tl+1);
		return temp;
	}
}

int main()
{
	freopen("bzoj1858.in","r",stdin);
	freopen("bzoj1858.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for (int i=1; i<=n; i++) scanf("%d",&a[i]);
	
	Build(1,1,n);
	
	/*for (int i=1; i<=30; i++)
	{
		cout<add<sum<num[0].llen<num[0].rlen<num[0].slen<num[1].llen<num[1].rlen<num[1].slen<