萌新求助
- 板块P2572 [SCOI2010] 序列操作
- 楼主FL_sleake
- 当前回复1
- 已保存回复1
- 发布时间2023/10/5 15:52
- 上次更新2023/11/2 15:29:48
查看原帖
被骇客银狼阻止的越权访问保存失败
萌新求助
调了3h都没调出来，求救qaq
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Tree{
int l,r,num_0,num_1;//个数
int lmax_0,lmax_1,rmax_0,rmax_1;//左起/右起个数
int ans_0,ans_1;//最长连续
int rev;//0:无 1:覆盖
int cov;//-1:无 0:0 1:1
}tree[100010<<2];
int n,m,a[100010];
void Pushup(int rt){
int lson=rt<<1;
int rson=rt<<1|1;
tree[rt].num_0=tree[lson].num_0+tree[rson].num_0;
tree[rt].num_1=tree[lson].num_1+tree[rson].num_1;
if(tree[lson].lmax_0==tree[lson].r-tree[lson].l+1) tree[rt].lmax_0=tree[lson].lmax_0+tree[rson].lmax_0;
else tree[rt].lmax_0=tree[lson].lmax_0;
if(tree[rson].rmax_0==tree[rson].r-tree[rson].l+1) tree[rt].rmax_0=tree[rson].rmax_0+tree[lson].rmax_0;
else tree[rt].rmax_0=tree[rson].rmax_0;
if(tree[lson].lmax_1==tree[lson].r-tree[lson].l+1) tree[rt].lmax_1=tree[lson].lmax_1+tree[rson].lmax_1;
else tree[rt].lmax_1=tree[lson].lmax_1;
if(tree[rson].rmax_1==tree[rson].r-tree[rson].l+1) tree[rt].rmax_1=tree[rson].rmax_1+tree[lson].rmax_1;
else tree[rt].rmax_1=tree[rson].rmax_1;
tree[rt].ans_0=max({tree[lson].ans_0,tree[rson].ans_0,tree[lson].rmax_0+tree[rson].lmax_0});
tree[rt].ans_1=max({tree[lson].ans_1,tree[rson].ans_1,tree[lson].rmax_1+tree[rson].lmax_1});
}
void Pushdown(int rt){
int lson=rt<<1,rson=rt<<1|1;
int Lengthl=tree[lson].r-tree[lson].l+1;
int Lengthr=tree[rson].r-tree[rson].l+1;
if(tree[rt].cov==0){
tree[rt].cov=-1;
tree[rt].rev=0;
tree[lson].cov=tree[rson].cov=0;
tree[lson].rev=0;
tree[rson].rev=0;
tree[lson].ans_0=Lengthl;
tree[rson].ans_0=Lengthr;
tree[lson].ans_1=0;
tree[rson].ans_1=0;
tree[lson].num_0=Lengthl;
tree[rson].num_0=Lengthr;
tree[lson].num_1=0;
tree[rson].num_1=0;
tree[lson].lmax_0=tree[lson].rmax_0=Lengthl;
tree[rson].lmax_0=tree[rson].rmax_0=Lengthr;
tree[lson].lmax_1=tree[lson].rmax_1=0;
tree[rson].lmax_1=tree[rson].rmax_1=0;
}else if(tree[rt].cov==1){
tree[rt].cov=-1;
tree[rt].rev=0;
tree[lson].cov=tree[rson].cov=1;
tree[lson].rev=0;
tree[rson].rev=0;
tree[lson].ans_0=0;
tree[rson].ans_0=0;
tree[lson].ans_1=Lengthl;
tree[rson].ans_1=Lengthr;
tree[lson].num_0=0;
tree[rson].num_0=0;
tree[lson].num_1=Lengthl;
tree[rson].num_1=Lengthr;
tree[lson].lmax_0=tree[lson].rmax_0=0;
tree[rson].lmax_0=tree[rson].rmax_0=0;
tree[lson].lmax_1=tree[lson].rmax_1=Lengthl;
tree[rson].lmax_1=tree[rson].rmax_1=Lengthr;
}
if(tree[rt].rev){
tree[rt].rev=0;
if(tree[lson].cov!=-1) Pushdown(lson);
if(tree[rson].cov!=-1) Pushdown(rson);
if(tree[lson].cov!=-1) tree[lson].cov^=1;
else tree[lson].rev^=1;
if(tree[rson].cov!=-1) tree[rson].cov^=1;
else tree[rson].rev^=1;
swap(tree[lson].ans_0,tree[lson].ans_1);
swap(tree[rson].ans_0,tree[rson].ans_1);
swap(tree[lson].num_0,tree[lson].num_1);
swap(tree[rson].num_0,tree[rson].num_1);
swap(tree[lson].lmax_0,tree[lson].lmax_1);
swap(tree[rson].lmax_0,tree[rson].lmax_1);
swap(tree[lson].rmax_0,tree[lson].rmax_1);
swap(tree[rson].rmax_0,tree[rson].rmax_1);
}
}
void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].rev=0;
tree[rt].cov=-1;
if(l==r){
if(a[l]==0){
tree[rt].num_0=1;
tree[rt].num_1=0;
tree[rt].lmax_0=1;
tree[rt].lmax_1=0;
tree[rt].rmax_0=1;
tree[rt].rmax_1=0;
tree[rt].ans_0=1;
tree[rt].ans_1=0;
}else{
tree[rt].num_0=0;
tree[rt].num_1=1;
tree[rt].lmax_0=0;
tree[rt].lmax_1=1;
tree[rt].rmax_0=0;
tree[rt].rmax_1=1;
tree[rt].ans_0=0;
tree[rt].ans_1=1;
}
return;
}
int mid=(l+r)>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
void Update1(int rt,int l,int r){
if(l<=tree[rt].l&&tree[rt].r<=r){
int Length=tree[rt].r-tree[rt].l+1;
tree[rt].cov=0;
tree[rt].ans_0=Length;
tree[rt].ans_1=0;
tree[rt].num_0=Length;
tree[rt].num_1=0;
tree[rt].lmax_0=Length;
tree[rt].lmax_1=0;
tree[rt].rmax_0=Length;
tree[rt].rmax_1=0;
return;
}
Pushdown(rt);
int mid=(tree[rt].l+tree[rt].r)>>1;
if(r<=mid) Update1(rt<<1,l,r);
else if(l>mid) Update1(rt<<1|1,l,r);
else Update1(rt<<1,l,mid),Update1(rt<<1|1,mid+1,r);
Pushup(rt);
}
void Update2(int rt,int l,int r){
if(l<=tree[rt].l&&tree[rt].r<=r){
int Length=tree[rt].r-tree[rt].l+1;
tree[rt].cov=1;
tree[rt].ans_0=0;
tree[rt].ans_1=Length;
tree[rt].num_0=0;
tree[rt].num_1=Length;
tree[rt].lmax_0=0;
tree[rt].lmax_1=Length;
tree[rt].rmax_0=0;
tree[rt].rmax_1=Length;
return;
}
Pushdown(rt);
int mid=(tree[rt].l+tree[rt].r)>>1;
if(r<=mid) Update2(rt<<1,l,r);
else if(l>mid) Update2(rt<<1|1,l,r);
else Update2(rt<<1,l,mid),Update2(rt<<1|1,mid+1,r);
Pushup(rt);
}
void Update3(int rt,int l,int r){
if(l<=tree[rt].l&&tree[rt].r<=r){
tree[rt].rev=1;
swap(tree[rt].num_0,tree[rt].num_1);
swap(tree[rt].ans_0,tree[rt].ans_1);
swap(tree[rt].lmax_0,tree[rt].lmax_1);
swap(tree[rt].rmax_0,tree[rt].rmax_1);
return;
}
Pushdown(rt);
int mid=(tree[rt].l+tree[rt].r)>>1;
if(r<=mid) Update3(rt<<1,l,r);
else if(l>mid) Update3(rt<<1|1,l,r);
else Update3(rt<<1,l,mid),Update3(rt<<1|1,mid+1,r);
Pushup(rt);
}
int Query1(int rt,int l,int r){
// cout<<"#:"<<rt<<","<<l<<","<<r<<endl;
// cout<<" #:"<<tree[rt].l<<","<<tree[rt].r<<endl;
if(l<=tree[rt].l&&tree[rt].r<=r) return tree[rt].num_1;
Pushdown(rt);
int mid=(tree[rt].l+tree[rt].r)>>1;
if(r<=mid) return Query1(rt<<1,l,r);
else if(l>mid) return Query1(rt<<1|1,l,r);
else return Query1(rt<<1,l,mid)+Query1(rt<<1|1,mid+1,r);
Pushup(rt);
}
Tree Query2(int rt,int l,int r){
//cout<<" #:"<<rt<<","<<l<<","<<r<<endl;
Pushdown(rt);
if(tree[rt].l==l&&tree[rt].r==r) return tree[rt];
Tree ans={0,0,0,0,0,0,0,0,0,0,0,0},lson={0,0,0,0,0,0,0,0,0,0,0,0},rson={0,0,0,0,0,0,0,0,0,0,0,0};
int mid=(tree[rt].l+tree[rt].r)>>1;
if(l>mid) return Query2(rt<<1|1,l,r);
else if(r<=mid) return Query2(rt<<1,l,r);
else{
lson=Query2(rt<<1,l,mid);
rson=Query2(rt<<1|1,mid+1,r);
ans.l=tree[rt].l;
ans.r=tree[rt].r;
ans.num_0=lson.num_0+rson.num_0;
ans.num_1=lson.num_1+rson.num_1;
ans.lmax_1=lson.lmax_1;
if(lson.lmax_1==lson.r-lson.l+1) ans.lmax_1+=rson.lmax_1;
ans.rmax_1=rson.rmax_1;
if(rson.rmax_1==rson.r-rson.l+1) ans.rmax_1+=lson.rmax_1;
ans.ans_1=max({lson.ans_1,rson.ans_1,lson.rmax_1+rson.lmax_1});
//cout<<"#:"<<ans.ans_1<<","<<ans.l<<","<<ans.r<<","<<ans.lmax_1<<","<<ans.rmax_1<<endl;
return ans;
}
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
Build(1,1,n);
while(m--){
int op,l,r;
scanf("%lld%lld%lld",&op,&l,&r);
l++,r++;
if(op==0) Update1(1,l,r);
else if(op==1) Update2(1,l,r);
else if(op==2) Update3(1,l,r);
else if(op==3) cout<<Query1(1,l,r)<<endl;
else if(op==4) cout<<Query2(1,l,r).ans_1<<endl;
}
return 0;
}
/*
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
0 0 0 1 1 0 1 0 1 1
1 1 1 1 1 0 1 0 1 1
1 1 0 1 1 0 1 0 1 1
1 1 0 0 0 0 0 0 1 1
1 1 0 1 1 1 1 1 1 1
8 9
0 1 0 1 0 1 0 0
2 1 5
3 3 3
2 3 7
4 3 6
4 5 6
2 3 5
0 0 4
0 0 5
1 0 7
0 1 0 1 0 1 0 0
0 0 1 0 1 0 0 0
0 0 1 1 0 1 1 1
*/
加载中...