這個是去年遺留歷史問題，之前思路混亂，搞了好多發(fā)都是WA，就沒做了

自從上次做了大白書上那個雙重懶惰標記的題目，做這個就思路很清晰了

跟上次大白上那個差不多，這個也是有一個sets標記，代表這個區(qū)間全部置為0或者1，沒有置位的時候為-1

還有個rev標記，代表翻轉操作，0代表當前不翻，1代表當前翻

要注意一下優(yōu)先級，發(fā)現(xiàn)有不同的弄法，我是這個弄得，有set操作的時候，set標記設值，并把當前節(jié)點的rev標記設為0，因為不管要不要rev，當前set操作肯定直接覆蓋了

rev操作不改變set操作，在pushdown的時候，先考慮set標記再弄rev標記，這也是很好理解的，因為一旦rev和set共存，肯定是rev在set后面。

有幾個細節(jié)要注意一下，一開始行云流水一氣呵成，發(fā)現(xiàn)還是WA了，就是這幾個地方，

1.除了set的時候強制給rev弄成0，其他任何時候對rev標記操作都是^1,取反，這個也很好理解，之前在pushdown里面我就是直接傳值，肯定不對嘛

2.在pushdown里面的set下傳操作也要記得把子樹的rev標記抹除，一開始只在主修改函數(shù)里寫了，這里沒寫，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);elseif (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);elseif (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);elseif (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);}elseif (op==2){revers(a,b,1,1,n);}else{int ans=output(op,a,b,1,1,n);printf("%d\n",ans);}}}return 0; }

　　

轉載于:https://www.cnblogs.com/kkrisen/p/3864311.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的HDU 3397 线段树 双懒惰标记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。