BZOJ_1858_[Scoi2010]序列操作_线段树

2023-10-13 15:54:28

Description

lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的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）

Output

对于每一个询问操作，输出一行，包括1个数，表示其对应的答案

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

分析：线段树处理多个标记。

我这里是先下传取反标记，后下传覆盖标记。

这样的话。如果操作是先覆盖后取反，就在取反的函数中判断一下，如果有覆盖就把覆盖的值取反。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 100050

#define ls p<<1

#define rs p<<1|1

int t[N<<2],cov[N<<2],rev[N<<2],n,m;

int lx[N<<2][2],rx[N<<2][2],nx[N<<2][2],siz[N<<2];

void pushup(int p) {

	t[p]=t[ls]+t[rs];

	for(int i=0;i<2;i++) {

		if(nx[ls][i]==siz[ls]) lx[p][i]=siz[ls]+lx[rs][i];

		else lx[p][i]=lx[ls][i];

		if(nx[rs][i]==siz[rs]) rx[p][i]=siz[rs]+rx[ls][i];

		else rx[p][i]=rx[rs][i];

		nx[p][i]=max(max(rx[ls][i]+lx[rs][i],nx[ls][i]),nx[rs][i]);

	}

}

void build(int l,int r,int p) {

	cov[p]=-1;

	siz[p]=r-l+1;

	if(l==r) {

		scanf("%d",&t[p]);

		lx[p][1]=rx[p][1]=nx[p][1]=t[p];

		lx[p][0]=rx[p][0]=nx[p][0]=!t[p];

		return ;

	}

	int mid=l+r>>1;

	build(l,mid,ls);

	build(mid+1,r,rs);

	pushup(p);

}

void pushdown(int p) {

	if(rev[p]) {

		t[ls]=siz[ls]-t[ls];

		swap(lx[ls][0],lx[ls][1]);

		swap(rx[ls][0],rx[ls][1]);

		swap(nx[ls][0],nx[ls][1]);

		if(cov[ls]!=-1)cov[ls]^=1;

		rev[ls]^=1;

		t[rs]=siz[rs]-t[rs];

		swap(lx[rs][0],lx[rs][1]);

		swap(rx[rs][0],rx[rs][1]);

		swap(nx[rs][0],nx[rs][1]);

		if(cov[rs]!=-1)cov[rs]^=1;

		rev[rs]^=1;

		rev[p]=0;

	}

	if(cov[p]!=-1) {

		int d=cov[p];

		cov[ls]=cov[rs]=d;

		lx[ls][d]=rx[ls][d]=nx[ls][d]=siz[ls];

		lx[rs][d]=rx[rs][d]=nx[rs][d]=siz[rs];

		lx[ls][!d]=rx[ls][!d]=nx[ls][!d]=lx[rs][!d]=rx[rs][!d]=nx[rs][!d]=0;

		t[ls]=siz[ls]*d;

		t[rs]=siz[rs]*d;

		cov[p]=-1;

	}

}

void uprever(int l,int r,int x,int y,int p) {

	if(x<=l&&y>=r) {

		t[p]=siz[p]-t[p];

		swap(lx[p][0],lx[p][1]);

		swap(rx[p][0],rx[p][1]);

		swap(nx[p][0],nx[p][1]);

		rev[p]^=1;

		if(cov[p]!=-1) cov[p]^=1;

		return ;

	}

	pushdown(p);

	int mid=l+r>>1;

	if(x<=mid) uprever(l,mid,x,y,ls);

	if(y>mid) uprever(mid+1,r,x,y,rs);

	pushup(p);

}

void update(int l,int r,int x,int y,int c,int p) {

	if(x<=l&&y>=r) {

		cov[p]=c;

		lx[p][c]=rx[p][c]=nx[p][c]=siz[p];

		lx[p][!c]=rx[p][!c]=nx[p][!c]=0;

		t[p]=siz[p]*c;

		return ;

	}

	pushdown(p);

	int mid=l+r>>1;

	if(x<=mid) update(l,mid,x,y,c,ls);

	if(y>mid) update(mid+1,r,x,y,c,rs);

	pushup(p);

}

int qsum(int l,int r,int x,int y,int p) {

	if(x<=l&&y>=r) return t[p];

	pushdown(p);

	int re=0,mid=l+r>>1;

	if(x<=mid) re+=qsum(l,mid,x,y,ls);

	if(y>mid) re+=qsum(mid+1,r,x,y,rs);

	return re;

}

int qcon(int l,int r,int x,int y,int p) {

	if(x<=l&&y>=r) return nx[p][1];

	pushdown(p);

	int ansl,ansr,ansm,mid=l+r>>1;

	if(y<=mid) return qcon(l,mid,x,y,ls);

	else if(x>mid) return qcon(mid+1,r,x,y,rs);

	else {

		ansl=qcon(l,mid,x,y,ls);

		ansr=qcon(mid+1,r,x,y,rs);

		ansm=min(mid-x+1,rx[ls][1])+min(y-mid,lx[rs][1]);

		return max(max(ansl,ansr),ansm);

	}

}

int main() {

	scanf("%d%d",&n,&m);

	int i,opt,x,y;

	build(1,n,1);

	for(i=1;i<=m;i++) {

		scanf("%d%d%d",&opt,&x,&y);

		x++;y++;

		if(opt==0) {

			update(1,n,x,y,0,1);

		}else if(opt==1) {

			update(1,n,x,y,1,1);

		}else if(opt==2) {

			uprever(1,n,x,y,1);

		}else if(opt==3) {

			printf("%d\n",qsum(1,n,x,y,1));

		}else {

			printf("%d\n",qcon(1,n,x,y,1));

		}

	}

}

码农公寓