能过样例,全WA求助
查看原帖
能过样例,全WA求助
307453
云浅知处はなび楼主2020/8/18 12:00

对拍了八十多组数据了=_=,还是没发现错误。

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>

#define MAXN 200005
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)

using namespace std;

int a[MAXN],n,m;
struct Node{
	int sum,len;
	int l,r;
	int lz,re;
	int lmax[2],rmax[2],max[2];
};

struct SMT{
	
	Node d[MAXN<<2];
	
	inline void pushup(int o){
		d[o].sum=d[lson(o)].sum+d[rson(o)].sum;
		d[o].len=d[lson(o)].len+d[rson(o)].len;
		for(int i=0;i<=1;i++){
			d[o].lmax[i]=d[lson(o)].lmax[i];
			if(i==0&&d[lson(o)].sum==0){
				d[o].lmax[i]+=d[rson(o)].lmax[i];
			}
			else if(i==1&&d[lson(o)].sum==d[lson(o)].r-d[lson(o)].l+1){
				d[o].lmax[i]+=d[rson(o)].lmax[i];
			}
			d[o].rmax[i]=d[rson(o)].rmax[i];
			if(i==0&&d[rson(o)].sum==0){
				d[o].rmax[i]+=d[lson(o)].rmax[i];
			}
			else if(i==1&&d[rson(o)].sum==d[rson(o)].r-d[rson(o)].l+1){
				d[o].rmax[i]+=d[lson(o)].rmax[i];
			}
			d[o].max[i]=d[lson(o)].rmax[i]+d[rson(o)].lmax[i];
			d[o].max[i]=max(d[lson(o)].max[i],d[o].max[i]);
			d[o].max[i]=max(d[rson(o)].max[i],d[o].max[i]);
		}
	}

	inline void build(int l,int r,int o){
		d[o].lz=-1;
		d[o].re=0;
		d[o].l=l;
		d[o].r=r;
		d[o].len=r-l+1;
		if(l==r){
			d[o].sum=a[l];
			d[o].lmax[1]=d[o].rmax[1]=d[o].max[1]=(a[l]==1);
			d[o].lmax[0]=d[o].rmax[0]=d[o].max[0]=(a[l]==0);
			return ;
		}
		int mid=(l+r)>>1;
		build(l,mid,lson(o));
		build(mid+1,r,rson(o));
		pushup(o);
	}

	inline void pushdown(int o){
		if(d[o].lz!=-1){
			d[o].re=0;
			int val=d[o].lz;

			d[lson(o)].sum=(d[lson(o)].r-d[lson(o)].l+1)*val;
			d[rson(o)].sum=(d[rson(o)].r-d[rson(o)].l+1)*val;

			d[lson(o)].lz=d[rson(o)].lz=val;
			d[lson(o)].re=d[rson(o)].re=0;
			
			d[lson(o)].max[val]=d[lson(o)].lmax[val]=d[lson(o)].rmax[val]=d[lson(o)].r-d[lson(o)].l+1;
			d[rson(o)].max[val]=d[rson(o)].lmax[val]=d[rson(o)].rmax[val]=d[rson(o)].r-d[rson(o)].l+1;

			d[lson(o)].max[val^1]=d[lson(o)].lmax[val^1]=d[lson(o)].rmax[val^1]=0;
			d[rson(o)].max[val^1]=d[rson(o)].lmax[val^1]=d[rson(o)].rmax[val^1]=0;

			d[o].lz=-1;
		}
		if(d[o].re){
			d[lson(o)].sum=(d[lson(o)].r-d[lson(o)].l+1)-d[lson(o)].sum;
 			d[rson(o)].sum=(d[rson(o)].r-d[rson(o)].l+1)-d[rson(o)].sum;
			
			if(d[lson(o)].lz!=-1)d[lson(o)].lz^=1;
			else d[lson(o)].re^=1;
			if(d[rson(o)].lz!=-1)d[rson(o)].lz^=1;
			else d[rson(o)].re^=1;

			swap(d[lson(o)].max[1],d[lson(o)].max[0]);
			swap(d[rson(o)].max[1],d[rson(o)].max[0]);
			
			swap(d[lson(o)].lmax[1],d[lson(o)].lmax[0]);
			swap(d[rson(o)].lmax[1],d[rson(o)].lmax[0]);
			
			swap(d[lson(o)].rmax[1],d[lson(o)].rmax[0]);
			swap(d[rson(o)].rmax[1],d[rson(o)].rmax[0]);
		}
	}

