本文主要是介绍洛谷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<bits/stdc++.h>
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<<1,l,mid);build(rt<<1|1,mid+1,r);tree[rt].lazy=-1;tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;pushup(tree[rt],tree[rt<<1],tree[rt<<1|1]);
}
inline void downlazy(int rt)
{if(tree[rt].lazy==-1&&tree[rt].lazyq==0) return;int rl=rt<<1,rr=rt<<1|1;if(tree[rt].lazy!=-1){tree[rl].lazyq=tree[rr].lazyq=0;tree[rl].lazy=tree[rr].lazy=tree[rt].lazy;tree[rl].sum=tree[rl].max1n=tree[rl].max1l=tree[rl].max1r=tree[rl].len*tree[rt].lazy;tree[rr].sum=tree[rr].max1n=tree[rr].max1l=tree[rr].max1r=tree[rr].len*tree[rt].lazy;tree[rl].max0n=tree[rl].max0l=tree[rl].max0r=tree[rl].len*(!tree[rt].lazy);tree[rr].max0n=tree[rr].max0l=tree[rr].max0r=tree[rr].len*(!tree[rt].lazy);tree[rt].lazy=-1;}if(tree[rt].lazyq){if(tree[rl].lazy!=-1) tree[rl].lazy^=1;else tree[rl].lazyq^=1;if(tree[rr].lazy!=-1) tree[rr].lazy^=1;else tree[rr].lazyq^=1;tree[rl].sum=tree[rl].len-tree[rl].sum;tree[rr].sum=tree[rr].len-tree[rr].sum;swap(tree[rl].max0l,tree[rl].max1l);swap(tree[rl].max0n,tree[rl].max1n);swap(tree[rl].max0r,tree[rl].max1r);swap(tree[rr].max0l,tree[rr].max1l);swap(tree[rr].max0n,tree[rr].max1n);swap(tree[rr].max0r,tree[rr].max1r);tree[rt].lazyq=0;}
}
inline void change(int rt,int L,int R,int d)
{if(tree[rt].l>=L&&tree[rt].r<=R){tree[rt].lazy=d;tree[rt].lazyq=0;tree[rt].sum=tree[rt].max1n=tree[rt].max1l=tree[rt].max1r=tree[rt].len*tree[rt].lazy;tree[rt].max0n=tree[rt].max0l=tree[rt].max0r=tree[rt].len*(!tree[rt].lazy);return;}downlazy(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(L<=mid) change(rt<<1,L,R,d);if(R>mid) change(rt<<1|1,L,R,d);pushup(tree[rt],tree[rt<<1],tree[rt<<1|1]);
}
inline void update(int rt,int L,int R)
{if(tree[rt].l>=L&&tree[rt].r<=R){if(tree[rt].lazy!=-1) tree[rt].lazy^=1;else tree[rt].lazyq^=1;tree[rt].sum=tree[rt].len-tree[rt].sum;swap(tree[rt].max0l,tree[rt].max1l);swap(tree[rt].max0n,tree[rt].max1n);swap(tree[rt].max0r,tree[rt].max1r);return;}downlazy(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(L<=mid) update(rt<<1,L,R);if(R>mid) update(rt<<1|1,L,R);pushup(tree[rt],tree[rt<<1],tree[rt<<1|1]);
}
inline int qerry_1(int rt,int L,int R)
{if(tree[rt].l>=L&&tree[rt].r<=R) return tree[rt].sum;downlazy(rt);int mid=(tree[rt].l+tree[rt].r)>>1,ans=0;if(L<=mid) ans+=qerry_1(rt<<1,L,R);if(R>mid) ans+=qerry_1(rt<<1|1,L,R);pushup(tree[rt],tree[rt<<1],tree[rt<<1|1]);return ans;
}
inline Tree qerry_2(int rt,int L,int R)
{if(tree[rt].l>=L&&tree[rt].r<=R) return tree[rt];downlazy(rt);int mid=(tree[rt].l+tree[rt].r)>>1;Tree ans,l,r;ans=l=r=(Tree){0,0,-1,0,0,0,0,0,0,0,0};if(L<=mid) l=qerry_2(rt<<1,L,R);if(R>mid) r=qerry_2(rt<<1|1,L,R);pushup(ans,l,r);return ans;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);for(int i=1;i<=m;i++){int op,l,r;scanf("%d%d%d",&op,&l,&r);l++,r++;switch(op){case 0:case 1:{change(1,l,r,op);break;}case 2:{update(1,l,r);break;}case 3:{printf("%d\n",qerry_1(1,l,r));break;}case 4:{Tree ans=qerry_2(1,l,r);printf("%d\n",ans.max1n);break;}} } return 0;
}这篇关于洛谷P2572 [SCOI2010] 序列操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
