自动搬运

查看原文

来自洛谷，原作者为

	forest114514 AFO|成也集合幂级数，败也集合幂级数|O Fortuna, velut luna,statu variabilis.

搬运于2025-08-24 22:12:07，当前版本为作者最后更新于2024-09-16 16:38:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先大家都知道了 $O(nk\log^2 n)$ 的做法吧，就是决策单调性分治+类莫队移动指针计算贡献，这是一个很优秀的做法，但是在 $k$ 很大的时候这个做法就寄了。然后 $k$ 很大的时候众所周知的是这个东西可以 wqs 二分优化，但是此时形如 $f_{i}=\min \limits_{j<i}f_{j}+w(j,i)$ 的 DP 又不能直接决策单调性做，除非套个 cdq 多个 $\log n$，二分队列的话又不能快速计算 $w(j,i)$，区间顺序对只能 $O(\sqrt n)$ 单次询问，这样太慢了。

但是在阅读完 APIO2021 Itst 大神的课件之后我们有一种可以由冷门科技 Wilber 算法改造的小清新做法。（其实就是把 SMAWK 换成了小清新决策单调性分治）

具体地，首先用 $[c,r]$ 一段作为决策点估计 $[r+1,\min(n,r+(r+c-1))]$ 的答案，得到的数组记为 $g$，显然所有满足决策点在 $[r,c]$ 之间的位置 $g$ 就是最优解了。然后再用 $[r+1,\min(n,r+(r+c-1))]$ 一段的 $g$ 去估计这一段的答案，得到的数组 $h$。然后将 $h$ 和 $g$ 对应位置两两比对得到第一个 $h$ 比 $g$ 优的位置 $t$，显然 $[r+1,t-1]$ 位置的 $g$ 数组是最优解，这里得到的 $h_{t}$ 也是最优解，这样可以得到 $t$ 是第一个决策点 $>r$ 的点，显然此时已经算完 $[r+1,t]$ 的答案，直接把 $[c,r]$ 点对改为 $[r+1,t]$ 继续做下去即可。（特殊的，如果 $t$ 不存在就直接把 $r$ 改成 $\min(n,r+(r+c-1))$ 即可）。

放一下本题这个部分的代码 （是不是非常小清新）：

void divide(int l,int r,int L,int R,const int &_mid){//决策单调性分治
	if(l>r) return;
	int mid=l+r>>1,p=L;
	F[mid]=(NODE){G[L].val+w(L+1,mid)+_mid,G[L].ch+1};
	rep(i,L+1,min(mid-1,R)){
		delL(cl++);//卡常
		NODE tmp=(NODE){G[i].val+val+_mid,G[i].ch+1};
		if(tmp<F[mid]) F[mid]=tmp,p=i;
	}
	divide(l,mid-1,L,p,_mid);
	divide(mid+1,r,p,R,_mid);
}
int Wilber(int mid){
	int r=0,c=0;
	cl=1,cr=0,TR.tt=0,memset(TR.c,0,sizeof TR.c);
	while(r<n){
		int ri=min(n,r+r-c+1);
		F=g,G=f,divide(r+1,ri,c,r,mid);//第一部分：用f估计得到g
		F=h,G=g,divide(r+2,ri,r+1,ri,mid);//第二部分：用g估计得到h
		int t=r+2;f[r+1]=g[r+1];
		while(t<=ri&&g[t]<h[t]) f[t]=g[t],++t;//找到第一个h比j优的t
		if(t>ri) r=ri;//t不存在，[c,r]->[c,ri]
		else f[t]=h[t],c=r+1,r=t;//t存在，[c,r]->[r+1,t]
	}
	return f[n].ch;
}

注意到花费了 $O(1)$ 的次数要么让 $r$ 和 $r-c+1$ 都增大了 $O(1)$，要么让 $r-c+1$ 减少 $O(1)$，所以总长均摊是 $O(n)$的，所以一轮的时间就是 $O(n\log nP)$ （$P$ 是莫队指针移动的复杂度）的，本题一轮就是 $O(n\log^2 n)$ 的。

然后就直接套上 wqs 二分，时间复杂度 $O(n\log^2 n\log V)$，但是 Wilber 因为每次要做两次决策单调性分治的原因常数大到爆炸，卡了卡常才勉强卡进 1s。

提一句这里可以用序列分块套值域分块做到 $O(n\sqrt n)$ 的预处理，$O(1)$ 回答区间有几个数 $>/<$ 自己，然后做到 $O(n\sqrt n+n\log n\log V)$，但是常数过大而且空间 $O(n\sqrt n)$ 估计表现不是很良好。

code（注意值域上界不是 $10^8$，这里只是卡常才开这么多）：

const int N=25500;
int n,k,a[N];
struct BIT{
	int c[N],tt;
	#define lowbit(x) (x&(-x))
	void update(int u,int x){tt+=x;for(;u<=n;u+=lowbit(u)) c[u]+=x;}
	int query(int u){int res=0;for(;u;u-=lowbit(u)) res+=c[u];return res;}
}TR;
int cl,cr;
LL val;
void delR(int i){val-=TR.query(a[i]-1),TR.update(a[i],-1);}
void addR(int i){val+=TR.query(a[i]-1),TR.update(a[i],1);}
void delL(int i){val-=TR.tt-TR.query(a[i]),TR.update(a[i],-1);}
void addL(int i){val+=TR.tt-TR.query(a[i]),TR.update(a[i],1);}
LL w(int l,int r){	
	while(cr>r) delR(cr--);
	while(cl<l) delL(cl++);
	while(cr<r) addR(++cr);
	while(cl>l) addL(--cl);
	return val;
}
struct NODE{
	LL val;int ch;
	bool operator <(const NODE &T)const{
		return val==T.val?ch>T.ch:val<T.val;
	}
}f[N],g[N],h[N],*F,*G;
void divide(int l,int r,int L,int R,const int &_mid){
	if(l>r) return;
	int mid=l+r>>1,p=L;
	F[mid]=(NODE){G[L].val+w(L+1,mid)+_mid,G[L].ch+1};
	rep(i,L+1,min(mid-1,R)){
		delL(cl++);
		NODE tmp=(NODE){G[i].val+val+_mid,G[i].ch+1};
		if(tmp<F[mid]) F[mid]=tmp,p=i;
	}
	divide(l,mid-1,L,p,_mid);
	divide(mid+1,r,p,R,_mid);
}
int Wilber(int mid){
	int r=0,c=0;
	cl=1,cr=0,TR.tt=0,memset(TR.c,0,sizeof TR.c);
	while(r<n){
		int ri=min(n,r+r-c+1);
		F=g,G=f,divide(r+1,ri,c,r,mid);
		F=h,G=g,divide(r+2,ri,r+1,ri,mid);
		int t=r+2;f[r+1]=g[r+1];
		while(t<=ri&&g[t]<h[t]) f[t]=g[t],++t;
		if(t>ri) r=ri;
		else f[t]=h[t],c=r+1,r=t;
	}
	return f[n].ch;
}
LL wqs(){
	int l=0,r=1e8,ans;
	while(l<=r){
		int mid=l+r>>1;
		if(Wilber(mid)>=k) ans=mid,l=mid+1;
		else r=mid-1;
	}
	Wilber(ans);
	return f[n].val-1ll*ans*k;
}