題目鏈接：點(diǎn)擊查看

題目大意：給定一個(gè)初始的數(shù)列，然后依次進(jìn)行m次操作：

0 a b：將閉區(qū)間[a,b]內(nèi)的點(diǎn)都變?yōu)?

1 a b：將閉區(qū)間[a,b]內(nèi)的點(diǎn)都變?yōu)?

2 a b：將閉區(qū)間[a,b]內(nèi)的點(diǎn)1變?yōu)?,0變?yōu)?（相當(dāng)于取異或）

3 a b：查詢閉區(qū)間[a,b]內(nèi)有多少個(gè)1

4 a b：查詢閉區(qū)間[a,b]內(nèi)的最大連續(xù)的1的長(zhǎng)度

題目分析：操作1、2、4是最簡(jiǎn)單的線段樹操作，區(qū)間更新，區(qū)間查詢，操作3、5是進(jìn)階一點(diǎn)的線段樹操作，即區(qū)間合并，這兩類操作分著做就十分簡(jiǎn)單了，寫上模板只要不出錯(cuò)就沒問題，但是如果這兩類問題結(jié)合到一起，就要考慮lazy標(biāo)記的次序問題了，這就涉及到這兩個(gè)lazy標(biāo)記之間的關(guān)系了，為了方便講解，區(qū)間和覆蓋的lazy標(biāo)記下面我就稱為lazy，取異或的lazy標(biāo)記下面我稱為xor：

首先，覆蓋lazy的優(yōu)先級(jí)要大于異或xor，如果該區(qū)間被覆蓋了，那么他之前的異或標(biāo)記xor將清零，如果之前不管經(jīng)過了多少操作，只要本次操作是覆蓋，那么之前的所有操作都可以視為無效。

相對(duì)的，如果之前都是覆蓋操作，而本次操作是異或，則子區(qū)間段接下來都需要異或處理才行。

