Problem Description
lxhgww got a sequence contains n characters which are all '0's or '1's.
We have five operations here:
Change operations:
0 a b change all characters into '0's in [a , b]
1 a b change all characters into '1's in [a , b]
2 a b change all '0's into '1's and change all '1's into '0's in [a, b]
Output operations:
3 a b output the number of '1's in [a, b]
4 a b output the length of the longest continuous '1' string in [a , b]
We have five operations here:
Change operations:
0 a b change all characters into '0's in [a , b]
1 a b change all characters into '1's in [a , b]
2 a b change all '0's into '1's and change all '1's into '0's in [a, b]
Output operations:
3 a b output the number of '1's in [a, b]
4 a b output the length of the longest continuous '1' string in [a , b]
典型的水题，对一段01序列进行区间覆盖和反转，维护1的个数，连续1的个数，前缀1的个数，后缀1的个数，以及连续0，前缀0，后缀0，用来计算反转时的1.
不过还是写错了个地方，在程序里面标记出来了。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring> #define lc po*2
#define rc po*2+1
#define lson L,M,lc
#define rson M+1,R,rc using namespace std; const int maxn=1e5+; int sum[maxn*],lsum[][maxn*],rsum[][maxn*],msum[][maxn*];
int COL[maxn*],XOR[maxn*]; inline void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
} void pushUP(int po,int len)
{
sum[po]=sum[lc]+sum[rc]; for(int i=;i<;++i)
{
msum[i][po]=max(msum[i][lc],msum[i][rc]);
msum[i][po]=max(msum[i][po],lsum[i][rc]+rsum[i][lc]); lsum[i][po]=lsum[i][lc];
if(lsum[i][lc]==(len-(len/)))
lsum[i][po]+=lsum[i][rc]; rsum[i][po]=rsum[i][rc];
if(rsum[i][rc]==(len/))
rsum[i][po]+=rsum[i][lc];
}
} void pushDown(int po,int len)
{
if(COL[po]!=-)
{
COL[lc]=COL[rc]=COL[po];
XOR[lc]=XOR[rc]=; sum[lc]=COL[po]*(len-(len/));
sum[rc]=COL[po]*(len/); for(int i=;i<;++i)
{
msum[i][lc]=lsum[i][lc]=rsum[i][lc]=(i ? sum[lc] : len-(len/)-sum[lc]);
msum[i][rc]=rsum[i][rc]=lsum[i][rc]=(i ? sum[rc] : (len/)-sum[rc]);
} COL[po]=-;
} if(XOR[po])
{
XOR[lc]=!XOR[lc];
XOR[rc]=!XOR[rc]; sum[lc]=len-(len/)-sum[lc];
sum[rc]=(len/)-sum[rc]; swap(msum[][lc],msum[][lc]);
swap(msum[][rc],msum[][rc]); swap(lsum[][lc],lsum[][lc]);
swap(rsum[][lc],rsum[][lc]); swap(lsum[][rc],lsum[][rc]);
swap(rsum[][rc],rsum[][rc]); XOR[po]=;
}
} void build_tree(int L,int R,int po)
{
COL[po]=-;
XOR[po]=; if(L==R)
{
int temp;
scanf("%d",&temp); sum[po]=temp;
lsum[][po]=rsum[][po]=msum[][po]=-temp;
lsum[][po]=rsum[][po]=msum[][po]=temp; return;
} int M=(L+R)/; build_tree(lson);
build_tree(rson); pushUP(po,R-L+);
} void update_col(int ul,int ur,int ut,int L,int R,int po)
{
if(ul<=L&&ur>=R)
{
COL[po]=ut;
XOR[po]=; sum[po]=ut*(R-L+);
lsum[][po]=rsum[][po]=msum[][po]=sum[po];
lsum[][po]=rsum[][po]=msum[][po]=R-L+-sum[po]; return;
} pushDown(po,R-L+); int M=(L+R)/; if(ul<=M)
update_col(ul,ur,ut,lson);
if(ur>M)
update_col(ul,ur,ut,rson); pushUP(po,R-L+);
} void update_xor(int ul,int ur,int L,int R,int po)
{
if(ul<=L&&ur>=R)
{
XOR[po]=!XOR[po]; sum[po]=R-L+-sum[po];
swap(msum[][po],msum[][po]);
swap(lsum[][po],lsum[][po]);
swap(rsum[][po],rsum[][po]); return;
} pushDown(po,R-L+); int M=(L+R)/; if(ul<=M)
update_xor(ul,ur,lson);
if(ur>M)
update_xor(ul,ur,rson); pushUP(po,R-L+);
} int query_sum(int ql,int qr,int L,int R,int po)
{
if(ql<=L&&qr>=R)
return sum[po]; pushDown(po,R-L+); int M=(L+R)/; if(qr<=M)
return query_sum(ql,qr,lson);
if(ql>M)
return query_sum(ql,qr,rson); return query_sum(ql,qr,lson)+query_sum(ql,qr,rson);
} int query_max(int ql,int qr,int L,int R,int po)
{
if(ql<=L&&qr>=R)
return msum[][po]; pushDown(po,R-L+); int M=(L+R)/;
int ans=; if(qr<=M)
return query_max(ql,qr,lson);
if(ql>M)
return query_max(ql,qr,rson); ans=max(query_max(ql,qr,lson),query_max(ql,qr,rson));
ans=max(ans,min(rsum[][lc],M-ql+)+min(lsum[][rc],qr-M)); //!!! return ans;
} int main()
{
int T;
int N,M;
int a,b,c;
cin>>T; while(T--)
{
scanf("%d %d",&N,&M); build_tree(,N-,); while(M--)
{
scanf("%d %d %d",&a,&b,&c); switch(a)
{
case :
update_col(b,c,,,N-,);
break;
case :
update_col(b,c,,,N-,);
break;
case :
update_xor(b,c,,N-,);
break;
case :
printf("%d\n",query_sum(b,c,,N-,));
break;
case :
printf("%d\n",query_max(b,c,,N-,));
break;
}
}
} return ;
}