P7825 「RdOI R3」VSQ 解题报告

解题报告

P7825 「RdOI R3」VSQ解题报告：

更好的阅读体验

题意

给定一个长度为 $n$ 的 01 序列，共 $m$ 次操作，每次支持区间推平，区间反转，查询区间最长 $01$ 间隔串，查询区间长度为 $k$ 的 $01$ 间隔串数量。

$1\leqslant n,m\leqslant 5\times 10^5$。

分析

为什么我要做这种毒瘤 ds 题啊，毒瘤 ds 毁我一上午。

首先套路地进行差分，那么我们要进行的操作就变成了：支持序列 $a$ 的区间推平，异或，支持 $a$ 的差分序列 $b$ 的区间推平为 $0$ 和单点修改，以及查询 $b$ 的区间最长全 $1$ 段和区间长度大于等于 $k$ 的全 $1$ 段数。

除了最后一个操作都可以用两颗线段树套路地维护，考虑最后一个操作怎么维护，考场我想的是分块，发现复杂度完全不能接受，于是写了写珂朵莉树，发现也不行，就罚坐到比赛结束。/ll

实际上可以考虑用第二棵线段树同时维护每个线段树区间的所有全 $1$ 段，每次区间推平为 $0$ 就在每个结点暴力删除全 $1$ 段，单点修改就在对应的结点用珂朵莉树类似的写法合并与分裂区间，然后每个区间的长度扔到对应结点的树状数组里，每次查询记一下上个位置，然后在树状数组内查一查，分类讨论一下就可以做了。

时间复杂度：$O(n\log^2 n)$。

代码

