题意:
lxhgww 最近收到了一个 01 序列,序列里面包含了 n 个数,下标从 0 开始。这些数要么是 0,要么是 1,现在对于这个序列有五种变换操作和询问操作:
0 l r
把 [l,r] 区间内的所有数全变成 0
1 l r
把 [l,r] 区间内的所有数全变成 1
2 l r
把 [l,r] 区间内的所有数全部取反,也就是说把所有的 0 变成 1,把所有的 1 变成 0
3 l r
询问 [l,r] 区间内总共有多少个 1
4 l r
询问 [l,r] 区间内最多有多少个连续的 1
对于每一种询问操作,lxhgww 都需要给出回答,聪明的程序员们,你们能帮助他吗?
题解:
这题其实就是一道线段树的基础应用题,只不过代码稍稍有点长。
本题只需要维护0/1的个数,左边和右边最长连续0/1的个数,总的最大的0/1的个数。取反操作就是把上述维护的值0/1互换,其余的直接修改。
注意细节,难度并不大。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,m,s[100002],op,a,b,ans,maxr;
typedef struct{
int sum0,sum1,lef0,lef1,righ0,righ1,max0,max1;
int f1;bool f2;
}P;
P p[400002];
void hb(int root,int begin,int end,int mid){
p[root].sum0=p[root*2].sum0+p[root*2+1].sum0;
p[root].sum1=p[root*2].sum1+p[root*2+1].sum1;
if (p[root*2].lef0==mid-begin+1)p[root].lef0=p[root*2].lef0+p[root*2+1].lef0;
else p[root].lef0=p[root*2].lef0;
if (p[root*2].lef1==mid-begin+1)p[root].lef1=p[root*2].lef1+p[root*2+1].lef1;
else p[root].lef1=p[root*2].lef1;
if (p[root*2+1].righ0==end