| 记录编号 |
602641 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
2083.[SCOI2010]序列操作 |
最终得分 |
100 |
| 用户昵称 |
 秋_Water |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
2.175 s |
| 提交时间 |
2025-07-04 22:03:23 |
内存使用 |
10.90 MiB |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node{
int l,r,sum1,max1,max0,lmax1,lmax0,rmax1,rmax0,len,add0,add1,add3;
}t[N];
int a[N],cnt,n,m,root;
void update(int p){
t[p].sum1=t[t[p].l].sum1+t[t[p].r].sum1;
if(t[t[p].l].max1==t[t[p].l].len) t[p].lmax1=t[t[p].l].len+t[t[p].r].lmax1;
else t[p].lmax1=t[t[p].l].lmax1;
if(t[t[p].r].max1==t[t[p].r].len) t[p].rmax1=t[t[p].r].len+t[t[p].l].rmax1;
else t[p].rmax1=t[t[p].r].rmax1;
t[p].max1=max(max(t[t[p].l].max1,t[t[p].r].max1),t[t[p].l].rmax1+t[t[p].r].lmax1);
if(t[t[p].l].max0==t[t[p].l].len) t[p].lmax0=t[t[p].l].len+t[t[p].r].lmax0;
else t[p].lmax0=t[t[p].l].lmax0;
if(t[t[p].r].max0==t[t[p].r].len) t[p].rmax0=t[t[p].r].len+t[t[p].l].rmax0;
else t[p].rmax0=t[t[p].r].rmax0;
t[p].max0=max(max(t[t[p].l].max0,t[t[p].r].max0),t[t[p].l].rmax0+t[t[p].r].lmax0);
}
void pushdown(int p){
if(t[p].add0){
t[t[p].l].sum1=t[t[p].l].max1=t[t[p].l].lmax1=t[t[p].l].rmax1=0;
t[t[p].l].max0=t[t[p].l].lmax0=t[t[p].l].rmax0=t[t[p].l].len;
t[t[p].l].add0=1;
t[t[p].l].add1=0;
t[t[p].l].add3=0;
t[t[p].r].sum1=t[t[p].r].max1=t[t[p].r].lmax1=t[t[p].r].rmax1=0;
t[t[p].r].max0=t[t[p].r].lmax0=t[t[p].r].rmax0=t[t[p].r].len;
t[t[p].r].add0=1;
t[t[p].r].add1=0;
t[t[p].r].add3=0;
t[p].add0=0;
}
if(t[p].add1){
t[t[p].l].sum1=t[t[p].l].max1=t[t[p].l].lmax1=t[t[p].l].rmax1=t[t[p].l].len;
t[t[p].l].max0=t[t[p].l].lmax0=t[t[p].l].rmax0=0;
t[t[p].l].add0=0;
t[t[p].l].add1=1;
t[t[p].l].add3=0;
t[t[p].r].sum1=t[t[p].r].max1=t[t[p].r].lmax1=t[t[p].r].rmax1=t[t[p].r].len;
t[t[p].r].max0=t[t[p].r].lmax0=t[t[p].r].rmax0=0;
t[t[p].r].add0=0;
t[t[p].r].add1=1;
t[t[p].r].add3=0;
t[p].add1=0;
}
if(t[p].add3){
t[t[p].l].sum1=t[t[p].l].len-t[t[p].l].sum1;
swap(t[t[p].l].max1,t[t[p].l].max0);
swap(t[t[p].l].lmax1,t[t[p].l].lmax0);
swap(t[t[p].l].rmax1,t[t[p].l].rmax0);
swap(t[t[p].l].add0,t[t[p].l].add1);
if(t[t[p].l].add0==0&&t[t[p].l].add1==0){
t[t[p].l].add3^=1;
}
t[t[p].r].sum1=t[t[p].r].len-t[t[p].r].sum1;
swap(t[t[p].r].max1,t[t[p].r].max0);
swap(t[t[p].r].lmax1,t[t[p].r].lmax0);
swap(t[t[p].r].rmax1,t[t[p].r].rmax0);
swap(t[t[p].r].add0,t[t[p].r].add1);
if(t[t[p].r].add0==0&&t[t[p].r].add1==0){
t[t[p].r].add3^=1;
}
t[p].add3=0;
}
}
void build(int &p,int l,int r){
p=++cnt;
t[p].len=(r-l+1);
if(l==r){
t[p].sum1=a[l];
t[p].max1=a[l];
t[p].max0=a[l]^1;
t[p].lmax1=a[l];
t[p].lmax0=a[l]^1;
t[p].rmax1=a[l];
t[p].rmax0=a[l]^1;
return;
}
int mid=l+r>>1;
build(t[p].l,l,mid);
build(t[p].r,mid+1,r);
update(p);
}
void change1(int p,int l,int r,int ql,int qr){
if(l>qr||r<ql){
return;
}
if(ql<=l&&r<=qr){
t[p].sum1=t[p].max1=t[p].lmax1=t[p].rmax1=0;
t[p].max0=t[p].lmax0=t[p].rmax0=t[p].len;
t[p].add0=1;
t[p].add1=0;
t[p].add3=0;
return;
}
pushdown(p);
int mid=l+r>>1;
change1(t[p].l,l,mid,ql,qr);
change1(t[p].r,mid+1,r,ql,qr);
update(p);
}
void change2(int p,int l,int r,int ql,int qr){
if(l>qr||r<ql){
return;
}
if(ql<=l&&r<=qr){
t[p].sum1=t[p].max1=t[p].lmax1=t[p].rmax1=t[p].len;
t[p].max0=t[p].lmax0=t[p].rmax0=0;
t[p].add0=0;
t[p].add1=1;
t[p].add3=0;
return;
}
pushdown(p);
int mid=l+r>>1;
change2(t[p].l,l,mid,ql,qr);
change2(t[p].r,mid+1,r,ql,qr);
update(p);
}
void change3(int p,int l,int r,int ql,int qr){
if(l>qr||r<ql){
return;
}
if(ql<=l&&r<=qr){
t[p].sum1=t[p].len-t[p].sum1;
swap(t[p].max1,t[p].max0);
swap(t[p].lmax1,t[p].lmax0);
swap(t[p].rmax1,t[p].rmax0);
swap(t[p].add0,t[p].add1);
if(t[p].add0==0&&t[p].add1==0){
t[p].add3^=1;
}
return;
}
pushdown(p);
int mid=l+r>>1;
change3(t[p].l,l,mid,ql,qr);
change3(t[p].r,mid+1,r,ql,qr);
update(p);
}
int query1(int p,int l,int r,int ql,int qr){
if(l>qr||r<ql){
return 0;
}
if(ql<=l&&r<=qr){
return t[p].sum1;
}
pushdown(p);
int mid=l+r>>1;
return query1(t[p].l,l,mid,ql,qr)+query1(t[p].r,mid+1,r,ql,qr);
}
int query2(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return t[p].max1;
}
pushdown(p);
int mid=l+r>>1;
if(qr<=mid){
return query2(t[p].l,l,mid,ql,qr);
}
else if(ql>mid){
return query2(t[p].r,mid+1,r,ql,qr);
}
else{
int v1=query2(t[p].l,l,mid,ql,mid);
int v2=query2(t[p].r,mid+1,r,mid+1,qr);
int v3=min(t[t[p].l].rmax1,mid-ql+1)+min(t[t[p].r].lmax1,qr-mid);
return max(max(v1,v2),v3);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(root,1,n);
for(int i=1;i<=m;i++){
int op,l,r;
cin>>op>>l>>r;
l++,r++;
if(op==0){
change1(root,1,n,l,r);
}
else if(op==1){
change2(root,1,n,l,r);
}
else if(op==2){
change3(root,1,n,l,r);
}
else if(op==3){
cout<<query1(root,1,n,l,r)<<"\n";
}
else{
cout<<query2(root,1,n,l,r)<<"\n";
}
}
return 0;
}