首页 > 代码库 > bzoj1858 [Scoi2010]序列操作

bzoj1858 [Scoi2010]序列操作

2024-08-05 09:46:45   220人阅读

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<n）表示对于区间[a, b]执行标号为op的操作="" <="" div="">

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

 
这线段树……写的我一口老血喷出来
唉……毕竟我老了
这题要维护的东西好多……先搞个tag表示这个区间有没有被完全覆盖，然后因为有恶心的连续段的询问操作所以还要记一下区间中从左端点往右（右端点往左）的连续的”1“的长度，还有区间中最长连续的“1”的长度，转移同“小白逛公园”
然后因为有翻转操作所以“0”的也要顺带记一下……
真是痛苦啊一开始pushdown写了60+行update30+行感觉不会再爱了
后来巧妙的把代码缩短了点（我有特殊的缩代码技巧）
幸好没出现什么坑爹的错……不然去调这个真的会出人命的
#include<cstdio>inline int read(){	int x=0,f=1;char ch=getchar();	while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}struct segtree{	int l,r,len;	int tag;	bool rev;	int l0,r0,l1,r1,mx0,mx1,sum;}tree[1000010];int n,m,saver1,mx;int a[100010];inline int max(const int &a,const int &b){if (a>b)return a;else return b;}inline void swap(int &a,int &b){int t=a;a=b;b=t;}inline void cover(int now,int c){	int len=tree[now].r-tree[now].l+1;	if (c)	{		tree[now].tag=1;		tree[now].sum=len;		tree[now].l0=0;		tree[now].l1=len;		tree[now].r0=0;		tree[now].r1=len;		tree[now].mx0=0;		tree[now].mx1=len;	}else	{		tree[now].tag=0;		tree[now].sum=0;		tree[now].l0=len;		tree[now].l1=0;		tree[now].r0=len;		tree[now].r1=0;		tree[now].mx0=len;		tree[now].mx1=0;	}}inline void rever(int now){	if (tree[now].tag!=-1)tree[now].tag^=1;	tree[now].rev^=1;	tree[now].sum=tree[now].len-tree[now].sum;	swap(tree[now].l0,tree[now].l1);	swap(tree[now].r0,tree[now].r1);	swap(tree[now].mx0,tree[now].mx1);}inline void update(int now){	tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;	tree[now].l0=tree[now<<1].l0;	if (tree[now<<1].l0==tree[now<<1].len)tree[now].l0+=tree[now<<1|1].l0;	tree[now].r0=tree[now<<1|1].r0;	if (tree[now<<1|1].r0==tree[now<<1|1].len)tree[now].r0+=tree[now<<1].r0;	tree[now].l1=tree[now<<1].l1;	if (tree[now<<1].l1==tree[now<<1].len)tree[now].l1+=tree[now<<1|1].l1;	tree[now].r1=tree[now<<1|1].r1;	if (tree[now<<1|1].r1==tree[now<<1|1].len)tree[now].r1+=tree[now<<1].r1;	tree[now].mx0=max(max(tree[now<<1].mx0,tree[now<<1|1].mx0),tree[now<<1].r0+tree[now<<1|1].l0);	tree[now].mx1=max(max(tree[now<<1].mx1,tree[now<<1|1].mx1),tree[now<<1].r1+tree[now<<1|1].l1);}inline void pushdown(int now){	if (tree[now].len==1)return;	int tag=tree[now].tag;tree[now].tag=-1;	bool rev=tree[now].rev;tree[now].rev=0;	if(tag!=-1)	{		int lenl=tree[now<<1].len,lenr=tree[now<<1|1].len;		tree[now<<1].rev=tree[now<<1|1].rev=0;		if (tag==0)		{			cover(now<<1,0);			cover(now<<1|1,0);		}else 		if(tag==1)		{			cover(now<<1,1);			cover(now<<1|1,1);		}	}else	if (rev)	{		rever(now<<1);		rever(now<<1|1);	}}inline void change(int now,int x,int y,int dat){	pushdown(now);	int l=tree[now].l,r=tree[now].r;	if (l==x&&r==y)	{		if (dat)cover(now,1);else cover(now,0);		return;	}	int mid=(l+r)>>1;	if (y<=mid)change(now<<1,x,y,dat);	else if (x>mid)change(now<<1|1,x,y,dat);	else	{		change(now<<1,x,mid,dat);		change(now<<1|1,mid+1,y,dat);	}	update(now);}inline void reverse(int now,int x,int y){	pushdown(now);	int l=tree[now].l,r=tree[now].r;	if (l==x&&r==y)	{		rever(now);		return;	}	int mid=(l+r)>>1;	if (y<=mid)reverse(now<<1,x,y);	else if (x>mid)reverse(now<<1|1,x,y);	else	{		reverse(now<<1,x,mid);		reverse(now<<1|1,mid+1,y);	}	update(now);}inline int ask(int now,int x,int y){	pushdown(now);	int l=tree[now].l,r=tree[now].r;	if (l==x&&r==y)return tree[now].sum;	int mid=(l+r)>>1;	if (y<=mid)return ask(now<<1,x,y);	else if (x>mid)return ask(now<<1|1,x,y);	else return ask(now<<1,x,mid)+ask(now<<1|1,mid+1,y);}inline void ask2(int now,int x,int y){	pushdown(now);	int l=tree[now].l,r=tree[now].r;	if (l==x&&r==y)	{		mx=max(mx,max(saver1+tree[now].l1,tree[now].mx1));		if (tree[now].mx1==tree[now].len)saver1+=tree[now].len;		else saver1=tree[now].r1;		return;	}	int mid=(l+r)>>1;	if (y<=mid) ask2(now<<1,x,y);	else if (x>mid) ask2(now<<1|1,x,y);	else	{		ask2(now<<1,x,mid);		ask2(now<<1|1,mid+1,y);	}}inline void buildtree(int now,int l,int r){	tree[now].l=l;tree[now].r=r;tree[now].len=r-l+1;	tree[now].tag=-1;	if(l==r)	{		if (a[l]==1)cover(now,1);		else cover(now,0);		return;	}	int mid=(l+r)>>1;	buildtree(now<<1,l,mid);	buildtree(now<<1|1,mid+1,r);	update(now);}int main(){	n=read();m=read();	for (int i=1;i<=n;i++)a[i]=read();	buildtree(1,1,n);	for (int i=1;i<=m;i++)	{		int opr=read(),x=read()+1,y=read()+1;		if (opr==0)change(1,x,y,0);		if (opr==1)change(1,x,y,1);		if (opr==2)reverse(1,x,y);		if (opr==3)printf("%d\n",ask(1,x,y));		if (opr==4)		{			saver1=0;mx=0;			ask2(1,x,y);			printf("%d\n",mx);		}	}	return 0; }

　　

bzoj1858 [Scoi2010]序列操作


联系
我们