题解 CF543E 【Listening to Music】
x义x
2020-07-05 08:14:45
怎么都是主席树卡空间做法……来个官方的分块解法吧。
一开始的思路很简单，首先转化成求大于等于 $q$ 的元素数目（个人感觉更好理解？），那么就是从大到小枚举 $a_i$，然后对 $[i-m+1,i]$ 区间加一，询问就是区间求 max。但是这题强制在线+卡空间，所以我们考虑分块。
考虑对序列分块再对修改分块，对修改分块的意思就是我们只存 $\sqrt n$ 个版本。整块的修改很好搞，和普通序列分块一样，整块打tag边角暴力修改。
考虑剩下的 $\sqrt n$ 个边角修改。如果按上面的方法 $O(\sqrt n)$ 修改那必然无法接受。整块依然可以差分打tag，对于两个边角块我们直接预处理它的 max 覆盖掉原来的答案。（此处 max 不考虑边角修改的整块 tag 的贡献，但是考虑整块修改的整块 tag 的贡献，因为查询的时候我们会把它和边角修改的整块 tag 加一起，我被这个迷惑了很久）
询问就很好搞了，还是边角暴力整块查tag。
代码里每个版本除了整块 max 只存了每一块开头的元素，其实显然是和每一个元素都存等价的。
有些细节还是需要注意的，有需要的话建议多读几遍代码。（这个鬼东西真的能读吗？）
不出意外喜提最劣解。代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxN=200005,LEN=450;
int N,M,Q,len,cntb; //len 块长，cntb 块数
int bg[LEN],ed[LEN]; //bg 块开头编号，ed 块结尾编号
int inb[maxN]; //inb 元素处在的块的编号
int A[maxN],id[maxN];
bool cmp(int a,int b){
return A[a]>A[b];
}
int Lpos[maxN],Rpos[maxN]; //修改操作的左右端点编号
int Linb[maxN],Rinb[maxN]; //修改操作的左右端点所在块编号
int Lans[maxN],Rans[maxN]; //修改操作的左右端点所在块的答案
int ans[LEN],val[maxN],lzy[LEN];
int ANS[LEN][LEN],bgval[LEN][LEN];
void init(){
scanf("%d%d",&N,&M);
len=sqrt(N);
for(int i=1;i<=N;i++) inb[i]=(i-1)/len+1,bg[inb[i]]=(bg[inb[i]]?bg[inb[i]]:i),ed[inb[i]]=i;cntb=inb[N];
for(int i=1;i<=N;i++) scanf("%d",&A[i]),id[i]=i;
sort(id+1,id+N+1,cmp);
for(int i=1;i<=N;i++){
Lpos[i]=max(1,id[i]-M+1),Rpos[i]=id[i];
Linb[i]=inb[Lpos[i]],Rinb[i]=inb[Rpos[i]];
if(inb[i]!=inb[i-1]){ //存储版本，pushdown tag，保证 LansRans 有完整修改的 tag 而没有边角修改的 tag
for(int j=1;j<=N;j++) val[j]+=lzy[inb[j]];
for(int j=1;j<=cntb;j++)
ANS[inb[i]][j]=ans[j],bgval[inb[i]][j]=val[bg[j]],lzy[j]=0;
}
//修改
if(Linb[i]==Rinb[i]){
for(int j=Lpos[i];j<=Rpos[i];j++) val[j]++,ans[inb[j]]=max(ans[inb[j]],val[j]+lzy[inb[j]]);
for(int j=bg[Linb[i]];j<=ed[Linb[i]];j++) Lans[i]=max(Lans[i],val[j]);
}
else{
for(int j=Lpos[i];j<=ed[Linb[i]];j++) val[j]++,ans[inb[j]]=max(ans[inb[j]],val[j]+lzy[inb[j]]);
for(int j=Linb[i]+1;j<=Rinb[i]-1;j++) lzy[j]++,ans[j]++;
for(int j=bg[Rinb[i]];j<=Rpos[i];j++) val[j]++,ans[inb[j]]=max(ans[inb[j]],val[j]+lzy[inb[j]]);
for(int j=bg[Linb[i]];j<=ed[Linb[i]];j++) Lans[i]=max(Lans[i],val[j]);
for(int j=bg[Rinb[i]];j<=ed[Rinb[i]];j++) Rans[i]=max(Rans[i],val[j]);
}
}
}
int lstans;
int brute_query(int L,int R,int bid,int tmp,int q){
int ANS=0;
for(int i=bg[bid];i<L;i++) tmp+=(A[i+M]>=q)-(A[i]>=q);
for(int i=L;i<=R;i++) ANS=max(ANS,tmp),tmp+=(A[i+M]>=q)-(A[i]>=q);
return ANS;
}
int main(){
init();
scanf("%d",&Q);
while(Q--){
int QL,QR,QQ,QX;scanf("%d%d%d",&QL,&QR,&QQ);QQ^=lstans;
A[N+1]=QQ;QX=upper_bound(id+1,id+N+1,N+1,cmp)-id-1;
memset(lzy,0,sizeof(lzy));
for(int i=1;i<=cntb;i++) ans[i]=ANS[inb[QX]][i];
int bgvalL=bgval[inb[QX]][inb[QL]],bgvalR=bgval[inb[QX]][inb[QR]];
for(int i=bg[inb[QX]];i<=QX;i++){
ans[Linb[i]]=Lans[i];
if(Linb[i]!=Rinb[i]) ans[Rinb[i]]=Rans[i],lzy[Linb[i]+1]++,lzy[Rinb[i]]--;
if(Lpos[i]<=bg[inb[QL]]&&bg[inb[QL]]<=Rpos[i]) bgvalL++;
if(Lpos[i]<=bg[inb[QR]]&&bg[inb[QR]]<=Rpos[i]) bgvalR++;
}
for(int i=1;i<=cntb;i++) lzy[i]+=lzy[i-1];
int ANS=0;
if(inb[QL]==inb[QR]) ANS=brute_query(QL,QR,inb[QL],bgvalL,QQ);
else{
ANS=max(ANS,brute_query(QL,ed[inb[QL]],inb[QL],bgvalL,QQ));
ANS=max(ANS,brute_query(bg[inb[QR]],QR,inb[QR],bgvalR,QQ));
for(int i=inb[QL]+1;i<=inb[QR]-1;i++)
ANS=max(ANS,ans[i]+lzy[i]);
}
printf("%d\n",lstans=M-ANS);
}
return 0;
}
```