P8524[Ynoi2078]（区间右移复制求和）
EnofTaiPeople
·
·
题解
Part1 题意简述：
三个操作：区间按位右移，复制，求和。
### Part2 前置知识：
[可持久化 WBLT](/blog/cjxdesmall/good-merge-wblt)；[花神游历各国](/problem/P4145)。
### Part3 正题：
如果没有复制操作，就可以暴力右移非零数，复杂度 $O(n\log_2n\log_2C)$，但有复制操作，就会影响势能，时间退化成 $O(nm)$。
使用可持久化平衡树维护复制操作，依旧考虑每一个数最多右移 $\log_2C$ 次，这样可以树上每一个节点存储右移 $[0,\log_2C]\cap Z$ 次的结果，而每一次操作会多出 $O(\log_2n)$ 个节点，这样空间复杂度是 $O(m\log_2n\log_2C)$ 的，不能通过。
如果每隔 $\frac{m}{\log_2n}$ 次操作就搜出所有节点，然后重构，就可以做到空间 $O(n\log_2C)$，但是时间有 $O((n+m)\log_2n\log_2C)$，到这里，如果实现得好一些已经可以通过了。
这里有一个小问题，就是本题给的时间和空间极度不平衡，光建立平衡树就必须 $n\log_2C$ 个 `long long`，而这样的空间已经达到了 $750MB$,显然开不下。
考虑在建树时底层分块，如果区间长度少于 $\log_2C$，就将整个区间当作一个节点，这样一棵全新的树空间是 $O(n)$ 的。
一棵可爱的 $\text{WBLT}$：
```cpp
ul sm[M][33],ans;
D n,q,a[N],t[M][2];
#define ls t[x][0]
#define rs t[x][1]
D g[M],cnt,F[M],ft;
D sz[M],L[M],b[N],rt;
inline void cp(D &x){
if(F[x]==ft)return;
F[++cnt]=ft;L[cnt]=L[x];
g[cnt]=g[x],sz[cnt]=sz[x];
t[cnt][0]=ls,t[cnt][1]=rs;
for(D i=0;i<=30;++i)
sm[cnt][i]=sm[x][i];
x=cnt;
}inline void add(D &x,D ta){
cp(x),g[x]=min(g[x]+ta,30u);
}
inline void pp(D x){
sz[x]=sz[ls]+sz[rs];
L[x]=L[ls]+L[rs];
for(D i=0;i<=30;++i){
sm[x][i]=0;
if(i+g[ls]<=30)sm[x][i]+=sm[ls][i+g[ls]];
if(i+g[rs]<=30)sm[x][i]+=sm[rs][i+g[rs]];
}
}inline void pd(D &x){
if(g[x]&&sz[x]>1){
cp(x),add(ls,g[x]);
add(rs,g[x]);
for(D i=30-g[x];~i;--i)
sm[x][i]=sm[x][i+g[x]];
for(D i=30-g[x]+1;i<=30;++i)
sm[x][i]=0;
g[x]=0;
}
}
D spt(D x,D l,D r){
if(!x||l>r)return 0;
if(l==1&&r==L[x])return x;
if(sz[x]==1){
g[++cnt]=g[x],L[cnt]=r-l+1,sz[cnt]=1;
t[cnt][0]=ls+l-1,t[cnt][1]=ls+r-1;
F[x=cnt]=ft;D i,j;
for(i=0;i<=30;++i)
for(sm[x][i]=0,j=ls;j<=rs;++j)
sm[x][i]+=a[j]>>i;
return x;
}else{
cp(x),pd(x);
if(r<=L[ls])return spt(ls,l,r);
else if(l>L[ls])return spt(rs,l-L[ls],r-L[ls]);
else{
rs=spt(rs,1,r-L[ls]),ls=spt(ls,l,L[ls]);
pp(x);return x;
}
}exit(100000);return 1e9;
}
D build(D l,D r){
D x=++cnt;F[x]=ft,g[x]=0,L[x]=r-l+1;
if(r-l<30){
ls=l,rs=r,sz[x]=1;D i,j;
for(i=0;i<=30;++i)
for(sm[x][i]=0,j=l;j<=r;++j)
sm[x][i]+=a[j]>>i;
}else{
D md=l+r>>1;ls=build(l,md);
rs=build(md+1,r);pp(x);
}return x;
}
void dfs(D x,D dat=0){
dat=min(dat+g[x],30u);
if(sz[x]>1){
dfs(ls,dat),dfs(rs,dat);
}else{
for(D i=ls;i<=rs;++i)
b[++n]=a[i]>>dat;
}
}
D mg(D L,D R){
if(!L||!R)return L|R;
D x=sz[L]>sz[R]?L:R,sm=sz[L]+sz[R];
if(sz[x]<ra*sm){
g[x=++cnt]=0,F[x]=ft;
ls=L,rs=R,pp(x);
return x;
}if(x==L){
cp(x),pd(x);
if(sz[ls]>af*sm){
rs=mg(rs,R),pp(x),g[x]=0;
return x;
}else{
D y=rs;cp(y),pd(y);
return mg(mg(ls,t[y][0]),mg(t[y][1],R));
}
}else{
cp(x),pd(x);
if(sz[rs]>af*sm){
ls=mg(L,ls),pp(x),g[x]=0;
return x;
}else{
D y=ls;cp(y),pd(y);
return mg(mg(L,t[y][0]),mg(t[y][1],rs));
}
}exit(1000000);return 1e9;
}
```
### Part4 关于常数
显然在没什么人提交时我一发得到了最优解 $(2022.9.29)$，时间最快 $1.70min$，空间最小 $160MB$，由此可见，常数优秀的 $\text{WBLT}$ 让我们不再需要卡常。时限太变态了，缩到 $30s$ 怎么样？或者把空间放到 $200MB$?不然这就是一个完全不卡常的 $\text{Ynoi}$ 了。
### Part5 后记
这篇文章只是抛砖引玉，作者听说有空间线性的做法，以及可以分裂合并的 $\text{AVL}$ 树，希望大家多多分享。