题目大意：
有一个01序列，现在对于这个序列有五种变换操作和询问操作： 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。
思路：
维护每一段数的和、左端和右端以及整段中连续的0和1的长度，并使用标记进行下传。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define N 400000 5 using namespace std; 6 7 int root,num,cnt,lmax[2][N],rmax[2][N],mmax[2][N],sum[N],tag[2][N],rev[N],h[N],t[N],rc[N],lc[N],a[N]; 8 9 void up_date(int x,int k) 10 { 11 int l=lc[x],r=rc[x]; 12 lmax[k][x]=lmax[k][l],rmax[k][x]=rmax[k][r]; 13 if (lmax[k][l]==t[l]-h[l]+1) lmax[k][x]+=lmax[k][r]; 14 if (rmax[k][r]==t[r]-h[r]+1) rmax[k][x]+=rmax[k][l]; 15 mmax[k][x]=max(max(mmax[k][l],mmax[k][r]),rmax[k][l]+lmax[k][r]); 16 } 17 18 void build(int l,int r,int &cur) 19 { 20 cur=++num,tag[0][cur]=tag[1][cur]=rev[cur]=0; 21 h[cur]=l,t[cur]=r; 22 if (l==r) 23 { 24 lc[cur]=rc[cur]=0; 25 lmax[0][cur]=rmax[0][cur]=mmax[0][cur]=(a[l]==0); 26 lmax[1][cur]=rmax[1][cur]=sum[cur]=mmax[1][cur]=(a[r]==1); 27 return; 28 } 29 int mid=l+r>>1; 30 build(l,mid,lc[cur]),build(mid+1,r,rc[cur]); 31 up_date(cur,0),up_date(cur,1),sum[cur]=sum[lc[cur]]+sum[rc[cur]]; 32 } 33 34 void mark(int x,int k) 35 { 36 tag[k][x]=1,tag[k^1][x]=rev[x]=0,sum[x]=(t[x]-h[x]+1)*k; 37 lmax[k][x]=rmax[k][x]=mmax[k][x]=t[x]-h[x]+1; 38 lmax[k^1][x]=rmax[k^1][x]=mmax[k^1][x]=0; 39 } 40 41 void re(int x) 42 { 43 rev[x]^=1,sum[x]=t[x]-h[x]+1-sum[x]; 44 swap(lmax[0][x],lmax[1][x]),swap(rmax[0][x],rmax[1][x]),swap(mmax[0][x],mmax[1][x]); 45 } 46 47 void push_down(int x) 48 { 49 if (tag[0][x]) mark(lc[x],0),mark(rc[x],0),tag[0][x]=0; 50 if (tag[1][x]) mark(lc[x],1),mark(rc[x],1),tag[1][x]=0; 51 if (rev[x]) re(lc[x]),re(rc[x]),rev[x]=0; 52 } 53 54 void change(int l,int r,int cur,int k) 55 { 56 if (h[cur]>r || t[cur]<l) return; 57 if (h[cur]>=l && t[cur]<=r) 58 { 59 if (k<2) mark(cur,k); 60 else re(cur); 61 return; 62 } 63 push_down(cur); 64 change(l,r,lc[cur],k),change(l,r,rc[cur],k); 65 up_date(cur,0),up_date(cur,1),sum[cur]=sum[lc[cur]]+sum[rc[cur]]; 66 } 67 68 int ask1(int l,int r,int cur) 69 { 70 if (h[cur]>r || t[cur]<l) return 0; 71 if (h[cur]>=l && t[cur]<=r) return sum[cur]; 72 push_down(cur); 73 return ask1(l,r,lc[cur])+ask1(l,r,rc[cur]); 74 } 75 76 int ask2(int l,int r,int cur) 77 { 78 if (l==h[cur] && r==t[cur]) return cur; 79 int mid=h[cur]+t[cur]>>1; 80 push_down(cur); 81 if (r<=mid) return ask2(l,r,lc[cur]); 82 else if (l>mid) return ask2(l,r,rc[cur]); 83 else 84 { 85 int ans=++cnt; 86 lc[ans]=ask2(l,mid,lc[cur]),rc[ans]=ask2(mid+1,r,rc[cur]); 87 up_date(ans,0),up_date(ans,1),sum[ans]=sum[lc[ans]]+sum[rc[ans]]; 88 return ans; 89 } 90 } 91 92 int main() 93 { 94 int n,m,i,x,y,z; 95 scanf("%d%d",&n,&m); 96 for (i=1;i<=n;i++) scanf("%d",&a[i]); 97 build(1,n,root); 98 for (i=1;i<=m;i++) 99 { 100 scanf("%d%d%d",&z,&x,&y); 101 x++,y++; 102 if (z==3) printf("%d\n",ask1(x,y,root)); 103 else if (z==4) cnt=num,printf("%d\n",mmax[1][ask2(x,y,root)]); 104 else change(x,y,root,z); 105 } 106 return 0; 107 }
转载于:https://www.cnblogs.com/HHshy/p/5733992.html
相关资源：JAVA上百实例源码以及开源项目