綜上所述，lazy的優(yōu)先級(jí)大于xor，更新lazy的同時(shí)記得清空xor，下傳lazy的同時(shí)記得清空子區(qū)間的xor，更新和下傳xor的時(shí)候不影響lazy，這樣實(shí)現(xiàn)每一個(gè)步驟就能實(shí)現(xiàn)這個(gè)題目了，一定一定要注意細(xì)節(jié)，也要同時(shí)注意一下封裝，因?yàn)榉庋b起來肯定用起來比較方便，而手寫很容易不小心寫錯(cuò)，調(diào)試的時(shí)候就難受了，上代碼了：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> #define ls (k<<1) #define rs (k<<1|1) using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Node {int l,r;int lazy,x_or;int l1,r1,all1;int l0,r0,all0;int sum1;int cal_len(){return r-l+1;}int mid(){return l+r>>1;} }tree[N<<2];void pushup(int k) {tree[k].sum1=tree[ls].sum1+tree[rs].sum1;tree[k].l0=tree[ls].l0;tree[k].r0=tree[rs].r0;if(tree[k].l0==tree[ls].cal_len())tree[k].l0+=tree[rs].l0;if(tree[k].r0==tree[rs].cal_len())tree[k].r0+=tree[ls].r0;tree[k].all0=max(max(tree[ls].all0,tree[rs].all0),tree[ls].r0+tree[rs].l0);tree[k].l1=tree[ls].l1;tree[k].r1=tree[rs].r1;if(tree[k].l1==tree[ls].cal_len())tree[k].l1+=tree[rs].l1;if(tree[k].r1==tree[rs].cal_len())tree[k].r1+=tree[ls].r1;tree[k].all1=max(max(tree[ls].all1,tree[rs].all1),tree[ls].r1+tree[rs].l1); }void XOR(int k) {swap(tree[k].l1,tree[k].l0);swap(tree[k].r1,tree[k].r0);swap(tree[k].all1,tree[k].all0);tree[k].sum1=tree[k].cal_len()-tree[k].sum1; }void pushdown(int k) {if(tree[k].lazy!=-1){tree[ls].lazy=tree[rs].lazy=tree[k].lazy;tree[ls].x_or=tree[rs].x_or=0;if(tree[k].lazy){tree[ls].l0=tree[ls].r0=tree[ls].all0=0;tree[rs].l0=tree[rs].r0=tree[rs].all0=0;tree[ls].sum1=tree[ls].cal_len();tree[rs].sum1=tree[rs].cal_len();tree[ls].l1=tree[ls].r1=tree[ls].all1=tree[ls].cal_len();tree[rs].l1=tree[rs].r1=tree[rs].all1=tree[rs].cal_len();}else{tree[ls].l0=tree[ls].r0=tree[ls].all0=tree[ls].cal_len();tree[rs].l0=tree[rs].r0=tree[rs].all0=tree[rs].cal_len();tree[ls].sum1=0;tree[rs].sum1=0;tree[ls].l1=tree[ls].r1=tree[ls].all1=0;tree[rs].l1=tree[rs].r1=tree[rs].all1=0;}tree[k].lazy=-1;}if(tree[k].x_or){tree[ls].x_or^=1;tree[rs].x_or^=1;tree[k].x_or=0;XOR(ls);XOR(rs);} }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].lazy=-1;tree[k].x_or=0;if(l==r){int num;scanf("%d",&num);tree[k].l1=tree[k].r1=tree[k].all1=tree[k].sum1=num;tree[k].l0=tree[k].r0=tree[k].all0=num^1;return;}int mid=tree[k].mid();build(ls,l,mid);build(rs,mid+1,r);pushup(k); }void update1(int k,int l,int r,int val) {if(tree[k].r<l||tree[k].l>r)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].lazy=val;tree[k].x_or=0;if(val){tree[k].l0=tree[k].r0=tree[k].all0=0;tree[k].sum1=tree[k].cal_len();tree[k].l1=tree[k].r1=tree[k].all1=tree[k].cal_len();}else{tree[k].l0=tree[k].r0=tree[k].all0=tree[k].cal_len();tree[k].sum1=0;tree[k].l1=tree[k].r1=tree[k].all1=0;}return;}pushdown(k);update1(ls,l,r,val);update1(rs,l,r,val);pushup(k); }void update2(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].x_or^=1;XOR(k);return;}pushdown(k);update2(ls,l,r);update2(rs,l,r);pushup(k); }int query1(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return 0;if(tree[k].l>=l&&tree[k].r<=r){return tree[k].sum1;}pushdown(k);return query1(ls,l,r)+query1(rs,l,r); }Node query2(int k,int l,int r) {if(tree[k].l>=l&&tree[k].r<=r){return tree[k];}pushdown(k);int mid=tree[k].mid();if(mid>=r)return query2(ls,l,r);else if(mid<l)return query2(rs,l,r);else{Node ans1,ans2,ans;ans1=query2(ls,l,r);ans2=query2(rs,l,r);ans.l1=ans1.l1;ans.r1=ans2.r1;if(ans.l1==ans1.r-ans1.l+1)ans.l1+=ans2.l1;if(ans.r1==ans2.r-ans2.l+1)ans.r1+=ans1.r1;ans.all1=max(max(ans1.all1,ans2.all1),ans1.r1+ans2.l1);return ans;} }void query(int k) {if(tree[k].l==tree[k].r){printf("%d ",tree[k].sum1);return;}pushdown(k);query(ls);query(rs); }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){int n,m;scanf("%d%d",&n,&m);build(1,1,n);while(m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);x++;y++;if(op==0){update1(1,x,y,0);}else if(op==1){update1(1,x,y,1);}else if(op==2){update2(1,x,y);}else if(op==3){printf("%d\n",query1(1,x,y));}else if(op==4){printf("%d\n",query2(1,x,y).all1);}}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 3397 Sequence operation(线段树+区间合并)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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