#include<stdio.h>
#include<math.h>
#include<vector>
#include<set>
#define lc(x) (x)<<1
#define rc(x) (x)<<1|1
#define lowbit(x) x&-x 
using namespace std;
const int maxn=500005,maxm=500005,maxt=maxn<<2;
int n,m;
int a[maxn],b[maxn],qo[maxm],ql[maxm],qr[maxm],qk[maxm],tag[maxt],lazy[maxt];
void abuild(int l,int r,int now){
    lazy[now]=-1;
    if(l==r){
        lazy[now]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    abuild(l,mid,lc(now)),abuild(mid+1,r,rc(now));
}
inline void agetlazy(int now,int v){
    lazy[now]=v,tag[now]=0;
}
inline void agettag(int now){
    if(lazy[now]!=-1)
        lazy[now]^=1;
    else tag[now]^=1;
}
inline void apushdown(int now){
    if(tag[now])
        agettag(lc(now)),agettag(rc(now)),tag[now]=0;
    if(lazy[now]!=-1)
        agetlazy(lc(now),lazy[now]),agetlazy(rc(now),lazy[now]),lazy[now]=-1;
}
void aupdate(int l,int r,int now,int L,int R,int v){
    if(L<=l&&r<=R){
        agetlazy(now,v);
        return ;
    }
    int mid=(l+r)>>1;
    apushdown(now);
    if(L<=mid)
        aupdate(l,mid,lc(now),L,R,v);
    if(mid<R)
        aupdate(mid+1,r,rc(now),L,R,v);
}
void aupdatexor(int l,int r,int now,int L,int R){
    if(L<=l&&r<=R){
        agettag(now);
        return ;
    }
    int mid=(l+r)>>1;
    apushdown(now);
    if(L<=mid)
        aupdatexor(l,mid,lc(now),L,R);
    if(mid<R)
        aupdatexor(mid+1,r,rc(now),L,R);
}
int aquery(int l,int r,int now,int pos){
    if(l==r)
        return tag[now]^lazy[now];
    apushdown(now);
    int mid=(l+r)>>1;
    return pos<=mid? aquery(l,mid,lc(now),pos):aquery(mid+1,r,rc(now),pos);
}
vector<int>t1[maxt],t2[maxt];
void update(int now,int pos,int val){
    if(pos==1)
        return ;
    int len=t1[now].size()-1;
    for(int i=len-pos+1;i<=len;i+=lowbit(i))
        t1[now][i]+=val,t2[now][i]+=val*pos;
}
int query(int now,int pos){
    if(pos==1)
        return 0;
    int len=t1[now].size()-1,res=0;
    if(len<pos)
        return 0;
    for(int i=len-pos+1;i;i-=lowbit(i))
        res+=t2[now][i]-t1[now][i]*(pos-1);
    return res;
}
int blazy[maxt];
struct bnode{
    int pre,suf,maxx,len;
}t[maxt];
struct section{
    int l,r;
    bool operator < (const section &p)const{
        return l<p.l;
    }
}lst;
set<section>s[maxt];
void cmodify(int now,int x,int v){
//  printf("cmodify %d (%d,%d)\n",now,x,v);
    if(v==1){
        if(s[now].empty()){
            s[now].insert(section{x,x}),update(now,1,1);
            return ;
        }
        set<section>::iterator itr=s[now].upper_bound(section{x,-1}),itl=itr;
        itl--;
        int l=itl->l,r=itr->r;
        int lt=itr!=s[now].begin()&&itl->r==x-1,rt=itr!=s[now].end()&&itr->l==x+1;
        if(lt==0&&rt==0)
            s[now].insert(section{x,x}),update(now,1,1);
        if(lt==1&&rt==0)
            s[now].erase(itl),update(now,x-l,-1),s[now].insert(section{l,x}),update(now,x-l+1,1);
        if(lt==0&&rt==1)
            s[now].erase(itr),update(now,r-x,-1),s[now].insert(section{x,r}),update(now,r-x+1,1);
        if(lt==1&&rt==1)
            s[now].erase(itl),update(now,x-l,-1),s[now].erase(itr),update(now,r-x,-1),s[now].insert(section{l,r}),update(now,r-l+1,1);
    }
    if(v==0){
        set<section>::iterator it=s[now].upper_bound(section{x,-1}); 
        it--;
        int l=it->l,r=it->r;
        s[now].erase(it),update(now,r-l+1,-1);
        if(l==x&&r!=x)
            s[now].insert(section{l+1,r}),update(now,r-l,1); 
        if(l!=x&&r==x)
            s[now].insert(section{l,r-1}),update(now,r-l,1);
        if(l!=x&&r!=x)
            s[now].insert(section{l,x-1}),update(now,x-l,1),s[now].insert(section{x+1,r}),update(now,r-x,1);
    }
}
set<section>::iterator split(int now,int pos){
    set<section>::iterator it=s[now].lower_bound(section{pos,-1}),tmp=it;
    if(it!=s[now].end()&&(it==s[now].begin()||it->l==pos))
        return it;
    tmp--;
    if(tmp->r<pos)
        return it;
    int l=tmp->l,r=tmp->r;
    s[now].erase(tmp),update(now,r-l+1,-1);
    if(pos>l)
        s[now].insert(section{l,pos-1}),update(now,pos-l,1);
    update(now,r-pos+1,1);
    return s[now].insert(section{pos,r}).first;
}
bnode merge(bnode a,bnode b){
    bnode res;
    res.pre=a.len==a.pre? (a.len+b.pre):a.pre;
    res.suf=b.len==b.suf? (b.len+a.suf):b.suf;
    res.maxx=max(max(a.maxx,b.maxx),a.suf+b.pre);
    res.len=a.len+b.len;
    return res;
}
inline void bpushup(int now){
    t[now]=merge(t[lc(now)],t[rc(now)]);
}
void bbuild(int l,int r,int now){
//  printf("l=%d r=%d now=%d\n",l,r,now);
    t1[now].resize(r-l+2),t2[now].resize(r-l+2);
    for(int i=l;i<=r;i++)
        if(b[i])
            cmodify(now,i,1);
    if(l==r){
        t[now].len=1,t[now].pre=t[now].suf=t[now].maxx=b[l];
        return ;
    }
    int mid=(l+r)>>1;
    bbuild(l,mid,lc(now)),bbuild(mid+1,r,rc(now));
    bpushup(now);
}
inline void bgetlazy(int now){
    t[now].pre=t[now].suf=t[now].maxx=0,blazy[now]=1;
}
inline void bpushdown(int now){
    if(blazy[now])
        bgetlazy(lc(now)),bgetlazy(rc(now)),blazy[now]=0;
}
void bmodify(int l,int r,int now,int pos,int v){
    cmodify(now,pos,v);
    if(l==r){
        b[l]=t[now].pre=t[now].suf=t[now].maxx=v;
        return ;
    }
    int mid=(l+r)>>1;
    bpushdown(now);
    if(pos<=mid)
        bmodify(l,mid,lc(now),pos,v);
    else bmodify(mid+1,r,rc(now),pos,v);
    bpushup(now);
}
void bupdate(int l,int r,int now,int L,int R){
    if(L<=l&&r<=R){
        bgetlazy(now);
        return ;
    }
    int mid=(l+r)>>1; 
    bpushdown(now);
    if(L<=mid)
        bupdate(l,mid,lc(now),L,R);
    if(mid<R)
        bupdate(mid+1,r,rc(now),L,R);
    bpushup(now);
}
void cupdate(int l,int r,int now,int L,int R){
    if(s[now].size()==0)
        return ;
    if(l==r){
        for(set<section>::iterator it=s[now].begin();it!=s[now].end();it=s[now].erase(it))
            update(now,it->r-it->l+1,-1);
        return ;
    }
    set<section>::iterator itr=split(now,min(r,R)+1),itl=split(now,max(l,L));
    while(itl!=itr)
        update(now,itl->r-itl->l+1,-1),itl=s[now].erase(itl);
    int mid=(l+r)>>1; 
    if(L<=mid)
        cupdate(l,mid,lc(now),L,R);
    if(mid<R)
        cupdate(mid+1,r,rc(now),L,R);
}
int bget(int l,int r,int now,int pos){
    if(l==r)
        return t[now].maxx;
    int mid=(l+r)>>1;
    bpushdown(now);
    return pos<=mid? bget(l,mid,lc(now),pos):bget(mid+1,r,rc(now),pos);
}
int bquerysum(int l,int r,int now,int L,int R,int K){
    if(s[now].empty())
        return 0;
    if(L<=l&&r<=R){
        int res=query(now,K);
        section st=*s[now].begin(),ed=*s[now].rbegin();
        if(lst.r+1==st.l){
            res+=max(st.r-lst.l+1-K+1,0)-max(lst.r-lst.l+1-K+1,0)-max(st.r-st.l+1-K+1,0);
            if(s[now].size()==1)
                lst=section{lst.l,ed.r};
            else lst=ed;
        }
        else lst=ed;
        return res;
    }
    int mid=(l+r)>>1,res=0;
    if(L<=mid)
        res+=bquerysum(l,mid,lc(now),L,R,K);
    if(mid<R)
        res+=bquerysum(mid+1,r,rc(now),L,R,K);
    return res;
}
bnode bquerymax(int l,int r,int now,int L,int R){
    if(L<=l&&r<=R)
        return t[now];
    int mid=(l+r)>>1;
    bpushdown(now);
    if(L<=mid&&mid<R)
        return merge(bquerymax(l,mid,lc(now),L,R),bquerymax(mid+1,r,rc(now),L,R));
    if(L<=mid)
        return bquerymax(l,mid,lc(now),L,R);
    return bquerymax(mid+1,r,rc(now),L,R);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    abuild(1,n,1);
    for(int i=1;i<n;i++)
        b[i]=a[i]^a[i+1];
    bbuild(1,n,1);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&qo[i],&ql[i],&qr[i]);
        if(qo[i]==3)
            scanf("%d",&qk[i]);
    }
    for(int i=1;i<=m;i++){
        int opt=qo[i],l=ql[i],r=qr[i],k=qk[i]; 
        if(opt==0){
            if(l>1){
                int x=aquery(1,n,1,l-1);
                if(bget(1,n,1,l-1)!=x)
                    bmodify(1,n,1,l-1,x);
            }
            if(r<n){
                int y=aquery(1,n,1,r+1);
                if(bget(1,n,1,r)!=y)
                    bmodify(1,n,1,r,y);
            }
            if(l<r)
                bupdate(1,n,1,l,r-1),cupdate(1,n,1,l,r-1);
            aupdate(1,n,1,l,r,0);
        }
        if(opt==1){
            if(l>1){
                int x=aquery(1,n,1,l-1)^1;
                if(bget(1,n,1,l-1)!=x)
                    bmodify(1,n,1,l-1,x);
            }
            if(r<n){
                int y=aquery(1,n,1,r+1)^1;
                if(bget(1,n,1,r)!=y)
                    bmodify(1,n,1,r,y);
            }
            if(l<r)
                bupdate(1,n,1,l,r-1),cupdate(1,n,1,l,r-1);
            aupdate(1,n,1,l,r,1);
        }
        if(opt==2){
            int x=bget(1,n,1,l-1),y=bget(1,n,1,r);
            if(l>1)
                bmodify(1,n,1,l-1,bget(1,n,1,l-1)^1);
            if(r<n)
                bmodify(1,n,1,r,bget(1,n,1,r)^1);
            aupdatexor(1,n,1,l,r);
        }
        if(opt==3){
            if(l==r)
                puts("0");
            else lst=section{-1,-1},printf("%d\n",bquerysum(1,n,1,l,r-1,k-1));
        }
        if(opt==4){
            if(l==r)
                puts("1");
            else printf("%d\n",bquerymax(1,n,1,l,r-1).maxx+1);
        }
    }
    return 0;
}