[cpp] /********************************************** 題目大意： 0 a b將區間[a,b]所有數全部變成0 1 a b將區間[a,b]所有數全部變成1 2 a b將區間[a,b]中所有數0 1互換，0變1,1變0 3 a b輸出區間[a,b]中1的個數 4 a b輸出區間[a,b]中最長連續1的個數 算法分析： 涉及到線段樹的多種操作; 0,1兩種操作可以合並到一起寫; 0,1互換即線段樹的異或操作; 查詢區間最長連續1個數的過程中; maxl=[l,m]上最長連續1個數; maxl=[m+1,r]上最長連續1的個數; maxm=min(m-l+1,左孩子的rs)+min(r-m,右孩子的ls); 結果應該是這三個中的最大值,即max(maxl,maxr,maxm); 其中查詢操作和pku3667類似; ***********************************************/ #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<climits> #include<algorithm> using namespace std; #define L l,m,u<<1 #define R m+1,r,u<<1|1 const int N =100010; struct node { int l,r; int ls,ms,rs;//ls左邊最長連續1數量;ms:最長連續1數量;rs:右邊最長連續1數量; int flag;//01狀態 int total;//區間1的總數 } t[N*3]; int len(int u) { return t[u].r-t[u].l+1; } int mid(int u) { return (t[u].l+t[u].r)>>1; } void PushUp(int u,int x)//把當前結點的信息更新到父結點 { t[u].ls=t[u].ms=t[u].rs=t[u].total=x*(t[u].r-t[u].l+1); t[u].flag=x; } void build(int l,int r,int u)//建樹 { t[u].l=l; t[u].r=r; t[u].ls=t[u].rs=t[u].ms=t[u].total=t[u].flag=0; if(l==r) return; int m=mid(u); build(L); build(R); } void PushUp(int u)//把當前結點的信息更新到父結點 { t[u].flag=(t[u<<1].flag==t[u<<1|1].flag?t[u<<1].flag:-1);//更新狀態 t[u].ls=t[u<<1].ls+((t[u<<1].ls==len(u<<1))?t[u<<1|1].ls:0);//更新左 t[u].rs=t[u<<1|1].rs+((t[u<<1|1].rs==len(u<<1|1))?t[u<<1].rs:0);//更新右 t[u].ms=max(t[u<<1].rs+t[u<<1|1].ls,max(t[u<<1].ms,t[u<<1|1].ms));//更新整體 t[u].total=t[u<<1].total+t[u<<1|1].total;//更新1的總數 } void update(int l,int r,int u,int x)//更新區間[l,r]0、1狀態 { if(t[u].flag==x) return; if(t[u].l==l&&t[u].r==r) { PushUp(u,x); return; } if(t[u].flag>=0) { PushUp(u<<1,t[u].flag); PushUp(u<<1|1,t[u].flag); t[u].flag=-1; } int m=mid(u); if(r<=m) { update(l,r,u<<1,x); } else if(l>m) { update(l,r,u<<1|1,x); } else { update(L,x); update(R,x); } PushUp(u); } void swap(int l,int r,int u)//[l,r]0、1交換 { if(t[u].l>=l&&t[u].r<=r&&(t[u].flag==0||t[u].flag==1)) { int x=t[u].flag^1; PushUp(u,x); return; } if(t[u].flag>=0) { PushUp(u<<1,t[u].flag); PushUp(u<<1|1,t[u].flag); } int m=mid(u); if(r<=m) { swap(l,r,u<<1); } else if(l>m) { swap(l,r,u<<1|1); } else { swap(L); swap(R); } PushUp(u); } int find1(int l,int r,int u)//找區間[l,r]內的1的個數 { if(t[u].l==l&&t[u].r==r) { return t[u].total; } if(t[u].flag>=0) { PushUp(u<<1,t[u].flag); PushUp(u<<1|1,t[u].flag); } int m=mid(u); if(r<=m) { return find1(l,r,u<<1); } else if(l>m) { return find1(l,r,u<<1|1); } else { return find1(L)+find1(R); } } int find2(int l,int r,int u)//找區間[l,r]內最長連續1的個數 { if(t[u].l==l&&t[u].r==r) { return t[u].ms; } if(t[u].flag>=0) { PushUp(u<<1,t[u].flag); PushUp(u<<1|1,t[u].flag); } int m=mid(u); if(r<=m) { return find2(l,r,u<<1); } else if(l>m) { return find2(l,r,u<<1|1); } else { int maxl=find2(L);//[l,m]上最長連續1個數 int maxr=find2(R);//[m+1,r]上最長連續1個數 int maxm=min(m-l+1,t[u<<1].rs)+min(r-m,t[u<<1|1].ls);//min(m-l+1,左孩子的rs)+min（r-m,右孩子的ls）, return max(maxm,max(maxl,maxr)); } } int main() { //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin); int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); build(0,n-1,1); for(int i=0; i<n; i++) { int x; scanf("%d",&x); if(x) update(i,i,1,x); } for(int i=0; i<m; i++) { int op,a,b; scanf("%d%d%d",&op,&a,&b); if(op==0||op==1) update(a,b,1,op); else if(op==2) swap(a,b,1); else if(op==3) printf("%d\n",find1(a,b,1)); else if(op==4) printf("%d\n",find2(a,b,1)); } } return 0; }
