云浅知处 @ 2020-08-18 12:00:12
对拍了八十多组数据了=_=,还是没发现错误。
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define MAXN 200005
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
using namespace std;
int a[MAXN],n,m;
struct Node{
int sum,len;
int l,r;
int lz,re;
int lmax[2],rmax[2],max[2];
};
struct SMT{
Node d[MAXN<<2];
inline void pushup(int o){
d[o].sum=d[lson(o)].sum+d[rson(o)].sum;
d[o].len=d[lson(o)].len+d[rson(o)].len;
for(int i=0;i<=1;i++){
d[o].lmax[i]=d[lson(o)].lmax[i];
if(i==0&&d[lson(o)].sum==0){
d[o].lmax[i]+=d[rson(o)].lmax[i];
}
else if(i==1&&d[lson(o)].sum==d[lson(o)].r-d[lson(o)].l+1){
d[o].lmax[i]+=d[rson(o)].lmax[i];
}
d[o].rmax[i]=d[rson(o)].rmax[i];
if(i==0&&d[rson(o)].sum==0){
d[o].rmax[i]+=d[lson(o)].rmax[i];
}
else if(i==1&&d[rson(o)].sum==d[rson(o)].r-d[rson(o)].l+1){
d[o].rmax[i]+=d[lson(o)].rmax[i];
}
d[o].max[i]=d[lson(o)].rmax[i]+d[rson(o)].lmax[i];
d[o].max[i]=max(d[lson(o)].max[i],d[o].max[i]);
d[o].max[i]=max(d[rson(o)].max[i],d[o].max[i]);
}
}
inline void build(int l,int r,int o){
d[o].lz=-1;
d[o].re=0;
d[o].l=l;
d[o].r=r;
d[o].len=r-l+1;
if(l==r){
d[o].sum=a[l];
d[o].lmax[1]=d[o].rmax[1]=d[o].max[1]=(a[l]==1);
d[o].lmax[0]=d[o].rmax[0]=d[o].max[0]=(a[l]==0);
return ;
}
int mid=(l+r)>>1;
build(l,mid,lson(o));
build(mid+1,r,rson(o));
pushup(o);
}
inline void pushdown(int o){
if(d[o].lz!=-1){
d[o].re=0;
int val=d[o].lz;
d[lson(o)].sum=(d[lson(o)].r-d[lson(o)].l+1)*val;
d[rson(o)].sum=(d[rson(o)].r-d[rson(o)].l+1)*val;
d[lson(o)].lz=d[rson(o)].lz=val;
d[lson(o)].re=d[rson(o)].re=0;
d[lson(o)].max[val]=d[lson(o)].lmax[val]=d[lson(o)].rmax[val]=d[lson(o)].r-d[lson(o)].l+1;
d[rson(o)].max[val]=d[rson(o)].lmax[val]=d[rson(o)].rmax[val]=d[rson(o)].r-d[rson(o)].l+1;
d[lson(o)].max[val^1]=d[lson(o)].lmax[val^1]=d[lson(o)].rmax[val^1]=0;
d[rson(o)].max[val^1]=d[rson(o)].lmax[val^1]=d[rson(o)].rmax[val^1]=0;
d[o].lz=-1;
}
if(d[o].re){
d[lson(o)].sum=(d[lson(o)].r-d[lson(o)].l+1)-d[lson(o)].sum;
d[rson(o)].sum=(d[rson(o)].r-d[rson(o)].l+1)-d[rson(o)].sum;
if(d[lson(o)].lz!=-1)d[lson(o)].lz^=1;
else d[lson(o)].re^=1;
if(d[rson(o)].lz!=-1)d[rson(o)].lz^=1;
else d[rson(o)].re^=1;
swap(d[lson(o)].max[1],d[lson(o)].max[0]);
swap(d[rson(o)].max[1],d[rson(o)].max[0]);
swap(d[lson(o)].lmax[1],d[lson(o)].lmax[0]);
swap(d[rson(o)].lmax[1],d[rson(o)].lmax[0]);
swap(d[lson(o)].rmax[1],d[lson(o)].rmax[0]);
swap(d[rson(o)].rmax[1],d[rson(o)].rmax[0]);
}
}
inline void modify(int l,int r,int tag,int o){
pushdown(o);
//printf("QAQ, o=%d, l=%d, r=%d\n",o,d[o].l,d[o].r);
if(d[o].l==l&&d[o].r==r){
if(tag==0||tag==1){
d[o].sum=d[o].len*tag;
d[o].lz=tag;
d[o].lmax[tag]=d[o].rmax[tag]=d[o].max[tag]=d[o].len;
d[o].lmax[tag^1]=d[o].rmax[tag^1]=d[o].max[tag^1]=0;
//puts("QAQAQ1");
}
else if(tag==2){
d[o].sum=d[o].len-d[o].sum;
d[o].re^=1;
swap(d[o].max[1],d[o].max[0]);
swap(d[o].lmax[1],d[o].lmax[0]);
swap(d[o].rmax[1],d[o].rmax[0]);
//puts("QAQAQ2");
}
return ;
}
int mid=(d[o].l+d[o].r)>>1;
//puts("QwQwQ");
if(l>mid)modify(l,r,tag,rson(o));
else if(r<=mid)modify(l,r,tag,lson(o));
else modify(l,mid,tag,lson(o)),modify(mid+1,r,tag,rson(o));
//puts("OvOvO");
pushup(o);
}
inline int query(int l,int r,int o){
pushdown(o);
if(d[o].l==l&&d[o].r==r){
return d[o].sum;
}
int mid=(d[o].l+d[o].r)>>1;
if(l>mid)return query(l,r,rson(o));
else if(r<=mid)return query(l,r,lson(o));
else return query(l,mid,lson(o))+query(mid+1,r,rson(o));
}
inline Node Q(int l,int r,int o){
pushdown(o);
if(d[o].l==l&&d[o].r==r){
return d[o];
}
int mid=(d[o].l+d[o].r)>>1;
if(l>mid)return Q(l,r,rson(o));
else if(r<=mid)return Q(l,r,lson(o));
else{
Node tmp,L=Q(l,mid,lson(o)),R=Q(mid+1,r,rson(o));
tmp.sum=L.sum+R.sum;
for(int i=0;i<=1;i++){
tmp.lmax[i]=L.lmax[i];
if(i==0&&L.sum==0){
tmp.lmax[i]+=R.lmax[i];
}
else if(i==1&&L.sum==L.len){
tmp.lmax[i]+=R.lmax[i];
}
tmp.rmax[i]=R.rmax[i];
if(i==0&&R.sum==0){
tmp.rmax[i]+=L.rmax[i];
}
else if(i==1&&R.sum==R.len){
tmp.rmax[i]+=L.rmax[i];
}
tmp.max[i]=L.rmax[i]+R.lmax[i];
tmp.max[i]=max(tmp.max[i],L.max[i]);
tmp.max[i]=max(tmp.max[i],R.max[i]);
}
return tmp;
}
}
inline void print(){
for(int i=1;i<=(n<<1);i++){
printf("i=%d, sum=%d, len=%d, l=%d, r=%d, lz=%d, re=%d, lmax[0]=%d, lmax[1]=%d, rmax[0]=%d, rmax[1]=%d, max[0]=%d, max[1]=%d\n",i,d[i].sum,d[i].len,d[i].l,d[i].r,d[i].lz,d[i].re,d[i].lmax[0],d[i].lmax[1],d[i].rmax[0],d[i].rmax[1],d[i].max[0],d[i].max[1]);
printf("————————————————————————————————————————————————-———————————————————————————————————————————————————————————————————\n");
}
}
};
SMT tree;
int main(void){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
tree.build(1,n,1);
//tree.print();
while(m--){
int opt,l,r;
scanf("%d%d%d",&opt,&l,&r);
opt++,l++,r++;
//printf("%d %d %d\n",opt,l,r);
if(opt==1){
tree.modify(l,r,0,1);
}
else if(opt==2){
tree.modify(l,r,1,1);
}
else if(opt==3){
tree.modify(l,r,2,1);
}
else if(opt==4){
printf("%d\n",tree.query(l,r,1));
}
else if(opt==5){
printf("%d\n",tree.Q(l,r,1).max[1]);
}
}
return 0;
}
by Andy_chen @ 2020-08-18 12:32:39
这个线段树太疯狂了%%%%%%%%%
by PYD1 @ 2020-08-19 12:22:00
@云浅知处
您的数据生成器是不是写挂了?或者您数据范围开太小了?我拍了一下:
Input:
10 3 1 1 1 1 0 1 0 1 0 1 2 1 7 4 7 9 3 1 5
Output:
1 1
Your Output:
1 2
同时,我把“4 7 9”这一查询操作删除后,发现您的程序的输出就对了,说明可能是4操作(或pushup/pushdown)出了一些问题。
by PYD1 @ 2020-08-19 12:22:21
好吧Markdown炸了
by 云浅知处 @ 2020-08-19 13:07:22
@PYD1 好的好的,谢谢大佬QAQ
by PYD1 @ 2020-08-19 13:18:01
@云浅知处 谔谔