歡迎訪問~原文出處——博客園-zhouzhendong

去博客園看該題解

---

題目傳送門 - BZOJ1858

---

題意概括

　　lxhgww最近收到了一個01序列，序列里面包含了n個數，這些數要么是0，要么是1，現在對于這個序列有五種變換操作和詢問操作：0 a b把[a,b]區間內的所有數全變成 0,1 a b把[a,b]區間內的所有數全變成1,2 a b 把[a,b]區間內的所有數全部取反，也就是說把所有的0變成1，把所有的1變成0,3 a b詢問[a,b]區間內總共 有多少個1,4 a b詢問[a,b]區間內最多有多少個連續的1,對于每一種詢問操作，lxhgww都需要給出回答

---

題解

　　是一題暴力的線段樹！

　　總共除了1的總個數之外，還要維護6個量，分別是(當前區間內)從左開始連續的0的個數，從又開始連續的0的個數，區間內最長的連續的0的個數；同理，1也有3個。這題多打幾個子程序是縮減代碼量的好方法，這樣便于查找錯誤。這題真的拼仔細！

---

代碼

#include <cstring> #include <cstdio> int n,m,ra[101000],op,a,b; int max2(int a,int b){return a>b?a:b;} int max3(int a,int b,int c){return max2(max2(a,b),c);} struct Segtree{int tot,add,t100,t101,t110,t000,t001,t010,le,ri,si;void set(int l,int r){tot=t100=t101=t110=t000=t001=t010=0;add=-1,le=l,ri=r,si=ri-le+1;} }t[101000*4]; void swap(int &a,int &b){int c=a;a=b,b=c; } void pushup(int rt){int ls=rt*2,rs=rt*2+1;t[rt].tot=t[ls].tot+t[rs].tot;t[rt].t110=t[ls].t110;if (t[ls].t110==t[ls].si)t[rt].t110+=t[rs].t110;t[rt].t101=t[rs].t101;if (t[rs].t101==t[rs].si)t[rt].t101+=t[ls].t101;t[rt].t100=max3(t[ls].t101+t[rs].t110,t[ls].t100,t[rs].t100);t[rt].t010=t[ls].t010;if (t[ls].t010==t[ls].si)t[rt].t010+=t[rs].t010;t[rt].t001=t[rs].t001;if (t[rs].t001==t[rs].si)t[rt].t001+=t[ls].t001;t[rt].t000=max3(t[ls].t001+t[rs].t010,t[ls].t000,t[rs].t000); } void build(int rt,int le,int ri){t[rt].add=-1,t[rt].le=le,t[rt].ri=ri,t[rt].si=ri-le+1;if (le==ri){t[rt].tot=t[rt].t101=t[rt].t110=ra[le];t[rt].t001=t[rt].t010=!ra[le];return;}int mid=(le+ri)/2,ls=rt*2,rs=rt*2+1;build(ls,le,mid);build(rs,mid+1,ri);pushup(rt); } void pushnew(int rt,int op){if (op<2)t[rt].add=op;else if (t[rt].add==-1)t[rt].add=2;else if (t[rt].add==2)t[rt].add=-1;elset[rt].add=!t[rt].add;if (op==0)t[rt].tot=t[rt].t100=t[rt].t101=t[rt].t110=0,t[rt].t000=t[rt].t010=t[rt].t001=t[rt].si;else if (op==1)t[rt].tot=t[rt].t100=t[rt].t101=t[rt].t110=t[rt].si,t[rt].t000=t[rt].t010=t[rt].t001=0;else if (op==2){t[rt].tot=t[rt].si-t[rt].tot;swap(t[rt].t000,t[rt].t100);swap(t[rt].t010,t[rt].t110);swap(t[rt].t001,t[rt].t101);} } void pushdown(int rt){if (t[rt].add!=-1){pushnew(rt*2,t[rt].add);pushnew(rt*2+1,t[rt].add);t[rt].add=-1;} } void update(int rt,int le,int ri,int xle,int xri,int op){if (le>xri||ri<xle)return;if (xle<=le&&ri<=xri){pushnew(rt,op);return;}pushdown(rt);int mid=(le+ri)/2;update(rt*2,le,mid,xle,xri,op);update(rt*2+1,mid+1,ri,xle,xri,op);pushup(rt); } int querytot(int rt,int le,int ri,int xle,int xri){if (le>xri||ri<xle)return 0;if (xle<=le&&ri<=xri)return t[rt].tot;pushdown(rt);int mid=(le+ri)/2;return querytot(rt*2,le,mid,xle,xri)+querytot(rt*2+1,mid+1,ri,xle,xri); } Segtree query(int rt,int le,int ri,int xle,int xri){Segtree ans;ans.set(le,ri);if (le>xri||ri<xle)return ans;if (xle<=le&&ri<=xri)return t[rt];pushdown(rt);int mid=(le+ri)/2;Segtree ls=query(rt*2,le,mid,xle,xri),rs=query(rt*2+1,mid+1,ri,xle,xri);ans.t110=ls.t110;if (ls.t110==ls.si)ans.t110+=rs.t110;ans.t101=rs.t101;if (rs.t101==rs.si)ans.t101+=ls.t101;ans.t100=max3(ls.t101+rs.t110,ls.t100,rs.t100);ans.t010=ls.t010;if (ls.t010==ls.si)ans.t010+=rs.t010;ans.t001=rs.t001;if (rs.t001==rs.si)ans.t001+=ls.t001;ans.t000=max3(ls.t001+rs.t010,ls.t000,rs.t000);return ans; } int queryans(int a,int b){Segtree tt=query(1,1,n,a,b);return max3(tt.t100,tt.t101,tt.t110); } int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)scanf("%d",&ra[i]);build(1,1,n);for (int i=1;i<=m;i++){scanf("%d%d%d",&op,&a,&b);a++,b++;if (op<3)update(1,1,n,a,b,op);else if (op==3)printf("%d\n",querytot(1,1,n,a,b));else if (op==4){printf("%d\n",queryans(a,b));}} return 0; }

　　

轉載于:https://www.cnblogs.com/zhouzhendong/p/BZOJ1858.html

總結

以上是生活随笔為你收集整理的BZOJ1858 [Scoi2010]序列操作 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

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