题目描述
lxhgww 最近收到了一个 01 序列, 序列里面包含了 n 个数, 这些数要么是 0, 要么是 1, 现在对于这个序列有五种变换操作和询问操作:
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
对于每一种询问操作, lxhgww 都需要给出回答, 聪明的程序员们, 你们能帮助他吗?
输入输出格式
输入格式:
输入数据第一行包括 2 个数, n 和 m, 分别表示序列的长度和操作数目
第二行包括 n 个数, 表示序列的初始状态
接下来 m 行, 每行 3 个数, op, a, b,(0<=op<=4,0<=a<=b<n)表示对于区间 [a, b] 执行标号为 op 的操作
输出格式:
对于每一个询问操作, 输出一行, 包括 1 个数, 表示其对应的答案
输入输出样例
输入样例 #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<=100000
看完这个题, 感觉对线段树的理解又加深了
根据题意和球最大字段和的经验, 我们一个结点应该保存 8 个信息, 才能进行合并
1 的个数
区间最长连续 1
区间从左边开始最长连续 1
区间从右边开始最长连续 1
行应的还有 0 的, 一共是八个, 因为交换的操作
注意的地方有两个, 区间的合并方式和标记下方的优先级
具体看码:
- #include<bits/stdc++.h>
- using namespace std;
- int n,q,a[100001];
- struct d{
- int w,b,lw,lb,rw,rb,mw,mb;
- d(int w=0,int b=0,int lw=0,int lb=0,int rw=0,int rb=0,int mw=0,int mb=0):
- w(w),b(b),lw(lw),lb(lb),rw(rw),rb(rb),mw(mw),mb(mb){}
- // 当写复杂的线段树的时候, 这种方式可以有效的减少代码量
- };
- inline d hb(d i,d j){
- return d(
- i.w+j.w, i.b+j.b,
- (i.b?i.lw:i.w+j.lw), (i.w?i.lb:i.b+j.lb),
- (j.b?j.rw:j.w+i.rw), (j.w?j.rb:j.b+i.rb),
- max(max(i.mw,j.mw),i.rw+j.lw),
- max(max(i.mb,j.mb),i.rb+j.lb));
- }
- d dat[262144]; int len[262144],tg1[262144],tg2[262144];
- inline void P(int i,int typ){
- d&t=dat[i];
- if(typ==0) tg2[i]= 0, tg1[i]=0, t=d(0,len[i],0,len[i],0,len[i],0,len[i]);
- if(typ==1) tg2[i]= 0, tg1[i]=1, t=d(len[i],0,len[i],0,len[i],0,len[i],0);
- if(typ==2) tg2[i]^=1, swap(t.w,t.b), swap(t.lw,t.lb), swap(t.rw,t.rb), swap(t.mw,t.mb);
- }
- inline void pd(int i){
- if(~tg1[i]) P(i<<1,tg1[i]), P(i<<1|1,tg1[i]);
- if(tg2[i]) P(i<<1,2), P(i<<1|1,2);
- tg1[i]=-1, tg2[i]=0;
- }
- void build(int i,int l,int r){
- len[i]=r-l+1; tg1[i]=-1;
- if(l==r) {int t=a[l]; dat[i]=d(t,t^1,t,t^1,t,t^1,t,t^1); return;}
- build(i<<1,l,l+r>>1);
- build(i<<1|1,(l+r>>1)+1,r);
- dat[i]=hb(dat[i<<1],dat[i<<1|1]);
- }
- void Mdf(int i,int l,int r,int a,int b,int t){
- if(b<l||r<a) return; if(a<=l&&r<=b) {P(i,t); return;}
- pd(i); Mdf(i<<1,l,l+r>>1,a,b,t), Mdf(i<<1|1,(l+r>>1)+1,r,a,b,t);
- dat[i]=hb(dat[i<<1],dat[i<<1|1]);
- }
- d Qur(int i,int l,int r,int a,int b){
- if(b<l||r<a) return d(); if(a<=l&&r<=b) return dat[i];
- pd(i); return hb(Qur(i<<1,l,l+r>>1,a,b),Qur(i<<1|1,(l+r>>1)+1,r,a,b));// 查询的操作也是两个区间的合并
- }
- int main(){
- scanf("%d%d",&n,&q);
- for(int i=1;i<=n;++i) scanf("%d",a+i);
- build(1,1,n);
- for(int i=1;i<=q;++i){
- int opt,l,r;
- scanf("%d%d%d",&opt,&l,&r); ++l, ++r;
- if(opt<3) Mdf(1,1,n,l,r,opt);
- else {d t=Qur(1,1,n,l,r); printf("%d\n",opt==3?t.w:t.mw);}
- }
- return 0;
- }
还有 ODT, 写起来超简单, 以后在更, 嘿嘿 qwq
来源: http://www.bubuko.com/infodetail-2987521.html