花了一秒钟时间构思，写了好几天。弱。
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int maxn=100000+10; int T,N,Q,ans; struct SegTree { int zero;//零的个数 int one;//一的个数 int lsum;//从左边开始的最长连续的1的长度 int rsum;//从右边开始的最长连续的1的长度 int msum;//这段区间连续最长的1的长度 int Lsum;//从左边开始的最长连续的0的长度 int Rsum;//从右边开始的最长连续的0的长度 int Msum;//这段区间连续最长的0的长度 int f; }segTree[maxn*4]; void tra1(int rt,int len)//变0 { segTree[rt].zero=len; segTree[rt].one=0; segTree[rt].lsum=0; segTree[rt].rsum=0; segTree[rt].msum=0; segTree[rt].Lsum=len; segTree[rt].Rsum=len; segTree[rt].Msum=len; } void tra2(int rt,int len)//变1 { segTree[rt].zero=0; segTree[rt].one=len; segTree[rt].lsum=len; segTree[rt].rsum=len; segTree[rt].msum=len; segTree[rt].Lsum=0; segTree[rt].Rsum=0; segTree[rt].Msum=0; } void Swap(int rt) { swap(segTree[rt].zero,segTree[rt].one); swap(segTree[rt].lsum,segTree[rt].Lsum); swap(segTree[rt].rsum,segTree[rt].Rsum); swap(segTree[rt].msum,segTree[rt].Msum); } void pushUp(int rt,int len) { //确定零的个数 segTree[rt].zero=segTree[2*rt].zero+segTree[2*rt+1].zero; //确定一的个数 segTree[rt].one=segTree[2*rt].one+segTree[2*rt+1].one; //确定从左边开始最长连续1的长度 if(segTree[2*rt].msum==len-len/2) segTree[rt].lsum=segTree[2*rt].lsum+segTree[2*rt+1].lsum; else segTree[rt].lsum=segTree[2*rt].lsum; //确定从右边开始最长连续1的长度 if(segTree[2*rt+1].rsum==len/2) segTree[rt].rsum=segTree[2*rt].rsum+segTree[2*rt+1].rsum; else segTree[rt].rsum=segTree[2*rt+1].rsum; //确定这段区间连续最长的1的长度 segTree[rt].msum=max(segTree[2*rt].msum,segTree[2*rt+1].msum); segTree[rt].msum=max(segTree[rt].msum,segTree[2*rt].rsum+segTree[2*rt+1].lsum); //确定从左边开始最长连续0的长度 if(segTree[2*rt].Msum==len-len/2) segTree[rt].Lsum=segTree[2*rt].Lsum+segTree[2*rt+1].Lsum; else segTree[rt].Lsum=segTree[2*rt].Lsum; //确定从右边开始最长连续0的长度 if(segTree[2*rt+1].Rsum==len/2) segTree[rt].Rsum=segTree[2*rt].Rsum+segTree[2*rt+1].Rsum; else segTree[rt].Rsum=segTree[2*rt+1].Rsum; //确定这段区间连续最长的0的长度 segTree[rt].Msum=max(segTree[2*rt].Msum,segTree[2*rt+1].Msum); segTree[rt].Msum=max(segTree[rt].Msum,segTree[2*rt].Rsum+segTree[2*rt+1].Lsum); } void pushDown(int rt,int len) { if(segTree[rt].f==0) { segTree[2*rt].f=segTree[2*rt+1].f=0; tra1(2*rt,len-len/2); tra1(2*rt+1,len/2); } else if(segTree[rt].f==1) { segTree[2*rt].f=segTree[2*rt+1].f=1; tra2(2*rt,len-len/2); tra2(2*rt+1,len/2); } else { Swap(2*rt); if(segTree[2*rt].f==0) segTree[2*rt].f=1; else if(segTree[2*rt].f==1) segTree[2*rt].f=0; else if(segTree[2*rt].f==-1) segTree[2*rt].f=2; else segTree[2*rt].f=-1; Swap(2*rt+1); if(segTree[2*rt+1].f==0) segTree[2*rt+1].f=1; else if(segTree[2*rt+1].f==1) segTree[2*rt+1].f=0; else if(segTree[2*rt+1].f==-1) segTree[2*rt+1].f=2; else segTree[2*rt+1].f=-1; } segTree[rt].f=-1; } void build(int l,int r,int rt) { segTree[rt].f=-1; if(l==r) { int x; scanf("%d",&x); if(x==0) tra1(rt,1); else if(x==1) tra2(rt,1); return; } int m=(l+r)/2; build(l,m,2*rt); build(m+1,r,2*rt+1); pushUp(rt,r-l+1); } void update(int L,int R,int f,int Xor,int l,int r,int rt) { if(L<=l&&r<=R) { if(f==-1)//第二种操作 { Swap(rt); if(segTree[rt].f==1) segTree[rt].f=0; else if(segTree[rt].f==0) segTree[rt].f=1; else if(segTree[rt].f==-1) segTree[rt].f=2; else segTree[rt].f=-1; } else //第零种，第一种操作 { if(f==0) tra1(rt,r-l+1); else tra2(rt,r-l+1); segTree[rt].f=f; } return; } if(segTree[rt].f!=-1) pushDown(rt,r-l+1); int m=(l+r)/2; if(L<=m) update(L,R,f,Xor,l,m,2*rt); if(R>m) update(L,R,f,Xor,m+1,r,2*rt+1); pushUp(rt,r-l+1); } int quary1(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return segTree[rt].one; if(segTree[rt].f!=-1) pushDown(rt,r-l+1); int m=(l+r)/2; int res=0; if(L<=m) res+=quary1(L,R,l,m,2*rt); if(R>m) res+=quary1(L,R,m+1,r,2*rt+1); pushUp(rt,r-l+1); return res; } int quary2(int L,int R,int l,int r,int rt) { if(L<=l&&R>=r) return segTree[rt].msum; if(segTree[rt].f!=-1) pushDown(rt,r-l+1); int m=(l+r)/2; if(R<=m) return quary2(L,R,l,m,2*rt); else if(L>m) return quary2(L,R,m+1,r,2*rt+1); else { int Q1=quary2(L,R,l,m,2*rt); int Q2=quary2(L,R,m+1,r,2*rt+1); int E=max(Q1,Q2); int Min1=min(segTree[2*rt].rsum,m-L+1); int Min2=min(segTree[2*rt+1].lsum,R-m); E=max(E,Min1+Min2); return E; } pushUp(rt,r-l+1); } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&N,&Q); build(1,N,1); for(int i=1;i<=Q;i++) { int op,a,b; scanf("%d%d%d",&op,&a,&b); a++;b++; if(op==0) update(a,b,0,-1,1,N,1); if(op==1) update(a,b,1,-1,1,N,1); if(op==2) update(a,b,-1,1,1,N,1); if(op==3) printf("%d ", quary1(a,b,1,N,1)); if(op==4) printf("%d ",quary2(a,b,1,N,1)); } } return 0; }