费了我一天半的时间，到处debug，后来才发现，主要是建树的时候只在叶子节点对lazy1和lazy2进行初始化了，父节点都没初始化。。。晕。
具体见代码吧。
#include <iostream> #include <stdio.h> #include <algorithm> #define lson rt<<1,L,mid #define rson rt<<1|1,mid+1,R /* 用两个lazy标记，lazy1标记01覆盖，lazy2标记异或（即取反）。 如果在lazy1标记之前，就已经有lazy2异或标记了，那么我们就可以直接去掉lazy2标记（赋值为0），直接进行置01标记； 如果在lazy2异或标记之前，就有01标记了，那么就需要处理一下，即对lazy1进行异或。 具体还是见代码吧，主要是操作繁琐了点 */ using namespace std; const int maxn=100005; int t,n,m; struct Node{ int lsum[2],rsum[2],msum[2]; //统计0/1的左连续的个数，右连续的个数，最大的连续个数 int num[2]; //统计0/1的个数 int lazy1; //标记01覆盖 int lazy2; //标记取反 int len; //区间长度 }tree[maxn<<2]; void pushUp(Node &rt,Node &ls,Node &rs){ rt.lsum[0]=ls.lsum[0];rt.rsum[0]=rs.rsum[0]; rt.lsum[1]=ls.lsum[1];rt.rsum[1]=rs.rsum[1]; rt.num[0]=ls.num[0]+rs.num[0]; rt.num[1]=ls.num[1]+rs.num[1]; if(ls.lsum[0]==ls.len) rt.lsum[0]+=rs.lsum[0]; if(rs.rsum[0]==rs.len) rt.rsum[0]+=ls.rsum[0]; rt.msum[0]=ls.rsum[0]+rs.lsum[0]; rt.msum[0]=max(rt.msum[0],max(ls.msum[0],rs.msum[0])); if(ls.lsum[1]==ls.len) rt.lsum[1]+=rs.lsum[1]; if(rs.rsum[1]==rs.len) rt.rsum[1]+=ls.rsum[1]; rt.msum[1]=ls.rsum[1]+rs.lsum[1]; rt.msum[1]=max(rt.msum[1],max(ls.msum[1],rs.msum[1])); } void changexor(Node &rt){ if(rt.lazy1!=-1) rt.lazy1^=1; //如果之前有01标记，那么就对01标记异或一下即可 else rt.lazy2^=1; //否则对取反标记异或 swap(rt.num[1],rt.num[0]); swap(rt.lsum[1],rt.lsum[0]); swap(rt.rsum[1],rt.rsum[0]); swap(rt.msum[1],rt.msum[0]); } void pushDown(Node &rt,Node &ls,Node &rs,int m){ /* 因为lazy1和lazy2标记只能同时存在一个，所以只需对其中一个操作即可 如果现有标记为lazy1，若进行取反，对lazy1异或即可，即原本全部覆盖成0的变成1，原本为1的变成0，不需对lazy2异或； 若进行覆盖操作，那么直接对lazy1修改。 如果现有标记为lazy2，若进行覆盖操作，那么lazy2直接变为0,；若进行取反操作，则对lazy2进行异或 */ if(rt.lazy1!=-1){ //01覆盖区间 ls.lazy1=rs.lazy1=rt.lazy1; rs.lazy2=ls.lazy2=0; ls.num[rt.lazy1]=ls.lsum[rt.lazy1]=ls.rsum[rt.lazy1]=ls.msum[rt.lazy1]=m-m/2; ls.num[!rt.lazy1]=ls.lsum[!rt.lazy1]=ls.rsum[!rt.lazy1]=ls.msum[!rt.lazy1]=0; rs.num[rt.lazy1]=rs.lsum[rt.lazy1]=rs.rsum[rt.lazy1]=rs.msum[rt.lazy1]=m/2; rs.num[!rt.lazy1]=rs.lsum[!rt.lazy1]=rs.rsum[!rt.lazy1]=rs.msum[!rt.lazy1]=0; rt.lazy1=-1; } else if(rt.lazy2){ //对区间取反 rt.lazy2=0; changexor(ls); changexor(rs); } } void build(int rt,int L,int R){ tree[rt].len=R-L+1; tree[rt].lazy1=-1; //build时都忘记初始化了啊 tree[rt].lazy2=0; //build时都忘记初始化了啊 if(L==R){ int v; scanf("%d",&v); tree[rt].lsum[v]=tree[rt].rsum[v]=tree[rt].msum[v]=1; tree[rt].lsum[!v]=tree[rt].rsum[!v]=tree[rt].msum[!v]=0; tree[rt].num[v]=1; tree[rt].num[!v]=0; tree[rt].lazy1=-1; return; } int mid=(L+R)>>1; build(lson); build(rson); pushUp(tree[rt],tree[rt<<1],tree[rt<<1|1]); } //进行操作01覆盖区间 void update(int rt,int L,int R,int l,int r,int c){ if(l<=L&&R<=r){ tree[rt].lazy2=0; //之前的取反操作就无效了 tree[rt].num[c]=tree[rt].lsum[c]=tree[rt].rsum[c]=tree[rt].msum[c]=(R-L+1); tree[rt].num[!c]=tree[rt].lsum[!c]=tree[rt].rsum[!c]=tree[rt].msum[!c]=0; tree[rt].lazy1=c; return; } pushDown(tree[rt],tree[rt<<1],tree[rt<<1|1],R-L+1); int mid=(L+R)>>1; if(l<=mid) update(lson,l,r,c); if(r>mid) update(rson,l,r,c); pushUp(tree[rt],tree[rt<<1],tree[rt<<1|1]); } //进行取反操作 void updatexor(int rt,int L,int R,int l,int r){ if(l<=L&&R<=r){ if(tree[rt].lazy1!=-1) tree[rt].lazy1^=1; //如果之前有01标记，则要进行处理，对其异或，即取反 else tree[rt].lazy2^=1; //只要将值互换一下即可 swap(tree[rt].num[1],tree[rt].num[0]); swap(tree[rt].lsum[1],tree[rt].lsum[0]); swap(tree[rt].rsum[1],tree[rt].rsum[0]); swap(tree[rt].msum[1],tree[rt].msum[0]); return; } pushDown(tree[rt],tree[rt<<1],tree[rt<<1|1],R-L+1); int mid=(L+R)>>1; if(l<=mid) updatexor(lson,l,r); if(r>mid) updatexor(rson,l,r); pushUp(tree[rt],tree[rt<<1],tree[rt<<1|1]); } //查询时，类型设为Node，进行节点合并，这样就方便好多 Node query(int rt,int L,int R,int l,int r){ if(l<=L&&R<=r){ return tree[rt]; } pushDown(tree[rt],tree[rt<<1],tree[rt<<1|1],R-L+1); int mid=(L+R)>>1; Node tmp,r1,r2; if(r<=mid) tmp=query(lson,l,r); else if(l>mid) tmp=query(rson,l,r); else{ r1=query(lson,l,mid); r2=query(rson,mid+1,r); tmp.len=r1.len+r2.len; pushUp(tmp,r1,r2); //将节点r1和r2合并成tmp } return tmp; } int main() { int op,a,b; Node ans; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); build(1,1,n); for(int i=1;i<=m;i++){ scanf("%d%d%d",&op,&a,&b); a++;b++; if(op<=1) update(1,1,n,a,b,op); else if(op==2) updatexor(1,1,n,a,b); else{ ans=query(1,1,n,a,b); if(op==3) printf("%d ",ans.num[1]); else printf("%d ",ans.msum[1]); } } } return 0; }