这个是去年遗留历史问题,之前思路混乱,搞了好多发都是WA,就没做了
自从上次做了大白书上那个双重懒惰标记的题目,做这个就思路很清晰了
跟上次大白上那个差不多,这个也是有一个sets标记,代表这个区间全部置为0或者1,没有置位的时候为-1
还有个rev标记,代表翻转操作,0代表当前不翻,1代表当前翻
要注意一下优先级,发现有不同的弄法,我是这个弄得,有set操作的时候,set标记设值,并把当前节点的rev标记设为0,因为不管要不要rev,当前set操作肯定直接覆盖了
rev操作不改变set操作,在pushdown的时候,先考虑set标记再弄rev标记,这也是很好理解的,因为一旦rev和set共存,肯定是rev在set后面。
有几个细节要注意一下,一开始行云流水一气呵成,发现还是WA了,就是这几个地方,
1.除了set的时候强制给rev弄成0,其他任何时候对rev标记操作都是^1,取反,这个也很好理解,之前在pushdown里面我就是直接传值,肯定不对嘛
2.在pushdown里面的set下传操作也要记得把子树的rev标记抹除,一开始只在主修改函数里写了,这里没写,WA的不明不白,理由跟上面的一样
然后就基本上没问题了
#include <iostream> #include <cstdio> #include <cstring> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r using namespace std; const int N=100000+10; int d[N*3],maxc[N*3],lc[N*3],rc[N*3],maxc0[N*3],lc0[N*3],rc0[N*3]; int sets[N*3],rev[N*3]; int n,Q; int A[N]; void up(int rt,int l,int r) { int mid=(l+r)>>1; d[rt]=d[rt<<1]+d[rt<<1|1]; maxc[rt]=max(maxc[rt<<1],maxc[rt<<1|1]); maxc[rt]=max(maxc[rt],lc[rt<<1|1]+rc[rt<<1]); lc[rt]=lc[rt<<1]; rc[rt]=rc[rt<<1|1]; if (lc[rt<<1]==mid-l+1) lc[rt]+=lc[rt<<1|1]; if (rc[rt<<1|1]==r-mid) rc[rt]+=rc[rt<<1]; maxc0[rt]=max(maxc0[rt<<1],maxc0[rt<<1|1]); maxc0[rt]=max(maxc0[rt],lc0[rt<<1|1]+rc0[rt<<1]); lc0[rt]=lc0[rt<<1]; rc0[rt]=rc0[rt<<1|1]; if (lc0[rt<<1]==mid-l+1) lc0[rt]+=lc0[rt<<1|1]; if (rc0[rt<<1|1]==r-mid) rc0[rt]+=rc0[rt<<1]; } void build(int rt,int l,int r) { sets[rt]=-1; rev[rt]=0; if (l>=r){ d[rt]=maxc[rt]=A[l]; lc[rt]=rc[rt]=A[l]; lc0[rt]=rc0[rt]=maxc0[rt]=1-A[l]; return; } int mid=(l+r)>>1; build(lson); build(rson); up(rt,l,r); } void pushdown(int rt,int l,int r) { if (l>=r) return; int mid=(l+r)>>1; if (sets[rt]>=0){ maxc[rt<<1]=lc[rt<<1]=rc[rt<<1]=d[rt<<1]=(mid-l+1)*sets[rt]; maxc[rt<<1|1]=lc[rt<<1|1]=rc[rt<<1|1]=d[rt<<1|1]=(r-mid)*sets[rt]; maxc0[rt<<1]=lc0[rt<<1]=rc0[rt<<1]=(mid-l+1)*(1-sets[rt]); maxc0[rt<<1|1]=lc0[rt<<1|1]=rc0[rt<<1|1]=(r-mid)*(1-sets[rt]); sets[rt<<1]=sets[rt<<1|1]=sets[rt]; rev[rt<<1]=rev[rt<<1|1]=0; sets[rt]=-1; } if (rev[rt]>0){ d[rt<<1]=(mid-l+1)-d[rt<<1]; d[rt<<1|1]=(r-mid)-d[rt<<1|1]; int t1,t2,t3; t1=maxc[rt<<1];t2=lc[rt<<1];t3=rc[rt<<1]; maxc[rt<<1]=maxc0[rt<<1]; lc[rt<<1]=lc0[rt<<1]; rc[rt<<1]=rc0[rt<<1]; maxc0[rt<<1]=t1; lc0[rt<<1]=t2; rc0[rt<<1]=t3; t1=maxc[rt<<1|1];t2=lc[rt<<1|1];t3=rc[rt<<1|1]; maxc[rt<<1|1]=maxc0[rt<<1|1]; lc[rt<<1|1]=lc0[rt<<1|1]; rc[rt<<1|1]=rc0[rt<<1|1]; maxc0[rt<<1|1]=t1; lc0[rt<<1|1]=t2; rc0[rt<<1|1]=t3; rev[rt<<1]^=1; rev[rt<<1|1]^=1; rev[rt]=0; } } void change(int val,int L,int R,int rt,int l,int r) { if (L<=l && r<=R){ d[rt]=(r-l+1)*val; lc[rt]=rc[rt]=(r-l+1)*val; maxc[rt]=(r-l+1)*val; lc0[rt]=rc0[rt]=maxc0[rt]=(r-l+1)*(1-val); sets[rt]=val; rev[rt]=0; return; } pushdown(rt,l,r); int mid=(l+r)>>1; if (L>mid) change(val,L,R,rson); else if (R<=mid) change(val,L,R,lson); else{ change(val,L,R,rson); change(val,L,R,lson); } up(rt,l,r); } void revers(int L,int R,int rt,int l,int r) { if (L<=l && r<=R) { d[rt]=(r-l+1)-d[rt]; int t1,t2,t3; t1=maxc[rt];t2=lc[rt];t3=rc[rt]; maxc[rt]=maxc0[rt];lc[rt]=lc0[rt];rc[rt]=rc0[rt]; maxc0[rt]=t1;lc0[rt]=t2;rc0[rt]=t3; rev[rt]^=1; return; } pushdown(rt,l,r); int mid=(l+r)>>1; if (R<=mid) revers(L,R,lson); else if (L>mid) revers(L,R,rson); else { revers(L,R,lson); revers(L,R,rson); } up(rt,l,r); } int output(int op,int L,int R,int rt,int l,int r) { if (L==l && r==R){ if (op==3) return d[rt]; else return maxc[rt]; } pushdown(rt,l,r); int mid=(l+r)>>1; if (L>mid) return output(op,L,R,rson); else if (R<=mid) return output(op,L,R,lson); else { int ret1=output(op,L,mid,lson); int ret2=output(op,mid+1,R,rson); if (op==3) return ret1+ret2; else{ int ret=max(ret1,ret2); int t1=min(rc[rt<<1],mid-L+1); int t2=min(lc[rt<<1|1],R-mid); ret=max(ret,t1+t2); return ret; } } } int main() { int t,op,a,b; scanf("%d",&t); while (t--) { scanf("%d%d",&n,&Q); for (int i=1;i<=n;i++) scanf("%d",&A[i]); build(1,1,n); while (Q--) { scanf("%d%d%d",&op,&a,&b); a++;b++; if (op<=1){ change(op,a,b,1,1,n); } else if (op==2){ revers(a,b,1,1,n); } else { int ans=output(op,a,b,1,1,n); printf("%d\n",ans); } } } return 0; }
HDU 3397 线段树 双懒惰标记,布布扣,bubuko.com
原文:http://www.cnblogs.com/kkrisen/p/3864311.html