洛谷P2572 [SCOI2010] 序列操作

题目描述

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 都需要给出回答，聪明的程序员们，你们能帮助他吗？

  输入格式

  第一行两个正整数 n,m，表示序列长度与操作个数。

  
  （图片来源网络，侵删）

  第二行包括 n 个数，表示序列的初始状态。

  接下来 m 行，每行三个整数，表示一次操作。

  输出格式

  对于每一个询问操作，输出一行一个数，表示其对应的答案。

  输入输出样例

  输入 #1

  10 10
  0 0 0 1 1 0 1 0 1 1
  1 0 2
  3 0 5
  2 2 2
  4 0 4
  0 3 6
  2 3 7
  4 2 8
  1 0 5
  0 5 6
  3 3 9
  

  输出 #1

  5
  2
  6
  5

  说明/提示

  【数据范围】

  对于 30% 的数据，1≤n,m≤1000；

  对于100% 的数据，1≤n,m≤105。

  思路

  一看就是线段树

  将操作简化：

  操作0，1：区间改值，同时优先级最大，用正常的lazy标记下传即可，下传时将区间取反标记清空。

  操作2：区间取反，下传时若下区间有操作0，1的标记，将其取反，否则将已有的区间取反标记取反。

  操作3：区间求和，对线段树每一个节点维护一个sum值

  操作4：区间最长连续“1”，维护方法与维护最大字段和类似：分别记录

  max1l,max1r,max1n,max0l,max0r,max0n;

  表示必然包含左端点的最长连续“1”数目，必然包含右端点的最长连续“1”数目，最长连续“1”数目，必然包含左端点的最长连续“0”数目，必然包含右端点的最长连续“0”数目，最长连续“0”数目。

  #include
  using namespace std;
  struct Tree{
  	int l,r,lazy,sum,max1l,max1n,max1r,len,lazyq;
  	int max0l,max0n,max0r;
  }tree[4000010]; 
  int n,m;
  int a[1000010];
  inline void pushup(Tree &rt,Tree rl,Tree rr)
  {
  	rt.max1n=max(rl.max1n,max(rr.max1n,rl.max1r+rr.max1l));
  	rt.max0n=max(rl.max0n,max(rr.max0n,rl.max0r+rr.max0l));
  	if(rl.sum==rl.len) rt.max1l=rl.sum+rr.max1l;
  	else rt.max1l=rl.max1l;
  	if(rr.sum==rr.len) rt.max1r=rr.sum+rl.max1r;
  	else rt.max1r=rr.max1r;
  	if(!rl.sum) rt.max0l=rl.len+rr.max0l;
  	else rt.max0l=rl.max0l;
  	if(!rr.sum) rt.max0r=rr.len+rl.max0r;
  	else rt.max0r=rr.max0r;
  	rt.sum=rl.sum+rr.sum;
  	return;
  }
  inline void build(int rt,int l,int r)
  {
  	if(l==r)
  	{
  		tree[rt]=(Tree){l,r,-1,a[l],a[l],a[l],a[l],1,0,!a[l],!a[l],!a[l]};
  		return;
  	}
  	tree[rt]=(Tree){l,r};
  	int mid=(l+r)>>1;
  	build(rt