Aiopr_2378 @ 2022-06-17 22:51:17
rt，或许存在我完全不知道的问题，请各位路过的大佬看一下，或者留下一组hack，现在调这个毫无头绪qwq
感谢
by Aiopr_2378 @ 2022-06-17 22:51:38
#include<iostream>
using namespace std;
#define MAXN 100005
#define mid ((tree[p].l+tree[p].r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
int n,m;
struct node{
int l,r,re,cov,sum[2],maxl[2],maxr[2],cnt[2];
}tree[MAXN<<2];
int len(int p){
return tree[p].r-tree[p].l+1;
}
void pushup(int p){
tree[p].cnt[1]=tree[ls].cnt[1]+tree[rs].cnt[1];
tree[p].cnt[0]=tree[ls].cnt[0]+tree[rs].cnt[0];
tree[p].maxl[1]=tree[ls].maxl[1];
if(tree[ls].cnt[1]==len(ls))
tree[p].maxl[1]=max(tree[p].maxl[1],tree[ls].cnt[1]+tree[rs].maxl[1]);
tree[p].maxl[0]=tree[ls].maxl[0];
if(tree[ls].cnt[0]==len(ls))
tree[p].maxl[0]=max(tree[p].maxl[0],tree[ls].cnt[0]+tree[rs].maxl[0]);
tree[p].maxr[1]=tree[rs].maxr[1];
if(tree[rs].cnt[1]==len(rs))
tree[p].maxr[1]=max(tree[p].maxr[1],tree[rs].cnt[1]+tree[ls].maxr[1]);
tree[p].maxr[0]=tree[rs].maxr[0];
if(tree[rs].cnt[0]==len(rs))
tree[p].maxr[0]=max(tree[p].maxr[0],tree[rs].cnt[0]+tree[ls].maxr[0]);
tree[p].sum[1]=max(
max(tree[ls].sum[1],tree[rs].sum[1]),tree[ls].maxr[1]+tree[rs].maxl[1]
);
tree[p].sum[0]=max(
max(tree[ls].sum[0],tree[rs].sum[0]),tree[ls].maxr[0]+tree[rs].maxl[0]
);
}
void build(int l,int r,int p){
tree[p].l=l,tree[p].r=r;
tree[p].cov=0;
tree[p].re=-1;
if(l==r){
int x;
cin>>x;
tree[p].sum[x]=tree[p].maxl[x]=tree[p].maxr[x]=tree[p].cnt[x]=1;
tree[p].sum[x^1]=tree[p].maxl[x^1]=tree[p].maxr[x^1]=tree[p].cnt[x^1]=0;
return;
}
build(l,mid,ls);
build(mid+1,r,rs);
pushup(p);
}
void pushdown(int p){
if(tree[p].re!=-1){
tree[p].cov=0;
int k=tree[p].re;
tree[ls].re=tree[rs].re=k;
tree[ls].cov=tree[rs].cov=0;
tree[ls].sum[k]=tree[ls].maxl[k]=tree[ls].maxr[k]=tree[ls].cnt[k]=len(ls);
tree[ls].sum[k^1]=tree[ls].maxl[k^1]=tree[ls].maxr[k^1]=tree[ls].cnt[k^1]=0;
tree[rs].sum[k]=tree[rs].maxl[k]=tree[rs].maxr[k]=tree[rs].cnt[k]=len(rs);
tree[rs].sum[k^1]=tree[rs].maxl[k^1]=tree[rs].maxr[k^1]=tree[rs].cnt[k^1]=0;
tree[p].re=-1;
}
if(tree[p].cov){
if(tree[ls].re!=-1) tree[ls].re^=1;
else tree[ls].cov^=1;
if(tree[rs].re!=-1) tree[rs].re=-1;
else tree[rs].cov^=1;
swap(tree[ls].sum[0],tree[ls].sum[1]);
swap(tree[ls].maxl[0],tree[ls].maxl[1]);
swap(tree[ls].maxr[0],tree[ls].maxr[1]);
swap(tree[ls].cnt[0],tree[ls].cnt[1]);
swap(tree[rs].sum[0],tree[rs].sum[1]);
swap(tree[rs].maxl[0],tree[rs].maxl[1]);
swap(tree[rs].maxr[0],tree[rs].maxr[1]);
swap(tree[rs].cnt[0],tree[rs].cnt[1]);
tree[p].cov=0;
}
}
void reset(int l,int r,int p,int k){
if(l<=tree[p].l&&r>=tree[p].r){
tree[p].re=k;
tree[p].sum[k]=tree[p].cnt[k]=tree[p].maxl[k]=tree[p].maxr[k]=len(p);
tree[p].sum[k^1]=tree[p].cnt[k^1]=tree[p].maxl[k^1]=tree[p].maxr[k^1]=0;
return;
}
pushdown(p);
if(l<=mid) reset(l,r,ls,k);
if(r>mid) reset(l,r,rs,k);
pushup(p);
}
void modify(int l,int r,int p){
if(l<=tree[p].l&&r>=tree[p].r){
tree[p].cov^=1;
swap(tree[p].sum[0],tree[p].sum[1]);
swap(tree[p].maxl[0],tree[p].maxl[1]);
swap(tree[p].maxr[0],tree[p].maxr[1]);
swap(tree[p].cnt[0],tree[p].cnt[1]);
return;
}
pushdown(p);
if(l<=mid) modify(l,r,ls);
if(r>mid) modify(l,r,rs);
pushup(p);
}
int querycnt(int l,int r,int p){
if(l<=tree[p].l&&r>=tree[p].r) return tree[p].cnt[1];
int ans=0;
pushdown(p);
if(l<=mid) ans+=querycnt(l,r,ls);
if(r>mid) ans+=querycnt(l,r,rs);
return ans;
}
node querymax(int l,int r,int p){
if(l<=tree[p].l&&r>=tree[p].r) return tree[p];
pushdown(p);
if(l>mid) return querymax(l,r,rs);
else if(r<=mid) return querymax(l,r,ls);
else{
node ans,la=querymax(l,mid,ls),ra=querymax(mid+1,r,rs);
ans.l=la.l,ans.r=ra.r;
ans.cnt[1]=la.cnt[1]+ra.cnt[1];
ans.cnt[0]=la.cnt[0]+ra.cnt[0];
ans.maxl[1]=la.maxl[1];
if(la.cnt[1]==la.r-la.l+1) ans.maxl[1]=max(ans.maxl[1],la.cnt[1]+ra.maxl[1]);
ans.maxl[0]=la.maxl[0];
if(la.cnt[0]==la.r-la.l+1) ans.maxl[0]=max(ans.maxl[0],la.cnt[0]+ra.maxl[0]);
ans.maxr[1]=ra.maxr[1];
if(ra.cnt[1]==ra.r-ra.l+1) ans.maxr[1]=max(ans.maxr[1],ra.cnt[1]+la.maxr[1]);
ans.maxr[0]=ra.maxr[0];
if(ra.cnt[0]==ra.r-ra.l+1) ans.maxr[0]=max(ans.maxr[0],ra.cnt[0]+la.maxr[0]);
ans.sum[1]=max(
max(la.sum[1],ra.sum[1]),la.maxr[1]+ra.maxl[1]
);
ans.sum[0]=max(
max(la.sum[0],ra.sum[0]),la.maxr[0]+ra.maxl[0]
);
return ans;
}
}
int main(){
cin>>n>>m;
build(1,n,1);
while(m--){
int op,l,r;
cin>>op>>l>>r;
l++,r++;
if(op==0||op==1) reset(l,r,1,op);
if(op==2) modify(l,r,1);
if(op==3) cout<<querycnt(l,r,1)<<endl;
if(op==4) cout<<querymax(l,r,1).sum[1]<<endl;
}
return 0;
}by Aiopr_2378 @ 2022-06-17 22:53:13
救救这个孩子qwq
by Y2y7m @ 2022-06-17 23:58:44
@Aiopr_2378 这道题我调了一周没出来，是挺毒瘤的，唉
by Aiopr_2378 @ 2022-06-18 08:46:47
@Y2y7m 您如果有时间可以帮忙看一下吗，或者有什么特别需要注意的地方qwq
by Y2y7m @ 2022-06-18 09:59:25
@Aiopr_2378 好的,我看看
by Y2y7m @ 2022-06-18 12:42:54
@Aiopr_2378 您能解释一下cnt数组是干什么的吗，以及变量re
by Aiopr_2378 @ 2022-06-18 12:56:18
cnt就是记录区域内0/1的个数
re就是区间覆盖的标记（就是操作0和1）
by Y2y7m @ 2022-06-18 13:00:17
@Aiopr_2378 此题需要维护0的个数吗？总数减去一的个数不就行了？
by Y2y7m @ 2022-06-18 13:01:18
@Aiopr_2378 现在查出来的问题：pushdown位置有问题，应该放在第一行的位置
by Aiopr_2378 @ 2022-06-18 13:11:25
@Y2y7m 您看一下是这样吗