题解 P7825【「RdOI R3」VSQ】
whiteqwq
·
·
题解
P7825 「RdOI R3」VSQ解题报告：
更好的阅读体验
题意
给定一个长度为 n 的 01 序列，共 m 次操作，每次支持区间推平，区间反转，查询区间最长 01 间隔串，查询区间长度为 k 的 01 间隔串数量。
## 分析
为什么我要做这种毒瘤 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;
}
```