1858: [Scoi2010]序列操作
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 3079 Solved: 1475
[Submit][Status][Discuss]
Description
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都需要给出回答，聪明的程序员们，你们能帮助他吗？
Input
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目 第二行包括n个数，表示序列的初始状态 接下来m行，每行3个数，op, a, b，（0 < = op < = 4，0 < = a < = b）
Output
对于每一个询问操作，输出一行，包括1个数，表示其对应的答案
Sample Input
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
Sample Output
5
2
6
5
HINT
对于30%的数据，1<=n, m<=1000 对于100%的数据，1< = n, m < = 100000
Source
操作有点多
因为会出现反转,所以0和1的信息都要记录
0,1分别记录出现次数,左数最长长度,右数最长长度和区间最长长度
代码别写错就好
#include<cstdio>
#include<algorithm>
#include<iostream>
#define ll long long
#define inf 2147483647
#define N 100005
using namespace std;
struct node{
int sum[2],lm[2],rm[2],mx[2];
int l,r,cov,rev;
void sp(){
swap(sum[0],sum[1]);
swap(lm[0],lm[1]);
swap(rm[0],rm[1]);
swap(mx[0],mx[1]);
}
void init(){cov=-1;}
}t[N*4];int n,m;
void pushup(int u){
int l=u<<1,r=l|1;
for(int i=0;i<2;i++){
t[u].sum[i]=t[l].sum[i]+t[r].sum[i];
t[u].lm[i]=t[l].lm[i];
if(t[l].lm[i]==t[l].r-t[l].l+1)t[u].lm[i]+=t[r].lm[i];
t[u].rm[i]=t[r].rm[i];
if(t[r].rm[i]==t[r].r-t[r].l+1)t[u].rm[i]+=t[l].rm[i];
t[u].mx[i]=max(max(t[l].mx[i],t[r].mx[i]),t[l].rm[i]+t[r].lm[i]);
}
}
void swapp(int u){t[u].sp();}
void change(int u){
int k=t[u].cov,o=k^1;
t[u].sum[k]=t[u].lm[k]=t[u].rm[k]=t[u].mx[k]=t[u].r-t[u].l+1;
t[u].sum[o]=t[u].lm[o]=t[u].rm[o]=t[u].mx[o]=0;
}
void pushdown(int u){
int l=u<<1,r=l|1;
if(t[u].rev){
if(t[l].cov!=-1)t[l].cov^=1,swapp(l);
else t[l].rev^=1,swapp(l);
if(t[r].cov!=-1)t[r].cov^=1,swapp(r);
else t[r].rev^=1,swapp(r);
t[u].rev=0;
}
if(t[u].cov!=-1){
t[l].cov=t[r].cov=t[u].cov;
change(l);change(r);
t[u].cov=-1;
}
}
void build(int u,int l,int r){
t[u].l=l;t[u].r=r;t[u].init();
if(l==r){
int x;
scanf("%d",&x);int o=x^1;
t[u].sum[x]=t[u].lm[x]=t[u].rm[x]=t[u].mx[x]=1;
t[u].sum[o]=t[u].lm[o]=t[u].rm[o]=t[u].mx[o]=0;
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
void cover(int u,int l,int r,int op){
if(t[u].l==l&&t[u].r==r){
t[u].rev=0;
t[u].cov=op;
change(u);
return;
}
pushdown(u);
int mid=(t[u].l+t[u].r)>>1;
if(r<=mid)cover(u<<1,l,r,op);
else if(l>mid)cover(u<<1|1,l,r,op);
else{
cover(u<<1,l,mid,op);
cover(u<<1|1,mid+1,r,op);
}
pushup(u);
}
void reverse(int u,int l,int r){
if(t[u].l==l&&t[u].r==r){
if(t[u].cov!=-1){
t[u].cov^=1;
swapp(u);
return;
}
t[u].rev^=1;
swapp(u);
return;
}
pushdown(u);
int mid=(t[u].l+t[u].r)>>1;
if(r<=mid)reverse(u<<1,l,r);
else if(l>mid)reverse(u<<1|1,l,r);
else{
reverse(u<<1,l,mid);
reverse(u<<1|1,mid+1,r);
}
pushup(u);
}
int sum(int u,int l,int r){
if(t[u].l==l&&t[u].r==r)return t[u].sum[1];
pushdown(u);
int mid=(t[u].l+t[u].r)>>1;
if(r<=mid)return sum(u<<1,l,r);
else if(l>mid)return sum(u<<1|1,l,r);
return sum(u<<1,l,mid)+sum(u<<1|1,mid+1,r);
}
struct ans{int len,lm,rm,mx;};
ans query(int u,int l,int r){
if(t[u].l==l&&t[u].r==r){
ans p;
p=(ans){t[u].r-t[u].l+1,t[u].lm[1],t[u].rm[1],t[u].mx[1]};
return p;
}
pushdown(u);
int mid=(t[u].l+t[u].r)>>1;
if(r<=mid)return query(u<<1,l,r);
else if(l>mid)return query(u<<1|1,l,r);
else{
ans a=query(u<<1,l,mid);
ans b=query(u<<1|1,mid+1,r);
ans k=(ans){a.len+b.len,a.lm,b.rm,a.mx};
if(a.lm==a.len)k.lm+=b.lm;
if(b.rm==b.len)k.rm+=a.rm;
k.mx=max(k.mx,max(b.mx,a.rm+b.lm));
return k;
}
}
int main(){
scanf("%d%d",&n,&m);
build(1,1,n);
for(int i=1;i<=m;i++){
int op,l,r;
scanf("%d%d%d",&op,&l,&r);l++;r++;
if(op==1||op==0)cover(1,l,r,op);
if(op==2)reverse(1,l,r);
if(op==3)printf("%d\n",sum(1,l,r));
if(op==4){
ans a=query(1,l,r);
printf("%d\n",a.mx);
}
}
return 0;
}