	inline void modify(int l,int r,int tag,int o){
		pushdown(o);
		//printf("QAQ, o=%d, l=%d, r=%d\n",o,d[o].l,d[o].r);
		if(d[o].l==l&&d[o].r==r){
			if(tag==0||tag==1){
				d[o].sum=d[o].len*tag;
				d[o].lz=tag;

				d[o].lmax[tag]=d[o].rmax[tag]=d[o].max[tag]=d[o].len;
				d[o].lmax[tag^1]=d[o].rmax[tag^1]=d[o].max[tag^1]=0;

				//puts("QAQAQ1");
			}
			else if(tag==2){
				d[o].sum=d[o].len-d[o].sum;
				d[o].re^=1;
				
				swap(d[o].max[1],d[o].max[0]);
				swap(d[o].lmax[1],d[o].lmax[0]);
				swap(d[o].rmax[1],d[o].rmax[0]);

				//puts("QAQAQ2");
			}
			return ;
		}
		int mid=(d[o].l+d[o].r)>>1;
		//puts("QwQwQ");
		if(l>mid)modify(l,r,tag,rson(o));
		else if(r<=mid)modify(l,r,tag,lson(o));
		else modify(l,mid,tag,lson(o)),modify(mid+1,r,tag,rson(o));
		//puts("OvOvO");
		pushup(o);
	}

	inline int query(int l,int r,int o){
		pushdown(o);
		if(d[o].l==l&&d[o].r==r){
			return d[o].sum;
		}
		int mid=(d[o].l+d[o].r)>>1;
		if(l>mid)return query(l,r,rson(o));
		else if(r<=mid)return query(l,r,lson(o));
		else return query(l,mid,lson(o))+query(mid+1,r,rson(o));
	}

	inline Node Q(int l,int r,int o){
		pushdown(o);
		if(d[o].l==l&&d[o].r==r){
			return d[o];
		}
		int mid=(d[o].l+d[o].r)>>1;
		if(l>mid)return Q(l,r,rson(o));
		else if(r<=mid)return Q(l,r,lson(o));
		else{
			Node tmp,L=Q(l,mid,lson(o)),R=Q(mid+1,r,rson(o));
			tmp.sum=L.sum+R.sum;
			for(int i=0;i<=1;i++){
				tmp.lmax[i]=L.lmax[i];
				if(i==0&&L.sum==0){
					tmp.lmax[i]+=R.lmax[i];
				}
				else if(i==1&&L.sum==L.len){
					tmp.lmax[i]+=R.lmax[i];
				}
				tmp.rmax[i]=R.rmax[i];
				if(i==0&&R.sum==0){
					tmp.rmax[i]+=L.rmax[i];
				}
				else if(i==1&&R.sum==R.len){
					tmp.rmax[i]+=L.rmax[i];
				}
				tmp.max[i]=L.rmax[i]+R.lmax[i];
				tmp.max[i]=max(tmp.max[i],L.max[i]);
				tmp.max[i]=max(tmp.max[i],R.max[i]);
			}
			return tmp;
		}
	}

	inline void print(){
		for(int i=1;i<=(n<<1);i++){
			printf("i=%d, sum=%d, len=%d, l=%d, r=%d, lz=%d, re=%d, lmax[0]=%d, lmax[1]=%d, rmax[0]=%d, rmax[1]=%d, max[0]=%d, max[1]=%d\n",i,d[i].sum,d[i].len,d[i].l,d[i].r,d[i].lz,d[i].re,d[i].lmax[0],d[i].lmax[1],d[i].rmax[0],d[i].rmax[1],d[i].max[0],d[i].max[1]);
			printf("————————————————————————————————————————————————-———————————————————————————————————————————————————————————————————\n");
		}
	}

};

SMT tree;

int main(void){

	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}

	tree.build(1,n,1);
	//tree.print();

	while(m--){
		int opt,l,r;
		scanf("%d%d%d",&opt,&l,&r);
		opt++,l++,r++;
		//printf("%d %d %d\n",opt,l,r);
		if(opt==1){
			tree.modify(l,r,0,1);
		}
		else if(opt==2){
			tree.modify(l,r,1,1);
		}
		else if(opt==3){
			tree.modify(l,r,2,1);
		}
		else if(opt==4){
			printf("%d\n",tree.query(l,r,1));
		}
		else if(opt==5){
			printf("%d\n",tree.Q(l,r,1).max[1]);
		}
	}

	return 0;
}
2020/8/18 12:00
加载中...