标签：return int mid 笔记 long 优化 DP dis

通过某些 trick 以优化复杂度。

I.单调队列/单调栈

单调队列/单调栈优化 DP 是对简单决策单调性 DP 的常见优化。

I.[HNOI2005]星际贸易

第一问直接背包一下就行，是模板。

然后，因为题面中的一句话：

……并使得只有一种获得最大贸易值的方法。

因此我们可以直接根据各状态是从哪个前驱状态转移而来直接得出那些必须要访问的星球。

注意，你所规定的这条路径必须满足贸易值最大（不管合不合法（走不走的完），但贸易值必须最大），不然你就会像我一样死活看不懂第二组样例……

我们考虑DP。

设\(f[i][j]\)表示：当前在位置\(i\)，已经进行了所有的操作随时可以起飞，并且当前舰上还有\(j\)份燃料的最小代价。

思路1.暴力DP：

我们有

\(f[i][j]=\min\limits_{k=\max(i\text{之前距离}i\text{最近的那个必须访问的星球},i\text{之前飞船不维修最远能到的那个星球})}^{i-1}\{\min\limits_{l=2}^{\min(r,j+2)}f[k][l]+(j-l+2)*p[i]+fx[i]\}\)

其中，\(p[i]\)是\(i\)星球一份暗物质的费用，\(fx[i]\)是\(i\)位置修船的费用。

复杂度\(O(n^4)\)，可以拿到\(55\%\)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,r,l,a[2010],b[2010],dis[2010],p[2010],fx[2010],f[2010][4010],mp,mn=0x3f3f3f3f;
bool cho[2010];
int main(){
	scanf("%d%d%d%d",&n,&m,&r,&l),memset(f,0x80,sizeof(f)),r=min(r,2*n);
	if(r<2){puts("Poor Coke!");return 0;}
	for(int i=1;i<=n;i++)scanf("%d%d%d%d%d",&a[i],&b[i],&dis[i],&p[i],&fx[i]);
	for(int i=1;i<=n;i++)if(dis[i]-dis[i-1]>l){puts("Poor Coke!");return 0;}
	f[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<a[i];j++)f[i][j]=f[i-1][j];
		for(int j=a[i];j<=m;j++)f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]);
	}
	for(int i=0;i<=m;i++)if(f[n][mp]<f[n][i])mp=i;
	for(int i=n,j=mp;i;i--){
		if(f[i][j]==f[i-1][j])continue;
		cho[i]=true,j-=a[i];
	}
//	for(int i=1;i<=n;i++)printf("%d ",cho[i]);puts("");
	mp=f[n][mp];
	memset(f,0x3f,sizeof(f));
	f[0][r]=0;
	for(int i=1;i<=n;i++)for(int j=0;j<=r;j++){
		for(int k=i-1;k>=0;k--){
			if(dis[i]-dis[k]>l)break;
			if(!p[i]){
				if(j>=2)f[i][j]=min(f[i][j],f[k][j+2]+fx[i]);
				else f[i][j]=0x3f3f3f3f;
			}
			else for(int l=2;l<=min(j+2,r);l++)f[i][j]=min(f[i][j],f[k][l]+(j-l+2)*p[i]+fx[i]);
			if(cho[k])break;
		}
//		printf("%d %d:%d\n",i,j,f[i][j]);
	}
	for(int i=0;i<=r;i++)mn=min(mn,f[n][i]);
	if(mn==0x3f3f3f3f){puts("Poor Coke!");return 0;}
	printf("%d %d\n",mp,mp-mn);
	return 0;
} 

思路2.背包

因为在位置\(i\)买暗物质的操作实际上就是一个完全背包的效果，所以我们完全可以不枚举\(l\)，转而采用完全背包的形式在\(O(n^3)\)解决它。可以拿到\(65\%\)。

即：\(f[i][j]=\min(f[k][j+2]+f[i],f[i][j-1]+p[i])\)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,r,l,a[2010],b[2010],dis[2010],p[2010],fx[2010],f[2010][4010],mp,mn=0x3f3f3f3f;
bool cho[2010];
int main(){
	scanf("%d%d%d%d",&n,&m,&r,&l),memset(f,0x80,sizeof(f)),r=min(r,2*n);
	if(r<2){puts("Poor Coke!");return 0;}
	for(int i=1;i<=n;i++)scanf("%d%d%d%d%d",&a[i],&b[i],&dis[i],&p[i],&fx[i]);
	for(int i=1;i<=n;i++)if(dis[i]-dis[i-1]>l){puts("Poor Coke!");return 0;}
	f[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<a[i];j++)f[i][j]=f[i-1][j];
		for(int j=a[i];j<=m;j++)f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]);
	}
	for(int i=0;i<=m;i++)if(f[n][mp]<f[n][i])mp=i;
	for(int i=n,j=mp;i;i--){
		if(f[i][j]==f[i-1][j])continue;
		cho[i]=true,j-=a[i];
	}
//	for(int i=1;i<=n;i++)printf("%d ",cho[i]);puts("");
	mp=f[n][mp];
	memset(f,0x3f,sizeof(f));
	f[0][r]=0;
	for(int i=1;i<=n;i++)for(int j=0;j<=r;j++){
		for(int k=i-1;k>=0;k--){
			if(dis[i]-dis[k]>l)break;
			f[i][j]=min(f[i][j],f[k][j+2]+fx[i]);
			if(cho[k])break;
		}
		if(p[i]&&j)f[i][j]=min(f[i][j],f[i][j-1]+p[i]);
//		printf("%d %d:%d\n",i,j,f[i][j]);
	}
	for(int i=0;i<=r;i++)mn=min(mn,f[n][i]);
	if(mn==0x3f3f3f3f){puts("Poor Coke!");return 0;}
	printf("%d %d\n",mp,mp-mn);
	return 0;
} 

思路3.单调队列

因为\(f[k][j+2]\)这个东西随着\(i\)的增加，每个\(i\)都要枚举一下，因此可以采用单调队列来保存每个暗物质数量\(j\)可以转移的最优位置，并且按照距离及时弹出已经距离\(i\)太远的位置。复杂度\(O(n^2)\)，期望得分\(100\%\)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,r,l,a[2010],b[2010],dis[2010],p[2010],fx[2010],f[2010][4010],mp,mn=0x3f3f3f3f;
deque<int>q[2010];
bool cho[2010];
int main(){
	scanf("%d%d%d%d",&n,&m,&r,&l),memset(f,0x80,sizeof(f)),r=min(r,2*n);
	if(r<2){puts("Poor Coke!");return 0;}
	for(int i=1;i<=n;i++)scanf("%d%d%d%d%d",&a[i],&b[i],&dis[i],&p[i],&fx[i]);
	for(int i=1;i<=n;i++)if(dis[i]-dis[i-1]>l){puts("Poor Coke!");return 0;}
	f[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<a[i];j++)f[i][j]=f[i-1][j];
		for(int j=a[i];j<=m;j++)f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]);
	}
	for(int i=0;i<=m;i++)if(f[n][mp]<f[n][i])mp=i;
	for(int i=n,j=mp;i;i--){
		if(f[i][j]==f[i-1][j])continue;
		cho[i]=true,j-=a[i];
	}
//	for(int i=1;i<=n;i++)printf("%d ",cho[i]);puts("");
	mp=f[n][mp];
	memset(f,0x3f,sizeof(f));
	f[0][r]=0;
	for(int i=1;i<=n;i++)for(int j=0;j<=r;j++){
		while(!q[j+2].empty()&&dis[i]-dis[q[j+2].front()]>l)q[j+2].pop_front();
		while(!q[j+2].empty()&&f[q[j+2].back()][j+2]>=f[i-1][j+2])q[j+2].pop_back();
		q[j+2].push_back(i-1);
		f[i][j]=min(f[i][j],f[q[j+2].front()][j+2]+fx[i]);
		if(p[i]&&j)f[i][j]=min(f[i][j],f[i][j-1]+p[i]);
		if(cho[i])q[j+2].clear();
//		printf("%d %d:%d\n",i,j,f[i][j]);
	}
	for(int i=0;i<=r;i++)mn=min(mn,f[n][i]);
	if(mn==0x3f3f3f3f){puts("Poor Coke!");return 0;}
	printf("%d %d\n",mp,mp-mn);
	return 0;
} 

II.[SCOI2010]股票交易

这题状态很好想：设\(f[i][j]\)表示：第\(i\)天，持有\(j\)支股票，的最大收益。

然后我就脑残了，想了个\(O(n^2m^2)\)的弱智初始DP，然后就WA掉惹。

实际上转移也挺简单的。设第\(i\)天买股票花\(a_i\)元，卖股票花\(b_i\)元，可以买\(A_i\)次，卖\(B_i\)次。

1. 从起始状态转移。即，如果有\(j\leq A_i\)，\(f[i][j]=-j*a_i\)。

2. 这一时刻不买。即，\(f[i][j]=f[i-1][j]\)。

3. 从\(i-w-1\)时刻买。即，\(f[i][j]=\max\{f[i-w-1][l]+\text{买或卖的费用}\}\)

然后1和2都是\(nm\)的；3套上单调队列也是\(nm\)的；总复杂度\(O(nm)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,w,a[2010],b[2010],A[2010],B[2010];
ll f[2010][2010];
deque<int>q;
int main(){
	scanf("%d%d%d",&n,&m,&w),w++,memset(f,0x80,sizeof(f));
	for(int i=1;i<=n;i++)scanf("%d%d%d%d",&a[i],&b[i],&A[i],&B[i]);
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(j<=A[i])f[i][j]=-j*a[i];
			f[i][j]=max(f[i][j],f[i-1][j]);	
		}
		if(i-w<=0)continue;
		int k=i-w;
		q.clear();
		for(int j=0;j<=m;j++){
			while(!q.empty()&&j-q.front()>A[i])q.pop_front();
			while(!q.empty()&&f[k][q.back()]-(j-q.back())*a[i]<=f[k][j])q.pop_back();
			q.push_back(j);
			f[i][j]=max(f[i][j],f[k][q.front()]-(j-q.front())*a[i]);
		}
		q.clear();
		for(int j=m;j>=0;j--){
			while(!q.empty()&&q.front()-j>B[i])q.pop_front();
			while(!q.empty()&&f[k][q.back()]+(q.back()-j)*b[i]<=f[k][j])q.pop_back();
			q.push_back(j);
			f[i][j]=max(f[i][j],f[k][q.front()]+(q.front()-j)*b[i]);
		}
	}
//	for(int i=1;i<=n;i++){for(int j=0;j<=m;j++)printf("%d ",f[i][j]);puts("");}
	printf("%lld\n",f[n][0]);
	return 0;
}

III.[NOI2005]瑰丽华尔兹

思路1.\(O(N^2T)\)暴力DP——设\(f[t,i,j]\)表示\(t\)时刻在位置\((i,j)\)时的最长路径。显然会T。

思路2.\(O(N^2T)\)暴力DP——观察到一段长为\(len\)的时间内向某个方向每时刻移动一格，等价于总共移动\(len\)格。又因为随时可以停止，所以可以移动\(0\sim len\)格中任意长度。暴力枚举转移几格即是上述复杂度。

思路3.\(O(N^2K)\)暴力DP——因为\(len\)在一次转移中不变，所以实际上就是经典老题滑动窗口，直接暴力硬套单调队列即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int f[2][210][210],n,m,p,sx,sy,res;
char s[210][210];
int main(){
	scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&p),memset(f,0xc0,sizeof(f)),f[0][sx][sy]=0;
	for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)s[i][j]=(s[i][j]=='.');
	int now=1,las=0;
	for(int len,dir;p--;now^=1,las^=1){
		scanf("%d%d",&len,&dir),len=dir-len+1,scanf("%d",&dir);
//		printf("%d %d\n",len,dir);
		if(dir==1){
			for(int j=1;j<=m;j++){
				deque<int>q;
				for(int i=n;i;i--){
					if(!s[i][j]){q.clear();continue;}
					while(!q.empty()&&(q.front()-i)>len)q.pop_front();
					while(!q.empty()&&(f[las][q.back()][j]+(q.back()-i))<=f[las][i][j])q.pop_back();
					q.push_back(i);
					f[now][i][j]=f[las][q.front()][j]+(q.front()-i);
				}
			}
		}
		if(dir==2){
			for(int j=1;j<=m;j++){
				deque<int>q;
				for(int i=1;i<=n;i++){
					if(!s[i][j]){q.clear();continue;}
					while(!q.empty()&&(i-q.front())>len)q.pop_front();
					while(!q.empty()&&(f[las][q.back()][j]+(i-q.back()))<=f[las][i][j])q.pop_back();
					q.push_back(i);
					f[now][i][j]=f[las][q.front()][j]+(i-q.front());
				}
			}
		}
		if(dir==3){
			for(int i=1;i<=n;i++){
				deque<int>q;
				for(int j=m;j;j--){
					if(!s[i][j]){q.clear();continue;}
					while(!q.empty()&&(q.front()-j)>len)q.pop_front();
					while(!q.empty()&&(f[las][i][q.back()]+(q.back()-j))<=f[las][i][j])q.pop_back();
					q.push_back(j);
					f[now][i][j]=f[las][i][q.front()]+(q.front()-j);
				}
			}
		}
		if(dir==4){
			for(int i=1;i<=n;i++){
				deque<int>q;
				for(int j=1;j<=m;j++){
					if(!s[i][j]){q.clear();continue;}
					while(!q.empty()&&(j-q.front())>len)q.pop_front();
					while(!q.empty()&&(f[las][i][q.back()]+(j-q.back()))<=f[las][i][j])q.pop_back();
					q.push_back(j);
					f[now][i][j]=f[las][i][q.front()]+(j-q.front());
				}
			}
		}
//		for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)printf("%11d ",f[now][i][j]);puts("");}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)res=max(res,f[las][i][j]);
	printf("%d\n",res);
	return 0;
}

IV.[POI2014]ZAL-Freight

题解

II.斜率优化

斜率优化是经典套路了。

I.单调队列/单调栈线性复杂度斜率优化

通过单调队列，我们可以进行一些线性序列上的 DP。

I.任务安排

设\(t[i]\)表示原题中的\(t_i\)的前缀和，\(c[i]\)表示原题中\(f_i\)的前缀和，\(m\)表示启动时间\(s\)。

思路1：\(n^3\)DP：

设\(f[i][j]\)表示：前\(i\)个位置，分成\(j\)组，的最快时间。

则有\(f[i][j]=\min\limits_{k=0}^{i-1}\{f[k][j-1]+(t[i]+m*j)*(c[i]-c[k])\}\)。

思路2：\(n^2\)DP：

观察到我们每在第\(i\)个点前多分出一组，则在\(i\)后面所有东西的时间都会向后拖\(m\)时刻，共计造成\(m*(c[n]-c[i])\)点费用，

因此我们可以设\(f[i]\)表示前\(i\)个位置的最短时间，

则有\(f[i]=\min\limits_{j=0}^{i-1}\{f[j]+m*(c[n]-c[j])+t[i]*(c[i]-c[j])\}\)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,f[10010],t[10010],c[10010];
int main(){
	scanf("%d%d",&n,&m),memset(f,0x3f3f3f3f,sizeof(f)),f[0]=0;
	for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&c[i]),t[i]+=t[i-1],c[i]+=c[i-1];
	for(int i=1;i<=n;i++)for(int j=0;j<i;j++)f[i]=min(f[i],f[j]+m*(c[n]-c[j])+t[i]*(c[i]-c[j]));
	printf("%d\n",f[n]);
	return 0;
}

思路3：考虑斜率优化。

设\(j<k<i\)，且\(j\)比\(k\)更优。

则有

\(f[j]+m*(c[n]-c[j])+t[i]*(c[i]-c[j])<f[k]+m*(c[n]-c[k])+t[i]*(c[i]-c[k])\)

拆括号

\(f[j]+m*c[n]-m*c[j]+t[i]*c[i]-t[i]*c[j]<f[k]+m*c[n]-m*c[k]+t[i]*c[i]-t[i]*c[k]\)

消元

\(f[j]-m*c[j]-t[i]*c[j]<f[k]-m*c[k]-t[i]*c[k]\)

移项并合并

\(f[j]-f[k]-(m+t[i])*(c[j]-c[k])<0\)

再移

\(f[j]-f[k]<(m+t[i])*(c[j]-c[k])\)

注意因为\(j<k\)，且\(c\)是前缀和，则\(c[j]<c[k]\)。不等式两边除以负数，应该换方向。

最终得到

\(\dfrac{f[j]-f[k]}{c[j]-c[k]}>m+t[i]\)

左边的东西仅与\(j\)和\(k\)有关；右边的东西是单调的（\(t\)也是前缀和）；

因此就可以斜率优化辣。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,t[10100],c[10100],f[10100],q[10100],l,r;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&c[i]),t[i]+=t[i-1],c[i]+=c[i-1];
	for(int i=1;i<=n;i++){
		while(r-l&&(f[q[l]]-f[q[l+1]])>=(c[q[l]]-c[q[l+1]])*(m+t[i]))l++;
		f[i]=f[q[l]]+m*(c[n]-c[q[l]])+t[i]*(c[i]-c[q[l]]);
		while(r-l&&(f[q[r-1]]-f[q[r]])*(c[q[r]]-c[i])>=(f[q[r]]-f[i])*(c[q[r-1]]-c[q[r]]))r--;
		q[++r]=i;
	}
	printf("%d\n",f[n]);
	return 0;
}

II.[SDOI2016]征途

这题已经在我的任务列表里吃了大半年的灰了……（去年7月加进来的，到现在已经8个月了）

开始推式子。

我们设第\(i\)天的路程是\(l_i\)，

则我们的目的是最小化

\(s^2=\sum\limits_{i=1}^m\dfrac{(\overline{l}-l_i)^2}{m}\)

代入平均值的定义

\(s^2=\dfrac{\sum\limits_{i=1}^m\bigg(\tfrac{\sum\limits_{j=1}^ml_j}{m}-l_i\bigg)^2}{m}\)

暴力展开平方项

\(s^2=\dfrac{\sum\limits_{i=1}^m\bigg(\dfrac{\sum\limits_{j=1}^ml_j}{m}\bigg)^2-2*l_i*\dfrac{\sum\limits_{j=1}^ml_j}{m}+l_i^2}{m}\)

分离\(\Sigma\)

\(s^2=\dfrac{m\bigg(\dfrac{\sum\limits_{j=1}^ml_j}{m}\bigg)^2-2*\sum\limits_{i=1}^ml_i*\dfrac{\sum\limits_{j=1}^ml_j}{m}+\sum\limits_{i=1}^ml_i^2}{m}\)

稍作整合

\(s^2=\dfrac{\dfrac{(\sum\limits_{j=1}^ml_j)^2}{m}-2*\dfrac{(\sum\limits_{j=1}^ml_j)^2}{m}+\sum\limits_{i=1}^ml_i^2}{m}\)

合并

\(s^2=\dfrac{-\dfrac{(\sum\limits_{j=1}^ml_j)^2}{m}+\sum\limits_{i=1}^ml_i^2}{m}\)

乘以\(m^2\)

\(s^2m^2=-(\sum\limits_{j=1}^ml_j)^2+m\sum\limits_{i=1}^ml_i^2\)

右边的等式中，左边是定值（等于总路程的平方）；右边则要我们最小化\(\sum\limits_{i=1}^ml_i^2\)。

设\(f[i][j]\)表示：前\(i\)天内分成了\(j\)段的最小平方和。再设\(s_i\)表示路程的前缀和。

则有\(f[i][j]=\min\limits_{k=0}^{i-1}\{f[k][j-1]+(s_i-s_k)^2\}\)

可以\(n^2m\)的进行暴力DP，能拿到\(60\%\)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,s[3010],f[3010][3010];
int main(){
	scanf("%d%d",&n,&m),memset(f,0x3f3f3f3f,sizeof(f));
	for(int i=1;i<=n;i++)scanf("%d",&s[i]),s[i]+=s[i-1];
	f[0][0]=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=min(i,m);j++)for(int k=0;k<i;k++)f[i][j]=min(f[i][j],f[k][j-1]+(s[i]-s[k])*(s[i]-s[k]));
	printf("%d\n",m*f[n][m]-s[n]*s[n]);
	return 0;
} 

我们尝试按段数DP，而不是按天数DP。即，在\(f[i][j]\)中，优先枚举\(j\)。

在枚举\(j\)后，我们就可以暂时忽略\(j\)这一维了。

我们有\(f[i]=\min\limits_{j=0}^{i-1}\{F[j]+(s_i-s_j)^2\}\)。其中，这个\(F[j]\)是上一轮DP时的\(f\)值，即原本的\(f[i][j-1]\)（注意这个\(j\)和上面递推式里面的枚举的\(j\)不是同一个\(j\)）

假设\(j<k<i\)，且\(j\)比\(k\)优，

则有

\(F[j]+(s_i-s_j)^2<F[k]+(s_i-s_k)^2\)

暴力展开

\(F[j]+s_i^2-s_is_j+s_j^2<F[k]+s_i^2-s_is_k+s_k^2\)

合并同类项

\(F[j]-s_is_j+s_j^2<F[k]-s_is_k+s_k^2\)

移项

\(F[j]-F[k]+s_j^2-s_k^2<s_is_j-s_is_k\)

提一下

\(F[j]-F[k]+s_j^2-s_k^2<s_i(s_j-s_k)\)

除过去（注意\(s_j-s_k\)是负的！！！）

\(\dfrac{F[j]-F[k]+s_j^2-s_k^2}{s_j-s_k}>s_i\)

左边的东西与\(i\)无关；右边的东西单调增；

那不就可以了吗！！！

维护下凸壳，直接斜率优化硬套，完事。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,s[3010],f[3010][3010],q[3010],l,r;
int main(){
	scanf("%d%d",&n,&m),memset(f,0x3f3f3f3f,sizeof(f));
	for(int i=1;i<=n;i++)scanf("%d",&s[i]),s[i]+=s[i-1];
	f[0][0]=0;
	for(int j=1;j<=m;j++){
		l=r=0;
		for(int i=1;i<=n;i++){
			while(r-l&&f[q[l]][j-1]-f[q[l+1]][j-1]+s[q[l]]*s[q[l]]-s[q[l+1]]*s[q[l+1]]>=2*s[i]*(s[q[l]]-s[q[l+1]]))l++;
			f[i][j]=f[q[l]][j-1]+(s[i]-s[q[l]])*(s[i]-s[q[l]]);
			while(r-l&&(f[q[r-1]][j-1]-f[q[r]][j-1]+s[q[r-1]]*s[q[r-1]]-s[q[r]]*s[q[r]])*(s[q[r]]-s[i])>=(f[q[r]][j-1]-f[i][j-1]+s[q[r]]*s[q[r]]-s[i]*s[i])*(s[q[r-1]]-s[q[r]]))r--;
			q[++r]=i; 
		}
	}
	printf("%d\n",m*f[n][m]-s[n]*s[n]);
	return 0;
} 

III.[HDU3507]Print Article

没什么好说的，这题比任务安排还水，随便推推完事。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s[500100],f[500100],q[500100],l,r;
signed main(){
	while(scanf("%lld%lld",&n,&m)!=EOF){
		for(int i=1;i<=n;i++){
			scanf("%lld",&s[i]);
			if(!s[i]){i--,n--;continue;}
			s[i]+=s[i-1];
		}
//		for(int i=1;i<=n;i++)printf("%d ",s[i]);puts("");
		l=r=0;
		for(int i=1;i<=n;i++){
			while(r-l&&f[q[l]]-f[q[l+1]]+s[q[l]]*s[q[l]]-s[q[l+1]]*s[q[l+1]]>=2*s[i]*(s[q[l]]-s[q[l+1]]))l++;
			f[i]=f[q[l]]+m+(s[i]-s[q[l]])*(s[i]-s[q[l]]);
			while(r-l&&(f[q[r-1]]-f[q[r]]+s[q[r-1]]*s[q[r-1]]-s[q[r]]*s[q[r]])*(s[q[r]]-s[i])>=(f[q[r]]-f[i]+s[q[r]]*s[q[r]]-s[i]*s[i])*(s[q[r-1]]-s[q[r]]))r--;
			q[++r]=i;
		}
		printf("%lld\n",f[n]);
	}
	return 0;
}

IV.CF311B Cats Transport

推式子时间到~~~

我们首先对题目中的\(d_i\)做前缀和，求出每座山距离原点距离；

然后对于第\(i\)只猫，如果一个饲养员在\(t_i-d_{h_i}\)时刻以后出发就可以接到它；

注意，饲养员可以在负时刻就出发！！！我之前想多了以为只能在非负时刻出发而纳闷了好半天

我们设\(t_i-d_{h_i}\)为新的\(t_i\)，然后将所有的\(t_i\)排序。

然后开始DP：

设\(f[i][j]\)表示：前\(i\)只猫，派出\(j\)个人，的最优时间。再设\(s_i\)表示\(t_i\)的前缀和。

则有\(f[i][j]=\min\limits_{k=0}^{i-1}\{f[k][j-1]+t_i*(i-k)-(s_i-s_k)\}\)

我们这样就可以写出\(O(m^2p)\)的代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p,d[100100],t[100100],s[100100],f[100100][110],qwq=0x3f3f3f3f3f3f3f3f;
signed main(){
	scanf("%lld%lld%lld",&n,&m,&p),memset(f,0x3f3f3f3f,sizeof(f));
	for(int i=2;i<=n;i++)scanf("%lld",&d[i]),d[i]+=d[i-1];
//	for(int i=1;i<=n;i++)printf("%lld ",d[i]);puts("");
	for(int i=1,x,y;i<=m;i++)scanf("%lld%lld",&x,&y),t[i]=y-d[x];
//	printf("%lld\n",res);
//	for(int i=1;i<=m;i++)printf("%lld ",t[i]);puts("");
	sort(t+1,t+m+1);
	for(int i=1;i<=m;i++)s[i]=s[i-1]+t[i];
//	for(int i=1;i<=m;i++)printf("%lld ",t[i]);puts("");
	f[0][0]=0;
	for(int j=1;j<=p;j++)for(int i=1;i<=m;i++)for(int k=0;k<i;k++)f[i][j]=min(f[i][j],f[k][j-1]+(i-k)*t[i]-(s[i]-s[k]));
	for(int i=1;i<=p;i++)qwq=min(qwq,f[m][i]);
	printf("%lld\n",qwq);
	return 0;
}

然后考虑斜率优化一下：

在\(f[i][j]\)中，我们按照列优先（先枚举\(j\)）的顺序进行DP；并且，设\(f[i][j-1]\)为\(F[i]\)。

设\(j<k<i\)（不是同一个\(j\)）。则如果\(j\)比\(k\)优，则有：

\(F_j+t_i*(i-j)-(s_i-s_j)<F_k+t_i*(i-k)-(s_i-s_k)\)

拆开

\(F_j+i*t_i-j*t_i-s_i+s_j<F_k+i*t_i-k*t_i-s_i-s_k\)

抵消

\(F_j-j*t_i+s_j<F_k-k*t_i+s_k\)

移项

\(F_j-F_k+s_j-s_k<(j-k)*t_i\)

除过去（注意\(j-k\)是负数）

\(\dfrac{F_j-F_k+s_j-s_k}{j-k}>t_i\)

右边的\(t_i\)是递增的（排过序了），因此可以采用单调队列维护斜率；然后维护一个下凸壳即可。复杂度\(O(mp)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p,d[100100],t[100100],s[100100],f[100100][110],qwq=0x3f3f3f3f3f3f3f3f,l,r,q[100100];
signed main(){
	scanf("%lld%lld%lld",&n,&m,&p),memset(f,0x3f3f3f3f,sizeof(f));
	for(int i=2;i<=n;i++)scanf("%lld",&d[i]),d[i]+=d[i-1];
//	for(int i=1;i<=n;i++)printf("%lld ",d[i]);puts("");
	for(int i=1,x,y;i<=m;i++)scanf("%lld%lld",&x,&y),t[i]=y-d[x];
//	printf("%lld\n",res);
//	for(int i=1;i<=m;i++)printf("%lld ",t[i]);puts("");
	sort(t+1,t+m+1);
	for(int i=1;i<=m;i++)s[i]=s[i-1]+t[i];
//	for(int i=1;i<=m;i++)printf("%lld ",t[i]);puts("");
	f[0][0]=0;
	for(int j=1;j<=p;j++){
		l=r=0;
		for(int i=1;i<=m;i++){
			while(r-l&&(f[q[l]][j-1]-f[q[l+1]][j-1]+s[q[l]]-s[q[l+1]])>=(q[l]-q[l+1])*t[i])l++;
			f[i][j]=f[q[l]][j-1]+(i-q[l])*t[i]-(s[i]-s[q[l]]);
			while(r-l&&(f[q[r-1]][j-1]-f[q[r]][j-1]+s[q[r-1]]-s[q[r]])*(q[r]-i)>=(f[q[r]][j-1]-f[i][j-1]+s[q[r]]-s[i])*(q[r-1]-q[r]))r--;
			q[++r]=i;
		}
	}
	for(int i=1;i<=p;i++)qwq=min(qwq,f[m][i]);
	printf("%lld\n",qwq);
	return 0;
}

V.[NOI2016] 国王饮水记

首先，我们一定可以舍去那些高度比 \(h_1\) 还小的城市，并且将剩余的高度比 \(h_1\) 大的城市排序，使得 \(h_1\) 到 \(h_n\) 递增。

我们不妨从三座城市想起。假如可以合并两次，应该怎么合并？

先合并 \((1,2)\)，再合并 \((2,3)\)，因为这样更多的水被贡献给了 \(1\)，对吧？

由此我们得出了第一个Obeservation：越早合并的城市，高度越低。这也就意味着，我们每次合并的城市，必定是高度递增的一段，且前一次合并的所有城市的水量都低于后一次合并的城市。

那如果只能合并一次呢？

首先，\((1,3)\) 肯定是要合并的。那么，\(2\) 要不要并进去呢？这就要看 \((1,3)\) 合并后，\(2\) 是否比 \(1,3\) 的高度高了。

于是我们得到了用一次合并来合并城市 \(1\) 与某段城市 \([l,r]\) 的策略：先合并城市 \(1\) 和 \(r\)，然后依次合并 \(r-1,r-2,\dots,l\)，直到并进去会使得平均值减小。

有了这两个观察，我们就可以开始DP了：设 \(f_{i,j}\) 表示前 \(i\) 个位置合并 \(j\) 次的最优答案。则 \(f_{i,j}=\max\limits_{k<i}\left\{\dfrac{f_{k,j-1}+s_i-s_k}{i-k+1}\right\}\)。

同时，为了处理上面“合并 \([l,r]\) 时实际上是合并了 \([l,r]\) 中一段最优的后缀 \([l',r]\)”的结论，\(f_{i,j}\) 还要与 \(f_{i-1,j},f_{i-2,j},\dots,f_{1,j}\) 取 \(\max\)，用来表示位置 \(i\) 不合并到某段区间中。

这种“合并 \(k\) 次”的DP，要优化肯定要按照合并次数DP。于是我们设 \(f_i\) 表示当前的DP数组，\(g_i\) 表示上一轮DP（合并次数少一）的DP数组。

则式子修改为 \(f_i=\max\limits_{j<i}\left\{\dfrac{g_j+s_i-s_j}{i-j+1}\right\}\)。

这时候，如果再观察到“合并次数 \(m\) 可以与 \(n-1\) 取 \(\min\)”的话，就可以 \(O(n^3)\) 地直接用 double 暴力DP了。

可以取得 \(58\) 分的好成绩。代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,p,h[8010];
double f[8010],g[8010],s[8010];
void solve(){
	for(int i=1;i<=n;i++)f[i]=-0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)f[i]=max(f[i],(g[j]+s[i]-s[j])/(i-j+1));
	for(int i=1;i<=n;i++)f[i]=max(f[i],f[i-1]);
}
int main(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;i++)scanf("%d",&h[i]);
	sort(h+2,h+n+1),reverse(h+2,h+n+1);
	while(h[n]<=h[1])n--;
	reverse(h+2,h+n+1);
//	for(int i=1;i<=n;i++)printf("%d ",h[i]);puts("");
	for(int i=1;i<=n;i++)s[i]=s[i-1]+h[i];
	m=min(m,n-1);
	for(int i=1;i<=n;i++)f[i]=h[1];
	while(m--){
		for(int i=1;i<=n;i++)g[i]=f[i];
		solve();
	}
	printf("%lf\n",f[n]);
	return 0;
}

然后，有一个推论是“合并 \([l,r]\) 时实际上是合并了 \([l,r]\) 中一段最优的后缀 \([l',r]\)”这个东西实际上是没有必要的，因为若 \([l,r]\) 只合并了 \([l',r]\)，而 \([l,l'-1]\) 未被合并，但是以 \(l-1\) 结尾的一段区间却被合并了的话，我们完全可以将它向右移至以 \(l'-1\) 结尾，并使得答案更大。因此，这个结论变换为，所有被合并过的位置是 \(h\) 数组的一段后缀。（虽然这个结论是我在写题解时才发现的，因此代码中完全没有用到这个结论）

这之后，我们掏出转移式 \(f_i=\max\limits_{j<i}\left\{\dfrac{g_j+s_i-s_j}{i-j+1}\right\}\)。

它可以被解释为 \((s_i,i+1)\) 与 \((s_j-g_j,j)\) 两点间的斜率。

因为我们已经将 \(h\) 排过序，所以 \(s\) 就不止有递增的性质——它还是凹的！

尽管 \((s_j-g_j,j)\) 可能在平面上随机分布，但是因为 \(s\) 的凹性，其就具有决策单调性（随着 \(i\) 的增大，每个点到它的斜率都在变大（这是由凹性决定的），而越大的 \(j\) 变大的速度就越快（因为所有的 \(j\) 的分子增长速度都是一致的，但是分母增长速度是 \(j\) 越大的越慢），终将在什么时候超越小的 \(j\)），因此我们可以对其进行斜率优化！

具体而言，发现最优决策点 \(j\) 只有可能在下凸壳上，于是就维护下凸壳，然后从下凸壳的队首进行转移即可。

明显单次复杂度就做到了 \(O(n)\)。这样子，若仍然用 double 暴力转移，复杂度是 \(O(n^2)\)，可以取得 \(64\) 分的好成绩。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> pdd;
int n,m,p,h[8010],l,r;
double f[8010],g[8010],s[8010];
pdd dat[8010];
int q[8010];
double slope(pdd x,pdd y){return (x.second-y.second)/(x.first-y.first);}
void solve(){
	l=r=0;
	for(int i=1;i<=n;i++){
		dat[i]=make_pair(i,s[i]-g[i]);
		while(r-l>=2&&slope(dat[q[r-2]],dat[q[r-1]])>slope(dat[q[r-1]],dat[i]))--r;
		q[r++]=i;
		pdd I=make_pair(i+1,s[i]);
		while(r-l>=2&&slope(dat[q[l]],I)<slope(dat[q[l+1]],I))l++;
		f[i]=(g[q[l]]+s[i]-s[q[l]])/(i-q[l]+1);
	}
	for(int i=1;i<=n;i++)f[i]=max(f[i],f[i-1]);
}
int main(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;i++)scanf("%d",&h[i]);
	sort(h+2,h+n+1),reverse(h+2,h+n+1);
	while(h[n]<=h[1])n--;
	reverse(h+2,h+n+1);
//	for(int i=1;i<=n;i++)printf("%d ",h[i]);puts("");
	for(int i=1;i<=n;i++)s[i]=s[i-1]+h[i];
	m=min(m,n-1);
	for(int i=1;i<=n;i++)f[i]=h[1];
	while(m--){
		for(int i=1;i<=n;i++)g[i]=f[i];
		solve();
	}
	printf("%lf\n",f[n]);
	return 0;
}

到这里，优化似乎已经到头了——单次DP已经压到底线 \(O(n)\) 了。因此要优化只能从合并次数 \(m\) 这一维下手了。

因为水量互不相等，所以肯定是越晚合并的区间长度越短，不然我们一定可以将一个原本在后面合并的元素移到前面并使得答案增加。

依据这个结论，有个性质是若 \(k\) 较大时，决策的区间长度会很快收敛到 \(1\)。而又有一个结论是长度大于 \(1\) 的区间仅有最多 \(\log nh\) 个，约 \(14\) 个。

于是我们只需DP \(14\) 层，剩下的部分全部选长度为 \(1\) 的区间就行了。

（证明？打表就行了！）

还有一个由“互不相同”带来的结论是，比较大小关系时精度只需要十几位就行了，这是显然的。于是我们DP时直接用普通 double 存，然后记录转移点，在DP结束后再用高精度小数按图索骥复原出完整的精度即可。

时间复杂度 \(O(n\log n+np)\)。

代码（省略模板部分）：

#include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> pdd;
int n,m,p,h[8010],l,r,las[17][8010];
double f[8010],g[8010],s[8010];
pdd dat[8010];
int q[8010];
double slope(pdd x,pdd y){return (x.second-y.second)/(x.first-y.first);}
void solve(int ID){
	l=r=0;
	for(int i=1;i<=n;i++){
		dat[i]=make_pair(i,s[i]-g[i]);
		while(r-l>=2&&slope(dat[q[r-2]],dat[q[r-1]])>slope(dat[q[r-1]],dat[i]))--r;
		q[r++]=i;
		pdd I=make_pair(i+1,s[i]);
		while(r-l>=2&&slope(dat[q[l]],I)<slope(dat[q[l+1]],I))l++;
		f[i]=(g[q[l]]+s[i]-s[q[l]])/(i-q[l]+1),las[ID][i]=q[l];
	}
	for(int i=1;i<=n;i++)if(f[i]<f[i-1])f[i]=f[i-1],las[ID][i]=-1;
}
Decimal calc(int i,int j){
	if(!i)return h[1];
	if(las[i][j]==-1)return calc(i,j-1);
	return (calc(i-1,las[i][j])+s[j]-s[las[i][j]])/(j-las[i][j]+1);
}
int main(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;i++)scanf("%d",&h[i]);
	sort(h+2,h+n+1),reverse(h+2,h+n+1);
	while(h[n]<=h[1])n--;
	reverse(h+2,h+n+1);
//	for(int i=1;i<=n;i++)printf("%d ",h[i]);puts("");
	for(int i=1;i<=n;i++)s[i]=s[i-1]+h[i];
	m=min(m,n-1);
	int lim=min(m,14);
	for(int i=1;i<=n;i++)f[i]=h[1];
	for(int j=1;j<=lim;j++){
		for(int i=1;i<=n;i++)g[i]=f[i];
		solve(j);
	}
	Decimal res=calc(lim,n-m+lim);
	for(int i=n-m+lim+1;i<=n;i++)res=(res+h[i])/2;
	cout<<res.to_string(p<<1)<<endl;
	return 0;
}

VI.[LOJ#2769][ROI 2017 Day 1]前往大都会

首先建出最短路 DAG，然后将每条路径切作多条 DAG 上的合法路径。

对于每条路径可以斜率优化。列出式子后发现可以用单调栈优化。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,id,nex[1001000],las[1001000],X[1001000],Y[1001000],Z[1001000];
vector<int>u[1001000],v[1001000];
int topo[1001000],cnt;
namespace DP{
ll f[1001000];
int q[1001000],L[1001000],R[1001000];
ll sqr(int x){return 1ll*x*x;}
double slope(int K,int J){
	return 1.0*(f[X[K]]+sqr(Z[las[K]])-f[X[J]]-sqr(Z[las[J]]))/(Z[las[K]]-Z[las[J]]);
}
void Slope_Boosting_DP(){
	memset(f,0x80,sizeof(f)),f[1]=0;
	for(int T=1;T<=n;T++){
		int x=topo[T];
		for(auto i:v[x]){
			if(nex[i]==-1&&las[i]==-1)continue;
			if(las[i])L[i]=L[las[i]],R[i]=R[las[i]],Z[i]+=Z[las[i]];
			while(R[i]-L[i]>=2&&slope(q[R[i]-2],q[R[i]-1])<=slope(q[R[i]-1],i))R[i]--;
			q[R[i]++]=i;
			while(R[i]-L[i]>=2&&slope(q[R[i]-2],q[R[i]-1])<=2.0*Z[i])R[i]--;
			if(L[i]!=R[i])f[x]=max(f[x],f[X[q[R[i]-1]]]+sqr(Z[i]-Z[las[q[R[i]-1]]]));
		}
//		printf("%d:%d\n",x,f[x]);
	}
}
}
namespace SP{
priority_queue<pair<int,int> >q;
int dis[1001000];
bool vis[1001000];
void Dijkstra(){
	memset(dis,0x3f,sizeof(dis)),q.emplace(dis[1]=0,1);
	while(!q.empty()){
		int x=q.top().second;q.pop();
		if(vis[x])continue;vis[x]=true;topo[++cnt]=x;
		for(auto i:u[x])if(dis[Y[i]]>dis[x]+Z[i])q.emplace(-(dis[Y[i]]=dis[x]+Z[i]),Y[i]);
	}
	for(int i=1;i<=id;i++)
		if(dis[Y[i]]!=dis[X[i]]+Z[i])las[nex[i]]=nex[las[i]]=0,nex[i]=las[i]=-1;
		else DP::L[i]=DP::R[i]=i;
//	for(int i=1;i<=n;i++)printf("%d ",dis[i]);puts("");
}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int j=1,x;j<=m;j++){
		scanf("%d",&x);
		scanf("%d",&X[id+1]);
		for(int i=1;i<=x;i++){
			scanf("%d%d",&Z[id+i],&Y[id+i]);
			u[X[id+i]].push_back(id+i),v[Y[id+i]].push_back(id+i);
			X[id+i+1]=Y[id+i];
			if(i<x)nex[id+i]=id+i+1,las[id+i+1]=id+i;
		}
		id+=x;
	}
	SP::Dijkstra();
	DP::Slope_Boosting_DP();
	printf("%d %lld\n",SP::dis[n],DP::f[n]);
	return 0;
}

VII.[ICPC2014 WF]Buffed Buffet

首先“离散食物”的问题是一个背包问题，有 \(f_{i,j}+t_0k-\dfrac{k(k-1)}2\Delta t\to f_{i+1,j+wk}\)。

显然我们不能直接就用它来暴力转移了。

注意到这个式子看上去一脸斜率优化的样子。我们按照 \(w\) 的余数分类。

设 \(k<j<i\)，三者模 \(w\) 同余，且 \(j\) 比 \(k\) 优。令 \(g=f_{i-1}\)，\(f=f_i\)。

\[g_k+\dfrac{t_0(i-k)}{w}-\dfrac{(i-k)(i-k-w)\Delta t}{2w^2}<g_j+\dfrac{t_0(i-j)}{w}-\dfrac{(i-j)(i-j-w)\Delta t}{2w^2} \\2w^2g_k+2wt_0(i-k)-(i-k)(i-k-w)\Delta t<2w^2g_j+2wt_0(i-j)-(i-j)(i-j-w)\Delta t \\2w^2(g_k-g_j)-2wt_0(k-j)-\Delta t(k^2-(2i-w)k)<\Delta t(j^2-(2i-w)j) \\2w^2(g_k-g_j)-2wt_0(k-j)-\Delta t(k^2-j^2)<\Delta t(j-k)(2i-w) \\\dfrac{2w^2(g_k-g_j)-2wt_0(k-j)-\Delta t(k^2+kw-j^2-jw)}{\Delta t(j-k)}<2i \]

完成。我们可以在 \(O(dw)\) 的时间完成这个部分。

然后考虑“连续食物”的问题。这是一个类闵可夫斯基和的问题，我们每次挑出当前最优的一段食物，加入它直到它不更优，然后合并它和它下一段食物即可。得到凸包后，只需枚举分多少给连续，分多少给离散即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld fni=-1e18;
const ld eps=1e-7;
int n,m,q[10100];
ld g[10100],f[10100],res;
void ins(){
	int w,t0,del;scanf("%d%d%d",&w,&t0,&del);
	if(!del){for(int i=w;i<=m;i++)f[i]=max(f[i],f[i-w]+t0);return;}
	auto slope=[=](int k,int j){return(2*w*w*(g[k]-g[j])-2.0*w*t0*(k-j)-1.0*del*(k*k+k*w-j*j-j*w))/del/(j-k);};
	for(int i=0;i<=m;i++)g[i]=f[i];
	for(int _=0;_<w;_++)for(int i=_,l=0,r=0;i<=m;i+=w){
		while(r-l>=2&&slope(q[r-2],q[r-1])>=slope(q[r-1],i))r--;
		q[r++]=i;
		while(r-l>=2&&slope(q[l],q[l+1])<=2*i)l++;
		int d=(i-q[l])/w;
		f[i]=g[q[l]]+1ll*d*t0-1ll*d*(d-1)/2*del;
	}
//	for(int i=0;i<=m;i++)printf("%Lf ",f[i]);puts("");
}
struct Line{
	ld k,b;
	Line(ld K,ld B){k=K,b=B;}
	friend bool operator<(const Line&u,const Line&v){return u.b>v.b;}
};
ld F;
vector<Line>v;
char s[10];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)f[i]=fni;f[0]=0;
	for(int i=1,x,y;i<=n;i++){
		scanf("%s",s);
		if(s[0]=='D')ins();
		else scanf("%d%d",&x,&y),v.emplace_back(y,x);
	}
	res=f[m];
	if(v.empty()){
		if(f[m]<=-1e15)puts("impossible");else printf("%Lf\n",f[m]);
		return 0;
	}
	sort(v.begin(),v.end());
	Line l=v[0];
	for(int i=1,j=1;i<=m;i++){
		double rem=1;
		while(j<v.size()&&l.b-l.k*rem+eps<v[j].b){
			double tt=(l.b-v[j].b)/l.k;
			F+=tt*l.b-0.5*l.k*tt*tt;
			rem-=tt;
			l.b-=l.k*tt;
			if(v[j].k<eps)l.k=0;else l.k=1/(1/l.k+1/v[j].k);
			j++;
		}
		F+=rem*l.b-0.5*l.k*rem*rem;
		l.b-=l.k*rem;
		res=max(res,F+f[m-i]);
	}
	printf("%Lf\n",res);
	return 0;
}

VIII.[LOJ#2390][JOISC 2017 Day 1]开荒者

首先第一个观察是风向的顺序并没有影响，我们只需关注每个方向具体刮风的天数即可。这个具体关于每个初始就有草籽的位置分析即可。

然后第二个观察是事实上左右方向和上下方向内部的刮风天数也是影响不大的：假如左右方向刮风天数确定了，则不管给左右分别分配多少天，整个图形都是全等的，真正有影响的就是落在范围内的部分了。这意味着，我们只需分别确定左右和上下的天数，然后判定就只需找到所有矩形的并中，是否存在一个 \(R\times C\) 的区域满足条件即可。

然后我们要回退一步，首先确定上下方向刮风的天数 \(u,d\)。此时每个初始草籽变成了纵向的一段线段。然后对于每一列分开分析，对左右方向刮风的天数的限制加以分析。

设某列中所有被某条线段覆盖的位置集合是 \(a_1,a_2,\dots,a_k\)。则限制是 \(l\geq a_1,r\geq C-a_n,l+r\geq a_{i+1}-a_i\)。对于所有限制合并考虑即可求出 \(l,r\)。

下一个观察是能够影响所有行上 \(\{a_1,a_2,\dots,a_k\}\) 这些集合构成的集合的 \(u,d\) 仅有那些满足：

• \(u\) 使得某个草籽首次延伸到第一行，且 \(d\) 使得某个草籽首次延伸到最后一行。
• \(u,d\) 使得某两个相邻草籽首次相遇，且一个草籽首次延伸到第一行或最后一行。

一共有 \(O(n^3)\) 种 \(u,d\)。对于每种 \(u,d\) 其 \(l,r\) 都可以通过上述流程在平方时间内求出。故现在有一个 \(O(n^5)\) 的暴力。

然后我们只管 \(u,d\) 的和然后就只有 \(O(n^2)\) 种 \(u+d\)，问题转化为求所有长度为 \(R\) 的窗口对应的 \(l+r\) 的最小值。单调队列即可。复杂度 \(O(n^4)\)。

下一步再想优化就只能从 \(u+d\) 的角度入手。记 \(s=u+d\) 并递增考虑之。

注意到所有关键行的关键位置集合的变化仅会变化 \(O(n^2)\) 次，每次变化都仅涉及到 \(O(1)\) 个关键行。那么每次暴力重构涉及到的关键行上信息，然后得知信息即可 \(O(n)\) 做单调队列，复杂度 \(O(n^3)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x7f7f7f7f;
int n,m,K,X[310],Y[310];
int V[310];
set<int>s;
int a[610],b[610],tp[610],p[610];
int vis[310];
int L[610],R[610],D[610];
void rebuild(int id){
	for(int i=1;i<=K;i++)vis[i]=0;
	for(int i=1;i<=id;i++)vis[b[p[i]]]+=tp[p[i]];
	int l=1,r;
	while(l<=K&&!vis[l])l++;
	if(l>K){L[id]=R[id]=D[id]=inf;return;}
	L[id]=V[l]-1,D[id]=0;
	for(;;l=r){
		for(r=l+1;r<=K&&!vis[r];r++);
		// printf("%d<%d,%d>\n",id,l,r);
		if(r>K){R[id]=m-V[l];break;}
		D[id]=max(D[id],V[r]-V[l]-1);
	}
}
void movefront(int x){swap(p[x],p[x-1]),rebuild(x-1);}
int func(int*o,int*mo){
	static int q[610],l,r;
	l=r=0;for(int i=1,j=1;i<=(K<<1);i++){
		auto push=[&](){while(l<r&&o[q[r-1]]<=o[j])r--;q[r++]=j;};
		for(;j<(K<<1)&&a[p[j]]-a[p[i]]<n;j++)if(a[p[j+1]]!=a[p[j]])push();
		if(a[p[j]]-a[p[i]]<n)return i;
		mo[i]=o[q[l]];
		if(l<r&&q[l]==i)l++;
	}
	return (K<<1);
}
int calc(){
	static int ml[610],mr[610],md[610];
	func(L,ml);
	func(R,mr);
	int P=func(D,md);
	int ret=inf;
	for(int i=1;i<P;i++)ret=min(ret,max(ml[i]+mr[i],md[i]));
	return ret;
}
int res=0x7f7f7f7f;
int main(){
	scanf("%d%d%d",&n,&m,&K);
	vector<int>v;
	for(int i=1;i<=K;i++)scanf("%d%d",&X[i],&Y[i]),V[i]=Y[i],v.push_back(X[i]);
	sort(v.begin(),v.end());
	int mvl=(v[0]-1)+(n-v.back());
	for(int i=1;i<v.size();i++)mvl=max(mvl,v[i]-v[i-1]-1);
	for(auto x:v)for(auto y:v)if((x-1)+(n-y)>=mvl)s.emplace((x-1)+(n-y));
	for(int i=0;i<v.size();i++)for(int j=i;j<v.size();j++)if(v[j]-v[i]-1>=mvl)s.emplace(v[j]-v[i]-1);
	sort(V+1,V+K+1);
	for(int i=1;i<=K;i++)Y[i]=lower_bound(V+1,V+K+1,Y[i])-V;
	for(int i=1;i<=K;i++)a[i]=X[i],a[i+K]=X[i]+1,b[i]=b[i+K]=Y[i],tp[i]=1,tp[i+K]=-1,p[i]=i,p[K+i]=K+i;
	sort(p+1,p+(K<<1)+1,[](int x,int y){return a[x]<a[y];});
	for(int i=1;i<=(K<<1);i++)rebuild(i);
	int las=0;for(auto i:s){
		for(int j=1;j<=K;j++)a[j]-=i-las;
		while(true){
			bool rv=false;
			for(int j=1;j<(K<<1);j++)if(a[p[j]]>a[p[j+1]])rv=true,movefront(j+1);
			if(!rv)break;
		}
		// printf("%d:\n",i);
		// for(int j=1;j<=(K<<1);j++)printf("%d ",a[p[j]]);puts("");
		// for(int j=1;j<=(K<<1);j++)printf("%d ",p[j]);puts("");
		// for(int j=1;j<=(K<<1);j++)printf("%d ",q[j]);puts("");
		// for(int j=1;j<=(K<<1);j++)printf("[%d,%d,%d]",L[j],R[j],D[j]);puts("");
		las=i;
		int qwq=calc();
		if(qwq!=inf)res=min(0ll+res,0ll+i+qwq);
	}
	printf("%d\n",res);
	return 0;
}

II.单调栈上二分对数复杂度斜率优化

通过单调栈上二分，我们可以在对数复杂度内实现一些 DP。

I.[SDOI2012]任务安排

同上一题一样，不过，这题的\(t_i\)可能有负数，这就意味着前缀和不再是单调增的！

我们不能再像前一题一样用单调队列维护了——但是因为队尾的单调性仍然存在，我们仍然可以维护上凸包。这就启发我们使用单调栈来维护斜率，并且在单调栈中二分。

我们不妨想一想，如果这个\(c\)也有可能是负数怎么办？

\(c\)是负数就意味着不再具有一个明确的凸壳——我们在两边同除时不知道\(c[j]-c[k]\)是正是负。因此，我们可以采用平衡树来支持插入斜率和查询，复杂度\(O(n\log n)\)。（该方法纯属口胡，请勿当真）

本题代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,t[300100],c[300100],f[300100],s[300100],tp;
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&t[i],&c[i]),t[i]+=t[i-1],c[i]+=c[i-1];
	for(int i=1;i<=n;i++){
		int L=0,R=tp;
		while(L<R){
			int mid=(L+R)>>1;
			if((f[s[mid]]-f[s[mid+1]])>=(c[s[mid]]-c[s[mid+1]])*(m+t[i]))L=mid+1;
			else R=mid;
		}
		f[i]=f[s[L]]+m*(c[n]-c[s[L]])+t[i]*(c[i]-c[s[L]]);
		while(tp&&(f[s[tp-1]]-f[s[tp]])*(c[s[tp]]-c[i])>=(f[s[tp]]-f[i])*(c[s[tp-1]]-c[s[tp]]))tp--;
		s[++tp]=i;
	}
	printf("%lld\n",f[n]);
	return 0;
}

II.[SDOI2013]保护出题人

这题好像不算DP……但是涉及到斜率和凸包的题都是好题

因为这题要求是确保没有任何一个姜丝能活着走到门口，

所以设血量的前缀和为\(s\)，每两只姜丝间距离为\(m\)，

则对于 \(\forall i\) ，

都应有\(ans_i=\max\limits_{j=0}^{i-1}\{\dfrac{s_i-s_j}{x_i+(i-j-1)*m}\}\)

其中，分母是第 \(j+1\) 只姜丝距离门的距离，分子是第\(i\)到第\(j+1\)姜丝的总血量。

这样便能拿到\(50\%\)！！

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s[100100];
double res,ans;
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1,x;i<=n;i++){
		scanf("%lld%lld",&s[i],&x),s[i]+=s[i-1],res=0;
		for(int j=0;j<i;j++)res=max(res,1.0*(s[i]-s[j])/(x+(i-j-1)*m));
		ans+=res;
	}
	printf("%.0lf\n",ans);
	return 0;
}

我们将这个东西变成斜率的形式：

\(ans_i=\max\limits_{j=0}^{i-1}\{\dfrac{\{s_i\}-\{s_j\}}{\{x_i+im\}-\{m(j+1)\}}\}\)

可以将其看作是\(\Big(s_i,x_i+im\Big)\)与\(\Big(s_j,m(j+1)\Big)\)的斜率。

即

\(ans_i=\max\limits_{j=0}^{i-1}\{\operatorname{slope}\{\Big(s_i,x_i+im\Big),\Big(s_j,m(j+1)\Big)\}\}\)

前者我们没法管它；但是后者，我们是可以维护下凸壳的（因为对于不同的\(i\)，后面的东西是相同的）。用单调栈维护并二分查找出斜率的最大值（实际上对于这种单峰函数应该写三分来着的……但是如果三分分的那两个点都在一起那不就是二分吗），并统计答案即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define mp make_pair 
int n,m,s[100100],tp;
double res,ans;
double slope(pii u,pii v){//ask for the slope from u to v
	return 1.0*(v.y-u.y)/(v.x-u.x);
}
pii stk[100100];
signed main(){
	scanf("%lld%lld",&n,&m),stk[0]=mp(m,0);
	for(int i=1,x;i<=n;i++){
		scanf("%lld%lld",&s[i],&x),s[i]+=s[i-1];
		int l=0,r=tp,qwq=0;
		pii tmp=mp(x+i*m,s[i]);
		while(l<=r){
			int mid=(l+r)>>1;
			if(slope(stk[mid],tmp)<slope(stk[mid-1],tmp))r=mid-1;
			else qwq=mid,l=mid+1;
		}
		res=slope(stk[qwq],tmp);
		tmp=mp((i+1)*m,s[i]);
		while(tp&&slope(stk[tp-1],tmp)>=slope(stk[tp],tmp))tp--;
		stk[++tp]=tmp;
		ans+=res;
	}
	printf("%.0lf\n",ans);
	return 0;
}

III.高速公路

简直恶心到爆炸……

首先，暴力的DP是非常简单的。设\(dis_x\)表示位置\(x\)到根的距离，则有

\[f_x=\min\limits_{y\text{ is an ancestor of }x}f_y+p_x(dis_x-dis_y)+q_x \]

暴力一敲，期望得分\(40\%\)。由于数据可能水了，实际得分\(60\%\)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,head[1001000],cnt,a[1001000],b[1001000],dis[1001000];
ll f[1001000];
struct node{
	int to,next,val;
}edge[1001000];
void ae(int u,int v,int w){
	edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
}
vector<int>v;
void dfs(int x){
	for(auto y:v)f[x]=min(f[x],1ll*a[x]*(dis[x]-dis[y])+b[x]+f[y]);
	v.push_back(x);
	for(int i=head[x];i!=-1;i=edge[i].next)dis[edge[i].to]=dis[x]+edge[i].val,dfs(edge[i].to);
	v.pop_back();
}
int main(){
	scanf("%d",&n),memset(head,-1,sizeof(head)),memset(f,0x3f3f3f3f,sizeof(f)),f[1]=0;
	for(int i=2,x,y;i<=n;i++)scanf("%d%d%d%d",&x,&y,&a[i],&b[i]),ae(x,i,y);
	dfs(1);
	for(int i=2;i<=n;i++)printf("%lld\n",f[i]);
	return 0;
}

考虑斜率优化一下。

我们先把问题抽象到序列上。设有一个\(j<k<i\)，则如果\(j\)比\(k\)优，必有

\[f_j+p_i(dis_i-dis_j)+q_i\leq f_k+p_i(dis_i-dis_k)+q_i \]

\[f_j+p_idis_i-p_idis_j\leq f_k+p_idis_i-p_idis_k \]

\[f_j-f_k\leq p_idis_j-p_idis_k \]

\[f_j-f_k\leq p_i(dis_j-dis_k) \]

\[\dfrac{f_j-f_k}{dis_j-dis_k}\geq p_i \]

然后直接优化即可，因为\(p_i\)保证递增。

但是，因为是在树上，所以你从一颗子树中跑出来之后，还要复原原序列！

当然，复原是很简单的，因为斜率优化的过程中除了队首队尾的移动以外，唯一真正改动的位置就是最后的入队环节。这时候只需要记录这个位置原本放了什么即可。

但是，暴力地维护队列的话，就不能完美地应用“单调队列”的性质了，因此复杂度最劣仍然是\(O(n^2)\)。期望得分\(60\%\)（听说常卡的好也能A？）

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,head[1001000],cnt,a[1001000],b[1001000],q[1001000],l[1001000],r[1001000],cha[100100];
ll f[1001000],dis[1001000];
void read(int &x){
	x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
}
struct node{
	int to,next,val;
}edge[1001000];
void ae(int u,int v,int w){
	edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
}
void dfs(int x){
	while(l[x]<r[x]&&(f[q[l[x]]]-f[q[l[x]+1]])>=(dis[q[l[x]]]-dis[q[l[x]+1]])*a[x])l[x]++;
	f[x]=(dis[x]-dis[q[l[x]]])*a[x]+b[x]+f[q[l[x]]];
	while(l[x]<r[x]&&(f[q[r[x]-1]]-f[q[r[x]]])*(dis[q[r[x]]]-dis[x])>=(f[q[r[x]]]-f[x])*(dis[q[r[x]-1]]-dis[q[r[x]]]))r[x]--;
	cha[x]=q[++r[x]],q[r[x]]=x;
	printf("%d:%d,%d:",x,l[x],r[x]);for(int i=l[x];i<=r[x];i++)printf("%d ",q[i]);puts("");
	for(int i=head[x];i!=-1;i=edge[i].next)dis[edge[i].to]=dis[x]+edge[i].val,l[edge[i].to]=l[x],r[edge[i].to]=r[x],dfs(edge[i].to);
	q[r[x]]=cha[x];
}
int main(){
	read(n),memset(head,-1,sizeof(head));
	for(int i=2,x,y;i<=n;i++)read(x),read(y),read(a[i]),read(b[i]),ae(x,i,y);
	l[1]=1,dfs(1);
	for(int i=2;i<=n;i++)printf("%lld\n",f[i]);
	return 0;
}

发现我们每个位置都那么费劲地移动左右端点太蠢了。不如直接套上一个二分。复杂度是妥妥的\(O(n\log n)\)。

（这二分真的非常难写，各种边界太恶心了）

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,head[1001000],cnt,a[1001000],b[1001000],q[1001000],l[1001000],r[1001000],cha[1001000];
ll f[1001000],dis[1001000];
void read(int &x){
	x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
}
struct node{
	int to,next,val;
}edge[1001000];
void ae(int u,int v,int w){
	edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
}
void dfs(int x){
	int L,R,res;
	L=l[x],R=r[x]-1,res=r[x];
	while(L<=R){
		int mid=(L+R)>>1;
		if((f[q[mid]]-f[q[mid+1]])>=(dis[q[mid]]-dis[q[mid+1]])*a[x])L=mid+1;
		else R=mid-1,res=mid;
	} 
	l[x]=res;
	f[x]=(dis[x]-dis[q[l[x]]])*a[x]+b[x]+f[q[l[x]]];
	L=l[x]+1,R=r[x],res=l[x];
	while(L<=R){
		int mid=(L+R)>>1;
		if((f[q[mid-1]]-f[q[mid]])*(dis[q[mid]]-dis[x])>=(f[q[mid]]-f[x])*(dis[q[mid-1]]-dis[q[mid]]))R=mid-1;
		else res=mid,L=mid+1;
	}	
	r[x]=res;
	cha[x]=q[++r[x]],q[r[x]]=x;
	for(int i=head[x];i!=-1;i=edge[i].next)dis[edge[i].to]=dis[x]+edge[i].val,l[edge[i].to]=l[x],r[edge[i].to]=r[x],dfs(edge[i].to);
	q[r[x]]=cha[x];
}
int main(){
	read(n),memset(head,-1,sizeof(head));
	for(int i=2,x,y;i<=n;i++)read(x),read(y),read(a[i]),read(b[i]),ae(x,i,y);
	l[1]=1,dfs(1);
	for(int i=2;i<=n;i++)printf("%lld\n",f[i]);
	return 0;
}

IV.[BZOJ#1767][CEOI2009]harbingers

设 \(d_i\) 表示位置 \(i\) 的深度，\(p_i\) 表示准备时间，\(v_i\) 表示速度，\(f_i\) 表示答案，则有 DP 式

\[f_i=\min\limits_{j\text{ is an ancestor of }i}\Big\{f_j+v_i(d_i-d_j)+p_i\Big\} \]

把式子拆开来倒腾倒腾就能发现其可以斜率优化，式子是 \(j\) 比 \(k\) 劣当且仅当

\[\dfrac{f_j-f_k}{d_j-d_k}<v_i \]

因为 \(v_i\) 没有显著性质所以维护单调栈然后二分求解。

又因为是树，所以单调栈出栈时也要用二分。

时间复杂度 \(O(n\log n)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,d[100100],p[100100],v[100100],head[100100],cnt;
struct node{int to,next,val;}edge[200100];
void ae(int u,int v,int w){
	edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
	edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
int stk[100100],tp;
ll f[100100];
void dfs(int x,int fa){
	int l=1,r=tp;
	while(l<r){
		int mid=(l+r)>>1;
		int j=stk[mid],k=stk[mid+1];
		if(1.0*(f[j]-f[k])*(d[k]-d[x])>=1.0*(f[k]-f[x])*(d[j]-d[k]))r=mid;
		else l=mid+1;
	}
	int tval=stk[r+1],ttp=tp;stk[tp=r+1]=x;
	for(int i=head[x],y;i!=-1;i=edge[i].next)if((y=edge[i].to)!=fa){
		d[y]=d[x]+edge[i].val;
		l=1,r=tp;
		while(l<r){
			int mid=(l+r)>>1;
			int j=stk[mid],k=stk[mid+1];
			if(f[j]-f[k]>=1ll*v[y]*(d[j]-d[k]))l=mid+1;
			else r=mid;
		}
		f[y]=f[stk[l]]+1ll*v[y]*(d[y]-d[stk[l]])+p[y];
		dfs(y,x);
	}
	stk[tp]=tval,tp=ttp;
}
int main(){
	scanf("%d",&n),memset(head,-1,sizeof(head));
	for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
	for(int i=2;i<=n;i++)scanf("%d%d",&p[i],&v[i]);
	dfs(1,0);
	for(int i=2;i<=n;i++)printf("%lld ",f[i]);
	return 0;
}

III.复杂斜率优化

使用其它东西来优化斜率优化。

I.CF1175G Yet Another Partiton Problem

首先条件反射把 \(K\) 套到外层。于是转移就变成数组 \(g\to f\)。

考虑从左往右转移。转移时，有若干段 \(\max\) 相等的区间，每段区间都可以用单调栈求出。考虑每段区间内部所有东西，都是 \(g_j+K\times(i-j)\) 的形式；区间内部仅涉及到 \(j\) 一维，故要求出 \(g_j-jK\) 的最大值，可以维护凸包。

在求出 \(g_j-jK\) 的最大值后，问题就变成了各个区间间的问题，其中每个区间的贡献都是 \(V_t+K_ti\) 的形式。把它扔到李超树中维护即可。

但是单调栈是会变动的。变动的时候涉及到合并若干凸包，以及李超树的回撤。凸包的合并可以启发式合并，李超树回撤可以用可持久化。这样，单次复杂度 \(O(n\log n)\)，总复杂度 \(kn\log n\)。

需要注意的是，本题因为 不满足四边形不等式（考虑对 \(10^9,1,1,1,10^9\) 这段东西分析）进而不存在决策单调性。因此无论是 wqs 二分还是分治优化都用不了。笛卡尔树分治+线段树维护差分等 trick 都无法使用。

另外，因为凸包合并的时候，前一个凸包的坐标全部小于后一个凸包的坐标，所以合并直接全都插入头或尾即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,K,f[20100],g[20100],a[20100],stk[20100],rt[20100],cnt,tp;
struct Line{
	int k,b;
	Line(){}
	Line(int K,int B){k=K,b=B;}
	int operator()(const int x)const{return k*x+b;}
};
#define lson seg[x].ch[0]
#define rson seg[x].ch[1]
#define mid ((l+r)>>1)
struct SegTree{int ch[2];Line l;}seg[1001000];
void insert(int&x,int y,int l,int r,Line V){
//	printf("INSERT:%d,%d[%d,%d](%dx+%d)\n",x,y,l,r,V.k,V.b);
	if(l>r)return;
	x=++cnt;if(!y){seg[x].l=V;return;}
	seg[x]=seg[y];
	if(seg[x].l(mid)>V(mid))swap(seg[x].l,V);
	if(seg[x].l(l)>V(l))insert(seg[x].ch[0],seg[y].ch[0],l,mid-1,V);
	if(seg[x].l(r)>V(r))insert(seg[x].ch[1],seg[y].ch[1],mid+1,r,V);
}
int query(int x,int l,int r,int P){
//	printf("QUERY:%d[%d,%d](%d,%d):%d\n",x,l,r,seg[x].l.k,seg[x].l.b,P);
	if(l>r||!x)return 0x3f3f3f3f;
	int ret=seg[x].l(P);
	if(P>mid)ret=min(ret,query(rson,mid+1,r,P));
	if(P<mid)ret=min(ret,query(lson,l,mid-1,P));
	return ret;
}
#undef lson
#undef rson
#undef mid 
struct Hull:deque<int>{
int query(int K)const{
	int l=0,r=size()-1;
	while(l<r){
		int mid=(l+r)>>1;
		int u=*(begin()+mid),v=*(begin()+mid+1);
		if(g[u]-K*u<=g[v]-K*v)r=mid;else l=mid+1;
	}
	int x=*(begin()+l);
	return g[x]-K*x;
}
void PUSH_BACK(int i){
	while(size()>=2){
		int k=*(rbegin()+1),j=*rbegin();
		if(1ll*(g[i]-g[k])*(j-k)>1ll*(g[j]-g[k])*(i-k))break;
		pop_back();
	}
	push_back(i);
}
void PUSH_FRONT(int k){
	while(size()>=2){
		int i=*(begin()+1),j=*begin();
		if(1ll*(g[i]-g[k])*(j-k)>1ll*(g[j]-g[k])*(i-k))break;
		pop_front();
	}
	push_front(k);
}
void merge(Hull&h){
	if(size()>=h.size()){for(auto i:h)PUSH_BACK(i);h.clear();}
	else{for(auto it=rbegin();it!=rend();it++)h.PUSH_FRONT(*it);clear(),swap(h);}
}
}h[20100];
void DP(){
	for(int i=1;i<=n;i++){
		while(tp>=2&&a[stk[tp-1]]<=a[i])h[tp-1].merge(h[tp]),tp--;
		if(!tp||a[stk[tp]]>a[i])tp++;
		h[tp].PUSH_BACK(i-1),stk[tp]=i;
//		for(int j=1;j<=tp;j++){printf("[");for(auto x:h[j])printf("%d ",x);printf("]");}puts("");
		insert(rt[tp],rt[tp-1],1,n,Line(a[i],h[tp].query(a[i])));
		f[i]=query(rt[tp],1,n,i);
	}//puts("");
//	for(int i=1;i<=n;i++)printf("%d ",f[i]);puts("");
	while(tp)h[tp].clear(),stk[tp]=rt[tp]=0,tp--;
	for(int i=1;i<=cnt;i++)seg[i].ch[0]=seg[i].ch[1]=0;cnt=0;
}
int main(){
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	memset(f,0x3f,sizeof(f)),f[0]=0;
	while(K--)swap(f,g),DP();
	printf("%d\n",f[n]);
	return 0;
}

II.CF1067D Computer Game

首先一个显然的想法是，我们必然是不断玩一个游戏直到其成功，然后升级 升级后期望收益最大的 游戏，随后一直玩它。

但是随着 \(T\) 的不同，我们可能会采取不同的策略：比如有一个游戏成功概率中等，未升级时收益中等；另一个游戏成功概率高，未升级时收益小（远小于前者），升级后收益大；则在 \(T\) 小时我们更喜欢第一个游戏（收益更大），\(T\) 大时我们更喜欢第二个游戏（成功概率大，能省出更多时间给收益大的游戏）。

进而我们考虑令 \(f_i\) 表示 \(i\) 秒时的期望收益，则 \(f_i=\max\limits_j\Big\{(1-p_j)f_{i-1}+p_j\big(a_j+M(i-1)\big)\Big\}\)，其中 \(M=\max b_jp_j\)。

把这个式子拿出来整理整理罢。令 \(S_i=Mi-f_i,A_j=p_ja_j\)，则 \(f_i=f_{i-1}+\max\limits_j\{S_{i-1}p_j+A_j\}\)。

\(S_i\) 是 单调不降 的。

感性理解可以发现随着 \(i\) 增大 \(1\)，\(Mi\) 一项必然会增大 \(M\)，但是 \(f_i\) 一项不可能增加超过 \(M\)，进而 \(S_i\) 总是不断上升的（虽然会上升地越来越慢）。

考虑推一个式子。令 \(p_j<p_k\)，考虑 \(j,k\) 对 \(i\) 贡献，且 \(j\) 更优：

\[S_{i-1}p_j+A_j\geq S_{i-1}p_k+ A_k\\\dfrac{A_j-A_k}{p_k-p_j}\geq S_{i-1} \]

因为 \(S\) 递增所以 \(j\) 的贡献区间在 \(k\) 前。换句话说就是 \(i\) 越大，\(p\) 大但 \(A\) 小的元素就越容易被选上，同我们一开始的例子相符。

考虑对 \((p_j,A_j)\) 求一个凸包。把凸包上点按照 \(p\) 递增排序，则凸包中的点会按照这个顺序依次被拿来转移。

二分+快速幂求出每个点被转移的区间即可。具体而言，一个点被用来转移时，需要维护的是三元组 \(\begin{bmatrix}f_i&i&1\end{bmatrix}\)，然后构造一个可以从 \(\begin{bmatrix}f_i&i&1\end{bmatrix}\to\begin{bmatrix}f_{i+1}&i+1&1\end{bmatrix}\) 的矩阵即可。复杂度对数平方。

通过预处理矩阵的幂次然后倍增可以优化到对数；但是没有意义。

需要注意的是，本题的 eps 不能开太大，我开 1e-12 挂了，1e-14 就过了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps=1e-14;
int cmp(ld x){if(x>eps)return 1;if(x<-eps)return -1;return 0;}
ld M;
ll T;
int n,m;
struct Matrix{
ld a[3][3];
Matrix(){for(int i=0;i<3;i++)for(int j=0;j<3;j++)a[i][j]=0;}
ld*operator[](const int&x){return a[x];}
friend Matrix operator*(Matrix&u,Matrix&v){
	Matrix w;
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)w[i][j]+=u[i][k]*v[k][j];
	return w;
}
};
struct Point{
	ld p,A;
	friend bool operator<(const Point&u,const Point&v){return cmp(u.p-v.p)==0?u.A>v.A:u.p<v.p;}
	ld DP(ll i,ld f,ll j){
		Matrix x,z;
		x[0][0]=1-p;
		x[1][0]=p*M,x[1][1]=1;
		x[2][0]=A,x[2][1]=1,x[2][2]=1;
		z[0][0]=z[1][1]=z[2][2]=1;
		for(j-=i;j;j>>=1,x=x*x)if(j&1)z=z*x;
		return z[0][0]*f+z[1][0]*i+z[2][0];
	}
}p[100100],c[100100];
ll tim;ld f;
int main(){
	scanf("%d%lld",&n,&T);
	for(int i=1,a,b;i<=n;i++){
		scanf("%d%d%Lf",&a,&b,&p[i].p);
		p[i].A=a*p[i].p,M=max(M,b*p[i].p);
	}
	sort(p+1,p+n+1);
	c[m=1]=p[1];
	for(int i=2;i<=n;i++){
		if(cmp(p[i].p-p[i-1].p)==0)continue;
//		printf("%Lf\n",(p[i].p-c[m-1].p)*(c[m].A-c[m-1].A)-(c[m].p-c[m-1].p)*(p[i].A-c[m-1].A));
		while(m>=2&&cmp((p[i].p-c[m-1].p)*(c[m].A-c[m-1].A)-(c[m].p-c[m-1].p)*(p[i].A-c[m-1].A))!=1)
			m--;
		c[++m]=p[i];
	}
//	for(int i=1;i<=m;i++)printf("[%Lf,%Lf]",c[i].p,c[i].A);
	for(int i=1;i<m;i++){
		ll l=tim,r=T;
		while(l<r){
			ll mid=(l+r+1)>>1;
			ld S=M*(mid-1)-c[i].DP(tim,f,mid-1);
			if(cmp((S*c[i].p+c[i].A)-(S*c[i+1].p+c[i+1].A))==1)l=mid;else r=mid-1;
		}
//		printf("QWQ:%lld\n",l);
		f=c[i].DP(tim,f,l),tim=l;
	}
	printf("%Lf\n",c[m].DP(tim,f,T));
	return 0;
}

IV.CF1787H Codeforces Scoreboard

所有的题目分为两类：吃低保的，和不吃的。

吃低保的东西显然放到最后吃是最好的，不吃的就直接按照 \(b_i-k_it\) 算即可。

用 exchange argument 简单分析一下，发现不吃低保的必然是 \(k\) 越大越靠前选。

于是我们将所有题目按照 \(k\) 递减排序，然后依次考虑每道题：

• 其要么是不吃低保，按照 \(b_i-k_it\) 算，这样算会让 \(t\) 增加 \(1\)；要么吃低保，按照 \(a_i\) 算，且不会让 \(t\) 增加 \(1\)。

考虑 DP：令 \(f_{i,j}\) 表示长度为 \(i\) 的前缀中有 \(j\) 个不吃低保，此时的答案。转移是 \(f_{i,j}=\max(f_{i-1,j}+a_i,f_{i-1,j-1}+b_i-k_ij)\)。

我声称，\(f_i\) 是凸的。

证明？没有证明。

那么就简单了。直接平衡树大力维护即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(17680321);
#define lson t[x].ch[0]
#define rson t[x].ch[1]
struct Treap{
	int ch[2],sz;
	unsigned int rd;
	ll tag,sum,val;
}t[200100];
void pushup(int x){
	t[x].sz=t[lson].sz+t[rson].sz+1;
	t[x].sum=t[lson].sum+t[x].val+t[rson].sum;
}
void ADD(int x,ll y){
	if(x)t[x].tag+=y,t[x].val+=y,t[x].sum+=t[x].sz*y;
}
void pushdown(int x){ADD(lson,t[x].tag),ADD(rson,t[x].tag),t[x].tag=0;}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(t[x].rd>t[y].rd)return pushdown(x),t[x].ch[1]=merge(t[x].ch[1],y),pushup(x),x;
	else return pushdown(y),t[y].ch[0]=merge(x,t[y].ch[0]),pushup(y),y;
}
void splitbysz(int x,int k,int&u,int&v){
	if(!x)return u=v=0,void();
	pushdown(x);
	if(t[lson].sz>=k)v=x,splitbysz(lson,k,u,lson);
	else u=x,splitbysz(rson,k-t[lson].sz-1,rson,v);
	pushup(x);
}
void splitbytrans(int x,int k,ll b,int&u,int&v){
	if(!x)return u=v=0,void();
	pushdown(x);
	if(b-1ll*k*(t[lson].sz+1)>=t[x].val)
		v=x,splitbytrans(lson,k,b,u,lson);
	else u=x,splitbytrans(rson,k,b-1ll*k*(t[lson].sz+1),rson,v);
	pushup(x);
}
ll f0;int rt,cnt,n;
ll f[200100];
void trans(int k,int b,int a){
	int u,v,w;
	splitbytrans(rt,k,b-a,u,w);
	v=++cnt;
	t[v].rd=rnd(),t[v].ch[0]=t[v].ch[1]=t[v].tag=0;
	t[v].sum=t[v].val=b-a-1ll*(t[u].sz+1)*k,t[v].sz=1;
	if(w){
		int o;splitbysz(w,1,o,w);
		t[o].val=t[o].val+b-a-1ll*(t[u].sz+2)*k-t[v].val;
		t[o].sum=t[o].val;
		ADD(w,-k);
		w=merge(o,w);
	}
	rt=merge(merge(u,v),w);
	f0+=a;
	// f[t[rt].sz]=f[t[rt].sz-1]+b-1ll*t[rt].sz*k;
	// for(int i=t[rt].sz-1;i;i--)f[i]=max(f[i-1]+b-1ll*i*k,f[i]+a);
	// f[0]+=a;
	// for(int i=1;i<=t[rt].sz;i++)printf("%lld ",f[i]-f[i-1]);puts("");
}
ll query(int x){
	if(!x)return 0;
	pushdown(x);
	if(t[x].val>=0)return t[lson].sum+t[x].val+query(rson);
	return query(lson);
}
void iterate(int x){
	if(x)pushdown(x),iterate(lson),printf("%d ",t[x].val),iterate(rson);
}
struct dat{
	int k,a,b;
	friend bool operator<(const dat&u,const dat&v){
		return u.k>v.k;
	}
}p[200100];
void mina(){
	scanf("%d",&n),rt=cnt=0,f0=0;
	for(int i=1;i<=n;i++)scanf("%d%d%d",&p[i].k,&p[i].b,&p[i].a);
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++)trans(p[i].k,p[i].b,p[i].a)/*,printf("%lld:",f0),iterate(rt),puts("")*/;
	printf("%lld\n",query(rt)+f0);
}
int T;
int main(){
	scanf("%d",&T);
	while(T--)mina();
	return 0;
}

III.分治优化

分治优化配合类莫队式转移，即可实现分层的决策单调性的应用。

I.CF868F Yet Another Minimization Problem

明显，可以设\(f[i][j]\)表示前\(i\)个位置分成\(j\)段的最大收益。显然，暴力是\(O(n^2k)\)的。

如果我们按照\(j\)一遍一遍地跑的话，是可以考虑在\(i\)上面进行优化的、

考虑设\(f[i]\)表示\(f[i][j-1]\)，\(g[i]\)表示\(f[i][j]\)，

然后设\(w[l,r]\)表示区间\([l,r]\)的费用，

则我们是否可以证明它具有决策单调性？

即：

对于\(\forall i_1<i_2\)，设它们分别从\(j_1\)，\(j_2\)转移来最优，则必有\(j_1\leq j_2\)。

则必有

\(g_{j_1}+w[j_1+1,i_1]\leq g_{j_2}+w[j_2+1,i_1],g_{j_2}+w[j_2+1,i_2]\leq g_{j_1}+w[j_1+1,i_2]\)

我们可以考虑反证法。假设有\(j_1>j_2\)，

则对于上面的两个不等式里，如果两个都取到了\(=\)，则交换\(j_1,j_2\)没有影响。

否则，我们不妨设在第一个式子里取到了\(<\)，

即

\(g_{j_1}+w[j_1+1,i_1]<g_{j_2}+w[j_2+1,i_1],g_{j_2}+w[j_2+1,i_2]\leq g_{j_1}+w[j_1+1,i_2]\)

移项得

\(w[j_1+1,i_1]-w[j_2+1,i_1]<g_{j_2}-g_{j_1},g_{j_2}-g_{j_1}\leq w[j_1+1,i_2]-w[j_2+1,i_2]\)

两边合并\(g_2-g_1\)，得

\(w[j_1+1,i_1]-w[j_2+1,i_1]<w[j_1+1,i_2]-w[j_2+1,i_2]\)

这两项全部只有后面的\(i_1\)和\(i_2\)不同。但\(i_1<i_2\)，因此这是不可能成立的，往区间后面加数后答案必不会减少。

然后就可以分治了。每一轮我们存储对于当前区间\([l,r]\)可行的决策点\([L,R]\)，对于\([l,r]\)的中点\(mid\)，我们找到最优转移位置\(mp\)，然后继续分治\(([l,mid-1],[L,mp])\)与\(([mid+1,r],[mp,R])\)。

关于如何计算\(w[l,r]\)吗……类似的莫队一下，因为单次分治中左右端点总移动距离是\(n\log n\)的（每一层里面左右端点总次数是\(O(n)\)的，然后一共\(\log n\)层）。

总复杂度\(O(nk\log n)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,num[101000],cnt[101000],res,f[100100],g[100100];
int u,v;
void Push(int x){
	res+=cnt[num[x]],cnt[num[x]]++;
}
void Pop(int x){
	cnt[num[x]]--,res-=cnt[num[x]];
}
int Calc(int l,int r){
	while(u>l)Push(--u);
	while(v<r)Push(++v);
	while(u<l)Pop(u++);
	while(v>r)Pop(v--);
	return res;
}
void solve(int l,int r,int L,int R){
	if(l>r||L>R)return;
	int mp=-1,mn=0x3f3f3f3f3f3f3f3f,mid=(l+r)>>1;
	for(int i=L;i<=R;i++){
		int tmp=Calc(i+1,mid);
		if(f[i]+tmp<mn)mp=i,mn=f[i]+tmp;
	}
	g[mid]=mn;
	solve(l,mid-1,L,mp),solve(mid+1,r,mp,R);
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&num[i]);
	u=v=1,cnt[num[1]]++;
	for(int i=1;i<=n;i++)f[i]=Calc(1,i);
	while(--m)solve(1,n,0,n-1),memcpy(f,g,sizeof(g));
	printf("%lld\n",f[n]);
	return 0;
}

II.[CmdOI2019]任务分配问题

首先，题意就是把所有数划分成\(k\)段，使得每段内部正序对数量之和最少。设\(w(i,j)\)表示区间\((i,j)\)内部正序对数量。则很轻松就能得到

\[w(i-1,j+1)+w(i,j)\geq w(i,j+1)+w(i-1,j) \]

因为其它所有正序对都在两个中被统计了，唯独\((i-1,j+1)\)的正序对只有可能在前一半中被统计。因此此式显然成立，即四边形不等式成立，可以使用决策单调性优化。

因此直接套用分治+类似莫队的\(w\)求法即可。复杂度\(O(nk\log^2n)\)。

代码（将正序对转换成了逆序对）：

#include<bits/stdc++.h>
using namespace std;
typedef long long lol;
int n,m,t[25010],a[25010],ll,rr;
lol res,f[25010],g[25010];
void add(int x,int y){
	while(x<=n)t[x]+=y,x+=x&-x;
}
int ask(int x){
	int rt=0;
	while(x)rt+=t[x],x-=x&-x;
	return rt;
}
lol calc(int l,int r){
	if(l>r)return 0x3f3f3f3f3f3f3f3f;
	while(l>ll)add(a[ll],-1),res-=ask(a[ll]),ll++;
	while(l<ll)--ll,res+=ask(a[ll]),add(a[ll],1);
	while(r<rr)add(a[rr],-1),res-=ask(n)-ask(a[rr]),rr--;
	while(r>rr)++rr,res+=ask(n)-ask(a[rr]),add(a[rr],1);
	return res;
}
void func(int l,int r,int L,int R){
	if(l>r||L>R)return;
	int mid=(l+r)>>1,mp;
	lol mn=0x3f3f3f3f3f3f3f3f;
	for(int i=L;i<=R;i++)if(f[i]+calc(i+1,mid)<mn)mn=f[i]+calc(i+1,mid),mp=i;
	g[mid]=mn;
	func(l,mid-1,L,mp),func(mid+1,r,mp,R);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]=n-a[i]+1,res+=ask(n)-ask(a[i]),f[i]=res,add(a[i],1);
	ll=1,rr=n;
	while(--m)func(1,n,0,n-1),memcpy(f,g,sizeof(f));
	printf("%lld\n",f[n]);
	return 0;
}

III.[GYM102904B]Dispatch Money

考虑设 \(f_i\) 表示长度为 \(i\) 的前缀的最优划分。则我们发现，有 \(f_j+\operatorname{inversion}(j+1,i)\rightarrow f_i\)，其中 \(\text{inversion}\) 是区间逆序对数。

区间逆序对数不好处理，但是我们考虑像莫队一样处理，则其可以轻松地使用树状数组，从任何一个 \(\operatorname{inversion}(l,r)\) 求出 \(\operatorname{inversion}(l',r')\)。

类莫队转移是分治优化DP的配套。但是分治优化DP要求转移具有单调性，此处明显 \(\text{inversion}\) 函数满足四边形不等式，可以使用分治优化。

分治优化还得有一个前提，即转移分层，形式化来说就是转移形如 \(g_j+\operatorname{inversion}(j+1,i)\rightarrow f_i\)，与本题结构不同。

但是，在分治的外面再套一个CDQ分治，即可使得转移分层——总是左子区间的 \(f\) 转移给右子区间的 \(f\)。

于是复杂度 \(O(n\log^3n)\)，其中的三个 \(\log\) 分别来自于CDQ、分治优化、树状数组。明显三个玩意常数都贼小，于是可以卡过。

但我们还不满足。现在考虑优化。

明显优化只能从树状数组下手。于是问题转换为能否 \(O(1)\) 地进行莫队的区间端点移动。考虑区间端点移动时，我们查询了区间中大于/小于某个数的元素个数，其可以被差分转换为前缀大于/小于查询。

考虑分块预处理。我们在值域上每 \(\sqrt n\) 分一个块，维护块内元素个数。与此同时，我们再在块间以及各个块内部作前缀和。这样，在往前缀内加入新元素时，就只需 \(O(\sqrt n)\) 地重构块内前缀和，再 \(O(\sqrt{n})\) 地重构块间前缀和，这样就能 \(O(1)\) 地回答询问（散块内部前缀和、整块前缀和都可以 \(O(1)\) 得到）。

但是这样的查询是离线的。只需要对其可持久化即可做到在线询问。因为每次加入一个数，只会变动 \(O(\sqrt n)\) 级别的元素，所以时空复杂度都是 \(O(n\sqrt{n})\)。这样就可以 \(O(1)\) 进行端点移动，总复杂度为 \(O(n\sqrt n+n\log^2n)\)。

这里因为笔者不会 \(O(1)\) 对数组可持久化，因此直接使用 \(O(n\log^3n)\) 暴力水过去了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[300100],t[300100];
void ADD(int x,int tp){while(x)t[x]+=tp,x-=x&-x;}
int SUM(int x){int ret=0;while(x<=n)ret+=t[x],x+=x&-x;return ret;}
int LL=1,RR;
ll sum,f[300100];
void PushL(int x){
	sum+=SUM(1)-SUM(a[x]);
	ADD(a[x],1);
}
void PopL(int x){
	ADD(a[x],-1);
	sum-=SUM(1)-SUM(a[x]);
}
void PushR(int x){
	sum+=SUM(a[x]);
	ADD(a[x],1);
}
void PopR(int x){
	ADD(a[x],-1);
	sum-=SUM(a[x]);
}
ll CALC(int L,int R){
//	printf("BEF:%d\n",sum);
	while(LL>L)PushL(--LL);
	while(RR<R)PushR(++RR);
//	printf("BEF:%d\n",sum);
	while(LL<L)PopL(LL++);
	while(RR>R)PopR(RR--);
//	printf("[%d,%d]:%d\n",L,R,sum);
	return sum;
}
void solve(int l,int r,int L,int R){
	if(l>r)return;
//	printf("[%d,%d]:[%d,%d]\n",l,r,L,R);
	int mid=(l+r)>>1,MID=L;
	ll mn=CALC(L+1,mid)+f[L];
	for(int i=L+1;i<=R;i++)if(CALC(i+1,mid)+f[i]<mn)mn=CALC(i+1,mid)+f[i],MID=i;
	f[mid]=min(f[mid],mn+m);
	solve(l,mid-1,L,MID),solve(mid+1,r,MID,R);
}
void CDQ(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	CDQ(l,mid);
	solve(mid+1,r,l,mid);
	CDQ(mid+1,r); 
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[i]=CALC(1,i)+m;
//	for(int i=1;i<=n;i++)printf("%d ",f[i]);puts("");
	CDQ(1,n);
//	for(int i=1;i<=n;i++)printf("%d ",f[i]);puts("");
	printf("%lld\n",f[n]);
	return 0;
}

IV.[ZJOI2010]基站选址

蒟蒻没学过线段树，因此使用了一种奇奇怪怪的解法来水过这题

首先，大眼观察可得这题有决策单调性，严谨的证明可以用四边形不等式。具体来说，考虑证明 \(w[l,r-1]+w[l+1,r]\leq w[l+1,r+1]+w[l,r]\)，其中 \(w[l,r]\) 意为最近的两个基站修在 \([l,r]\) 的代价。观察到两者间的差异仅在存在覆盖区间为 \([l+1,r-1]\) 的村庄时存在，此时此村庄的代价不会在前面计算，而会在后面计算一次。

然后，题目很明显是让我们用分治优化的亚子。于是套上分治优化，考虑莫队式求出 \(w[l,r]\)。

显然 \(w[l,r]\) 在移动端点时的变化——不妨以右端点右移为例——只会影响右边界 \(=r\)，且左边界 \(>l\) 的所有村庄。于是我们在 \(r\) 的位置开个 vector 装所有右端点 \(=r\) 的村庄，然后按左端点递减排序并作前缀和，这样移动右端点时只需在桶中二分出 \(>l\) 的前缀即可。

单次移动复杂度 \(O(\log n)\)，则单次DP复杂度 \(O(n\log^2n)\)，总复杂度 \(O(m\log^2n)\)。因为常数小，水过去了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,pos[20100],bui[20100],rag[20100],cps[20100],res;
int lp[20100],rp[20100];
vector<int>vl[20100],vr[20100],sl[20100],sr[20100];
int sum;
bool cmpl(int x,int y){return lp[x]>lp[y];}
bool cmpr(int x,int y){return rp[x]<rp[y];}
void PushR(){
	int len=(lower_bound(vr[rp[0]].begin(),vr[rp[0]].end(),0,cmpl)-vr[rp[0]].begin())-1;
	if(len>=0)sum+=sr[rp[0]][len];
	rp[0]++;
//	printf("[%d,%d]:%d\n",lp[0],rp[0],sum);
}
void PopR(){
	rp[0]--;
	int len=(lower_bound(vr[rp[0]].begin(),vr[rp[0]].end(),0,cmpl)-vr[rp[0]].begin())-1;
	if(len>=0)sum-=sr[rp[0]][len];
//	printf("[%d,%d]:%d\n",lp[0],rp[0],sum);
}
void PushL(){
	int len=(lower_bound(vl[lp[0]].begin(),vl[lp[0]].end(),0,cmpr)-vl[lp[0]].begin())-1;
	if(len>=0)sum+=sl[lp[0]][len];
	lp[0]--;
//	printf("[%d,%d]:%d\n",lp[0],rp[0],sum);
}
void PopL(){
	lp[0]++;
	int len=(lower_bound(vl[lp[0]].begin(),vl[lp[0]].end(),0,cmpr)-vl[lp[0]].begin())-1;
	if(len>=0)sum-=sl[lp[0]][len];
//	printf("[%d,%d]:%d\n",lp[0],rp[0],sum);
}
int calc(int l,int r){
	while(lp[0]>l)PushL();
	while(rp[0]<r)PushR();
	while(lp[0]<l)PopL();
	while(rp[0]>r)PopR();
	return sum;
}
int f[20100],g[20100];
void solve(int l,int r,int L,int R){
	if(l>r)return;
	int mid=(l+r)>>1;
	int dim,mn=0x3f3f3f3f;
	for(int i=L;i<=min(R,mid-1);i++)if(g[i]+calc(i,mid)<mn)dim=i,mn=g[i]+calc(i,mid);
	f[mid]=mn+bui[mid];
	solve(l,mid-1,L,dim),solve(mid+1,r,dim,R);
}
int main(){
//	freopen("1.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++)scanf("%d",&pos[i]);
	for(int i=1;i<=n;i++)scanf("%d",&bui[i]);
	for(int i=1;i<=n;i++){
		scanf("%d",&rag[i]);
		vl[lp[i]=lower_bound(pos+1,pos+n+1,pos[i]-rag[i])-pos].push_back(i);
		vr[rp[i]=upper_bound(pos+1,pos+n+1,pos[i]+rag[i])-pos-1].push_back(i);
	}
	for(int i=1;i<=n;i++)scanf("%d",&cps[i]),res+=cps[i];
	for(int i=1;i<=n;i++){
		sort(vl[i].begin(),vl[i].end(),cmpr);
		if(!vl[i].empty()){sl[i].resize(vl[i].size()),sl[i][0]=cps[vl[i][0]];for(int j=1;j<vl[i].size();j++)sl[i][j]=sl[i][j-1]+cps[vl[i][j]];}
		sort(vr[i].begin(),vr[i].end(),cmpl);
		if(!vr[i].empty()){sr[i].resize(vr[i].size()),sr[i][0]=cps[vr[i][0]];for(int j=1;j<vr[i].size();j++)sr[i][j]=sr[i][j-1]+cps[vr[i][j]];}
	}/*
	for(int i=1;i<=n;i++)printf("%d %d\n",lp[i],rp[i]);
	for(int i=1;i<=n;i++){
		printf("%d:\n",i); 
		for(auto j:vl[i])printf("%d ",j);puts("");
		for(auto j:sl[i])printf("%d ",j);puts("");
		for(auto j:vr[i])printf("%d ",j);puts("");
		for(auto j:sr[i])printf("%d ",j);puts("");
	}*/
	lp[0]=rp[0]=0;
	for(int i=1;i<=n;i++)f[i]=calc(0,i)+bui[i];
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++)res=min(res,f[j]+calc(j,n+1)),g[j]=f[j],f[j]=0x3f3f3f3f;
		solve(i+1,n,i,n);
	}
	printf("%d\n",res);
	return 0;
}

IV.wqs 二分

wqs 二分是你解决某些问题的利器。

I.[GYM102268J]Jealous Split

wqs二分。

首先，先讲一下wqs二分的应用条件：

对于某个函数 \(f(x)\) 和一个特定的 \(x\)，要求出 \(f(x)\) 的值的复杂度是不可接受的；但是，若满足 \(f\) 是上凸/下凹的，且对于一个给定的 \(k\)，求出函数 \(f(x)+xk\) 的全局最大（也可能是小，视 \(f\) 的凹凸性而定）值及取得最值的位置的复杂度是可接受的，则此时就可以使用此种方式来求解。

具体来说，明显 \(f(x)\) 会在平面上构成一个凸壳；而对于一个给定的 \(k\) 求全局的最值，就相当于拿一条斜率为 \(-k\) 的直线去切凸壳，最值出现的位置就是切点的位置。

明显我们可以二分 \(k\)，即二分切线斜率。显然，通过二分，最后定会切到给定的 \(x\) 的位置，则此时我们就已经知道了 \(f(x)+xk\) 的值及 \(k\) 的值，倒着推一下就能推回 \(f(x)\) 出来。

但需要注意的是，对于某些 \(k\)，可能其与凸壳的切点不止一个，但因为其是凸的，故所有切点必定是一段区间。这时候就只需判断要求的 \(x\) 是在区间左边、内部或者右边即可。假如在区间内部，就可以直接返回了。

我们回到本题。

先从简单的情形想起：假如仅能切一刀，应该怎么切？

明显我们可以初始令最左方的元素单独成段，然后剩下元素再成一段。之后，不断向右移动切点，直到再往右移动会使得左段元素和大于右端元素和。这时，明显一定满足题目要求，因为当且仅当切点将要跨越的那个元素比当前的差要大才会停止移动，而这本身就表明已经有一个元素大于当前差的绝对值。

当能切更多刀时，明显我们可以通过逐步调整法使得每一刀都符合上述要求，也即解一定存在。

我们发现，这种情形下，对于任意实数 \(k>1\)，都应有所有（段内元素之和的 \(k\) 次幂）之和最小。取 \(k=2\) 会使计算简便。

于是我们现在就要找到一种分成 \(m\) 段且所有段的平方和最小。显然直接DP是 \(O(n^2)\) 的。

但是，我们发现平方和，随着段数的越分越多，肯定是递减的；不仅如此，其还是下凸的，因为否则我们一定可以更早地分开一段使答案更优。

考虑套上wqs二分。于是我们就变成了每切一段需要额外的代价 \(k\)，求平方和加上额外代价最小的分段方式。这是简单斜率优化，可以 \(O(n)\) 使用单调队列简单解决。

但是依据我们上文对wqs二分的分析，其好像并不能很好地求出方案来（因为不能保证切线刚好就切到我们需要的点上）。事实上，对于大多数的wqs二分题，我们都无法找到一种方案。

但是，注意到这里说的是大多数！事实上，对于本题这种“区间划分”wqs二分问题，的确是有一种构造方案的。具体而言，当求出的区间包含目标位置时，我们可以求出分段最少的方法以及最多的方法——可以通过斜率优化时当队首首个和次个元素的斜率与所需斜率相等时，出不出队来分别求出。明显我们的目标介于两种方法之间。

考虑用一种方法的一段前缀与另一种方法的一段后缀拼成完整的分段方案。考虑如何拼接。

首先，若两者方法出现了相同的分割点，明显在分割点处拼接前一半和后一半是一种合法的方案，因为最小方法和最大方法本质相当于从初始状态到终止状态的两条不同的最短路，一条从起点到终点的最短路，对于路径上所有节点，也必是最短路，故拼接合法。

我们还有一种拼接方法。考虑最少方案中，出现了一段区间 \([l,r]\)；最多方案中，出现了一段区间 \([L,R]\)；若有 \(l<L\land R<r\)，则我们可以用最少方案中 \(l\) 以前的前缀，拼上最多方案中 \(R\) 以后的后缀构成一组方案，也可以用 \(L\) 以前和 \(r\) 以后拼成另一种方案。具体的话，因为区间和的平方函数满足四边形不等式，所以新方案一定不更劣；但因为其本身都是最短路，故新方案最优也只能是最短路，所以两者结合，就得到新方案必定是最短路。

可以被证明的是，一定存在一种拼接方案满足长度恰好为任何 \(k\in[L,R]\)，其中 \(L,R\) 分别为最少方案、最多方案的长度。因为依据鸽巢原理，最多方案中一定至少有 \(R-L\) 个区间是最少方案中某个区间的子区间；而我们构造的一种方案中包含多少个上述区间，其长度就会在 \(L\) 基础上增加多少。明显我们上述方案中包含了从 \(0\) 个到 \(R-L\) 个所有可能需要的个数的构造方式，故我们一定可以构造出符合条件的方式。

于是我们现在已经知道如何二分、如何构造方式了。是不是就结束了呢？

稍等！我们还没有讨论 \(0\) 的情形——\(0\) 会使得问题变麻烦，因为斜率优化时前缀和就不是严格单调递增了。一个明智的想法是忽略所有 \(0\)，直到方式构造完成后再加入 \(0\)。

然后就是一些具体实现的问题了。一开始我wqs二分写的是实数二分，因为考虑到斜率可能为一切实数。但是后来思考发现，只需整数二分，得到的直线就可以切到所有点，于是就换成了整数二分。

实际上，还有一个原因是本题数据范围就非常尴尬（序列中所有数之和最大为 \(50\) 亿，刚好爆 int，平方后就爆了 long long），即使使用long double，也会被卡精度 WA 71。用实数二分就无法避免地用 long double 存状态，因此会挂。

但是爆 long long 也意为着我们不能使用 long long 储存。我尝试使用了压 13 个 bit 的 \(8\) 个 int 来模拟 __int128，但是被卡常了。所以最后索性直接上了 __int128（第一次知道 CF 开 C++17(64) 就能用 __int128 的），才卡过。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 ii;
int n,m,F[100100],G[100100];
ii f[100100],g[100100];
ll s[100100];
ii sqr(ll x){return (ii)x*x;}
int read(){
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x;
}
int q[100100],l,r;
int che(ll ip){
//	printf("%lld:\n",ip);
	l=r=0;
	for(int i=1;i<=n;i++){
		if(s[i]==s[i-1]){f[i]=f[i-1],F[i]=F[i-1];continue;}
//		if(r-l>=1)(2*BigNum(s[i])*(s[q[l+1]]-s[q[l]])).print(),(f[q[l+1]]-f[q[l]]+sqr(s[q[l+1]])-sqr(s[q[l]])).print(),puts("");
		while(r-l>=1&&f[q[l+1]]-f[q[l]]+sqr(s[q[l+1]])-sqr(s[q[l]])<(ii)2*s[i]*(s[q[l+1]]-s[q[l]]))l++;
		F[i]=q[l],f[i]=f[q[l]]+sqr(s[i]-s[q[l]])+ip;
		while(r-l>=1&&(f[q[r]]-f[q[r-1]]+sqr(s[q[r]])-sqr(s[q[r-1]]))*(s[i]-s[q[r]])>(f[i]-f[q[r]]+sqr(s[i])-sqr(s[q[r]]))*(s[q[r]]-s[q[r-1]]))r--;
		q[++r]=i;
	}
//	for(int i=1;i<=n;i++)f[i].print();puts("");
//	for(int i=1;i<=n;i++)printf("%d ",F[i]);puts("");
	l=r=0;
	for(int i=1;i<=n;i++){
		if(s[i]==s[i-1]){g[i]=g[i-1],G[i]=G[i-1];continue;}
//		if(r-l>=1)printf("%d:%d,%d\n",i,q[l],q[l+1]),(2*BigNum(s[i])*(s[q[l+1]]-s[q[l]])).print(),(g[q[l+1]]-g[q[l]]+sqr(s[q[l+1]])-sqr(s[q[l]])).print(),puts("");
		while(r-l>=1&&g[q[l+1]]-g[q[l]]+sqr(s[q[l+1]])-sqr(s[q[l]])<=(ii)2*s[i]*(s[q[l+1]]-s[q[l]]))l++;
		G[i]=q[l],g[i]=g[q[l]]+sqr(s[i]-s[q[l]])+ip;
		while(r-l>=1&&(g[q[r]]-g[q[r-1]]+sqr(s[q[r]])-sqr(s[q[r-1]]))*(s[i]-s[q[r]])>=(g[i]-g[q[r]]+sqr(s[i])-sqr(s[q[r]]))*(s[q[r]]-s[q[r-1]]))r--;
		q[++r]=i;
	}
//	for(int i=1;i<=n;i++)g[i].print();puts("");
//	for(int i=1;i<=n;i++)printf("%d ",G[i]);puts("");
	l=0;for(int i=n;i;i=F[i])l++;
	r=0;for(int i=n;i;i=G[i])r++;
//	printf("[%d %d]\n",l,r);
	if(l>m)return -1;
	if(r<m)return 1;
	return 0;
}
vector<int>u,v;
int tot;
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)s[i]=s[i-1]+read(),tot+=(s[i]!=s[i-1]);
	puts("Yes");
	if(tot<m){//cases when there have to be single 0 sections
		for(int i=1;i<n;i++){
			if(tot<m&&s[i]==s[i-1])tot++,printf("%d ",i);
			if(s[i]!=s[i-1])printf("%d ",i);
		}puts("");return 0;
	}
//	for(int i=1;i<=n;i++)printf("%Lf ",s[i]);puts("");
	ll L=0,R=0x3f3f3f3f3f3f3f3f,mid;
	while(true){
//		printf("%lld %lld\n",L,R);
		int tmp=che(mid=(L+R)>>1);
		if(tmp==-1)L=mid+1;
		if(tmp==1)R=mid-1;
		if(!tmp)break;
	}
//	printf("%d %d\n",l,r);
	for(int i=n;i;i=F[i])u.push_back(i);u.push_back(0),reverse(u.begin(),u.end());
	for(int i=n;i;i=G[i])v.push_back(i);v.push_back(0),reverse(v.begin(),v.end());
//	for(auto i:u)printf("%d ",i);puts("");
//	for(auto i:v)printf("%d ",i);puts("");
//	if(l==m){for(int i=1;i+1<u.size();i++)printf("%d ",u[i]);puts("");return 0;}
//	if(r==m){for(int i=1;i+1<v.size();i++)printf("%d ",v[i]);puts("");return 0;}
	for(int i=1,j=0;i<u.size();i++){
		for(;j<v.size()&&v[j]<u[i];j++){
			if(!j||v[j-1]<=u[i-1])continue;
			if(i+v.size()-j-1==m){for(int k=1;k<i;k++)printf("%d ",u[k]);for(int k=j;k+1<v.size();k++)printf("%d ",v[k]);puts("");return 0;}
			if(j+u.size()-i-1==m){for(int k=1;k<j;k++)printf("%d ",v[k]);for(int k=i;k+1<u.size();k++)printf("%d ",u[k]);puts("");return 0;}
		}
		if(j==v.size()||v[j]!=u[i])continue;
		if(i+v.size()-j-1==m){for(int k=1;k<i;k++)printf("%d ",u[k]);for(int k=j;k+1<v.size();k++)printf("%d ",v[k]);puts("");return 0;}
		if(j+u.size()-i-1==m){for(int k=1;k<j;k++)printf("%d ",v[k]);for(int k=i;k+1<u.size();k++)printf("%d ",u[k]);puts("");return 0;}
	}
	return 0;
}

II.[HDU6094]Rikka with K-Match

依旧wqs二分。

首先，依据我们之前提到过的一个性质，“凡是可以表示成费用流模型的东西都有凹凸性”，本题也不例外，关于匹配个数的函数是凹的。

凹的就可以wqs二分。于是问题转换为最小权任意匹配。因为 \(m\) 只有 \(4\)，使用轮廓线DP即可在 \(O(nm2^m)\) 时间内解决问题。

需要注意的是本题二分的边界。或许会认为仅仅是 \(10^9\) 就行了，但考虑一条长度为 \(nm\) 的 \(1\) 与 \(10^9\) 交错的链，且链的开头结尾都是 \(10^9\)，就会发现最后一条边的斜率是 \(10^9\times nm\) 级别的。于是要把边界开到 \(10^{14}\)，这样能保证不爆 long long，同时还能求出答案。

时间复杂度 \(O(nm2^m\log 10^{14})\)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,q,X[40100][4],Y[40100][4],F[40100][4][1<<4],G[40100][4][1<<4],lim;
ll f[40100][4][1<<4];
void chmn(int i,int j,int k,int K,ll bon,bool mat){
	int I=i-!j,J=(!j?m:j)-1;
	if(f[i][j][k]>f[I][J][K]+bon)f[i][j][k]=f[I][J][K]+bon,F[i][j][k]=F[I][J][K]+mat,G[i][j][k]=G[I][J][K]+mat;
	else if(f[i][j][k]==f[I][J][K]+bon)F[i][j][k]=min(F[i][j][k],F[I][J][K]+mat),G[i][j][k]=max(G[i][j][k],G[I][J][K]+mat);
}
int che(ll ip){
//	printf("%d\n",ip);
	for(int i=0;i<n;i++)for(int j=0;j<m;j++){
		if(!i&&!j){for(int k=0;k<lim;k++)f[i][j][k]=0;continue;}
		for(int k=0;k<lim;k++)f[i][j][k]=0x3f3f3f3f3f3f3f3f;
		for(int k=0;k<lim;k++){
			if(i&&!(k&(1<<j)))chmn(i,j,k|(1<<j),k,X[i][j]-ip,true);
			if(j&&!(k&(1<<(j-1))))chmn(i,j,k|(1<<(j-1))|(1<<j),k,Y[i][j]-ip,true);
			chmn(i,j,k&(lim-1-(1<<j)),k,0,false);
		}
	}
	ll mn=0x3f3f3f3f3f3f3f3f;
	for(int k=0;k<lim;k++)mn=min(mn,f[n-1][m-1][k]);
	int L=0x3f3f3f3f,R=0;
	for(int k=0;k<lim;k++)if(mn==f[n-1][m-1][k])L=min(L,F[n-1][m-1][k]),R=max(R,G[n-1][m-1][k]);
	if(L>q)return -1;
	if(R<q)return 1;
	printf("%lld\n",mn+ip*q);
	return 0;
}
void read(int &x){
	x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
	read(T);
	while(T--){
		read(n),read(m),read(q),lim=1<<m;
		for(int i=1;i<n;i++)for(int j=0;j<m;j++)read(X[i][j]);
		for(int i=0;i<n;i++)for(int j=1;j<m;j++)read(Y[i][j]);
		ll l=0,r=1e14,mid;
		while(true){
			int tp=che(mid=(l+r)>>1);
			if(tp==-1)r=mid-1;
			if(tp==1)l=mid+1;
			if(!tp)break;
		}
	}
	return 0;
}

III.[IOI2000] 邮局 加强版

Observation 1. 若一段村庄中设一个邮局，则邮局一定设在其中位数（若是偶数则任一中位数）的位置。

Observation 2. 若令 \(w(l,r)\) 为区间 \((l,r)\) 中村庄设一个邮局的费用，则其满足四边形不等式。

Observation 3. 显然全段中修几个邮局的函数有凹性，可以wqs二分。

考虑check二分的 \(mid\)。则我们有转移式

\[f_i=\min\limits_{j<i}f_j+w(j+1,i)+mid \]

当转移分层时，因为四边形不等式得出的决策单调性，可以分治解决；不分层时，一种解法是使用CDQ分治，正如[GYM102904B]Dispatch Money。但是那题囿于逆序对没有 \(O(1)\) 的在线计算方法，所以只能莫队式解决；而本题的 \(w\) 函数是可以简单 \(O(1)\) 在线解决的，因此没有必要使用CDQ分治。

考虑我们当前已经求出了 \(1\sim i\) 所有的 \(f\) 值。此时，位置 \(0\) 转移的位置必定是从 \(i+1\) 开始的一段（当然可能为空），位置 \(1\) 转移的位置必定是紧接着 \(0\) 的转移段后的一段（仍可能为空）……位置 \(i\) 是紧接着 \(i-1\) 的转移段往后一直到结尾的一段。

显然，此时 \(i+1\) 最优转移点已经明确，是从左到右第一个非空的段。但是我们要让其它东西也可以从 \(i+1\) 转移来。

明显，\(i+1\) 转移到的位置必定是一段后缀。于是我们从右往左枚举每一段，若这段最左方的位置从 \(i+1\) 转移更优，显然这一整段都应从 \(i+1\) 转移，然后再判断下一段；否则，就在这段中二分出 \(i+1\) 更优的后缀，然后这段后缀，再加上之前已经判断为 \(i+1\) 转移的那些段，就是 \(i+1\) 的转移段。

这样，内层DP的复杂度就是 \(O(n\log n)\) 的；再套上wqs二分，复杂度就是 \(O(n\log^2n)\) 的。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[500100],F[500100],G[500100],pos[500100],trs[500100],l,r;
ll s[500100],f[500100],g[500100];
ll calc(int l,int r){return s[l-1]+s[r]-s[(l+r)/2]-s[(l+r-1)/2];}
void read(int &x){
	x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int che(ll ip){
//	printf("%lld\n",ip); 
	l=r=1,trs[l]=0;
	for(int i=1;i<=n;i++){
		if(l<r&&pos[l]==i)l++;
		f[i]=f[trs[l]]+calc(trs[l]+1,i)+ip,F[i]=F[trs[l]]+1;
		if(i==n)break;
		pos[l-1]=i+1,pos[r]=n+1;
		while(true){
			if(r<l){trs[++r]=i;break;}
			if(f[i]+calc(i+1,pos[r-1])<=f[trs[r]]+calc(trs[r]+1,pos[r-1])){r--;continue;}
			int L=pos[r-1],R=pos[r];
			while(L+1<R){
				int mid=(L+R)>>1;
				if(f[i]+calc(i+1,mid)<=f[trs[r]]+calc(trs[r]+1,mid))R=mid;
				else L=mid;
			}
			if(R<=n)r++,pos[r-1]=R,trs[r]=i;
			break;
		}
	}
//	for(int i=1;i<=n;i++)printf("%lld ",f[i]);puts("");
//	for(int i=1;i<=n;i++)printf("%d ",F[i]);puts("");
	
	l=r=1,trs[l]=0;
	for(int i=1;i<=n;i++){
		if(l<r&&pos[l]==i)l++;
		g[i]=g[trs[l]]+calc(trs[l]+1,i)+ip,G[i]=G[trs[l]]+1;
		if(i==n)break;
		pos[l-1]=i+1,pos[r]=n+1;
		while(true){
			if(r<l){trs[++r]=i;break;}
			if(g[i]+calc(i+1,pos[r-1])<g[trs[r]]+calc(trs[r]+1,pos[r-1])){r--;continue;}
			int L=pos[r-1],R=pos[r];
			while(L+1<R){
				int mid=(L+R)>>1;
				if(g[i]+calc(i+1,mid)<g[trs[r]]+calc(trs[r]+1,mid))R=mid;
				else L=mid;
			}
			if(R<=n)r++,pos[r-1]=R,trs[r]=i;
			break;
		}
	}
	
	int R=F[n],L=G[n];
//	printf("%d %d\n",L,R);
	if(L>m)return 1;
	if(R<m)return -1;
	printf("%lld\n",f[n]-ip*m);
	return 0;
}
int main(){
	read(n),read(m);
	for(int i=1;i<=n;i++)read(a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
	ll l=0,r=1e12,mid;
	while(true){
		int tp=che(mid=(l+r)>>1);
		if(tp==-1)r=mid-1;
		if(tp==1)l=mid+1;
		if(!tp)break;
	}
	return 0;
}

IV.[国家集训队]Tree I

两年前刚学MST时做这题WA了，然后两年后才把它补上……

明显直接wqs二分就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,q,dsu[50100],ip;
int read(){
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x;
}
struct dat{
	int u,v,w,c;
	void READ(){u=read()+1,v=read()+1,w=read(),c=!read();}
	int calc()const{return c?ip+w:w;}
	friend bool operator<(const dat&u,const dat&v){return u.calc()==v.calc()?u.c<v.c:u.calc()<v.calc();}
}p[100100];
vector<dat>v[2];
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
bool merge(int x,int y){x=find(x),y=find(y);if(x==y)return false;dsu[x]=y;return true;}
int che(){
//	printf("%lld:\n",ip);
	for(int i=0,j=0;i<v[0].size()||j<v[1].size();)if(i!=v[0].size()&&(j==v[1].size()||v[0][i]<v[1][j]))p[i+j+1]=v[0][i],i++;else p[i+j+1]=v[1][j],j++;
	int f=0,F=0;
	for(int i=1;i<=n;i++)dsu[i]=i;
	for(int i=1,j=1;i<=m;i=j){
		while(j<=m&&p[i].calc()==p[j].calc())j++;
		for(int k=i;k<j;k++)if(merge(p[k].u,p[k].v))f+=p[k].calc(),F+=p[k].c;
	}
	
	int g=0,G=0;
	for(int i=1;i<=n;i++)dsu[i]=i;
	for(int i=1,j=1;i<=m;i=j){
		while(j<=m&&p[i].calc()==p[j].calc())j++;
		for(int k=j-1;k>=i;k--)if(merge(p[k].u,p[k].v))g+=p[k].calc(),G+=p[k].c;
	}
	if(F>q)return 1;
	if(G<q)return -1;
	printf("%d\n",f-ip*q);
	return 0;
}
int main(){
//	freopen("P2619_10.in","r",stdin);
	n=read(),m=read(),q=read();
	for(int i=1;i<=m;i++)p[i].READ(),v[p[i].c].push_back(p[i]);
	for(int i=0;i<2;i++)sort(v[i].begin(),v[i].end());
	int l=-100,r=100;
	while(true){
		ip=(l+r)>>1;
		int tp=che();
		if(tp==-1)r=ip-1;
		if(tp==1)l=ip+1;
		if(!tp)return 0;
	}
	return 0;
} 

V.CF739E Gosha is hunting

因为 \(n\) 是 \(2000\)，我们可以想出设一个二维状态来保证 \(n,a\) 这两维，然后再wqs二分 \(b\) 这一维。（明显，随着 \(b\) 越来越大，呈现一凸函数）。

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

需要注意的是，在wqs二分 \(b\) 后，我们不能再二分 \(a\)，因为我们不知道此时应该优先最小化 \(a\) 的数量还是 \(b\) 的数量。

代码：

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-9;
int n,a,b,F[2010][2010],G[2010][2010];
double p[2010],q[2010],f[2010][2010];
int cmp(double ip){
	if(ip>eps)return 1;
	if(ip<-eps)return -1;
	return 0;
}
void trans(int i,int j,int I,int J,double k,int K){
	if(cmp(f[I][J]-k)==-1)f[I][J]=k,F[I][J]=F[i][j]+K,G[I][J]=G[i][j]+K;
	else if(cmp(f[I][J]-k)==0)F[I][J]=min(F[I][J],F[i][j]+K),G[I][J]=max(G[I][J],G[i][j]+K);
}
int che(double ip){
	for(int i=1;i<=n;i++)for(int j=0;j<=min(i,a);j++)f[i][j]=-n;
	for(int i=0;i<n;i++)for(int j=0;j<=min(i,a);j++){
		if(j+1<=a){
			trans(i,j,i+1,j+1,f[i][j]+p[i+1],0);
			trans(i,j,i+1,j+1,f[i][j]+1-(1-p[i+1])*(1-q[i+1])-ip,1);
		}
		trans(i,j,i+1,j,f[i][j],0);
		trans(i,j,i+1,j,f[i][j]+q[i+1]-ip,1);
	}
	if(F[n][a]>b)return 1;
	if(G[n][a]<b)return -1;
	printf("%lf\n",f[n][a]+ip*b);
	return 0;
}
int main(){
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
	for(int i=1;i<=n;i++)scanf("%lf",&q[i]);
	double l=0,r=1,mid;
	while(true){
		int tp=che(mid=(l+r)/2);
		if(tp==1)l=mid;
		if(tp==-1)r=mid;
		if(!tp)break;
	}
	return 0;
}

VI.忘情

wqs二分水题，明显那个式子可以被化成 \((1+\sum x)^2\)，于是可以斜率优化，然后又明显随着段数越分越多函数是凹的，于是可以简单wqs二分。时间复杂度 \(O(n\log n)\)。

需要注意的是，因为二分上界是 \(10^{18}\)，所以得开 __int128。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 ii;
int n,m,s[100100],F[100100],q[100100],l,r;
ii f[100100];
inline void print(ii x){
	if(x<=9)putchar('0'+x);
	else print(x/10),putchar('0'+x%10);
}
ll sqr(int x){return 1ll*x*x;}
int che(ll ip){
//	printf("%lld\n",ip);
	l=r=0;
	for(int i=1;i<=n;i++){
		while(l<r&&f[q[l]]-f[q[l+1]]+sqr(s[q[l]])-sqr(s[q[l+1]])-2*(s[q[l]]-s[q[l+1]])>2ll*s[i]*(s[q[l]]-s[q[l+1]]))l++;
//		printf("%d:%d\n",i,q[l]);
		f[i]=f[q[l]]+sqr(s[i]-s[q[l]]+1)+ip,F[i]=F[q[l]]+1;
		while(l<r&&(f[q[r-1]]-f[q[r]]+sqr(s[q[r-1]])-sqr(s[q[r]]))*(s[q[r]]-s[i])>(f[q[r]]-f[i]+sqr(s[q[r]])-sqr(s[i]))*(s[q[r-1]]-s[q[r]]))r--;
		q[++r]=i;
	}
//	for(int i=1;i<=n;i++)printf("%lld ",f[i]);puts("");
//	for(int i=1;i<=n;i++)printf("%d ",F[i]);puts("");
	int L=F[n];
	l=r=0;
	for(int i=1;i<=n;i++){
		while(l<r&&f[q[l]]-f[q[l+1]]+sqr(s[q[l]])-sqr(s[q[l+1]])-2*(s[q[l]]-s[q[l+1]])>=2ll*s[i]*(s[q[l]]-s[q[l+1]]))l++;
		f[i]=f[q[l]]+sqr(s[i]-s[q[l]]+1)+ip,F[i]=F[q[l]]+1;
		while(l<r&&(f[q[r-1]]-f[q[r]]+sqr(s[q[r-1]])-sqr(s[q[r]]))*(s[q[r]]-s[i])>=(f[q[r]]-f[i]+sqr(s[q[r]])-sqr(s[i]))*(s[q[r-1]]-s[q[r]]))r--;
		q[++r]=i;
	}
	int R=F[n];
//	printf("[%d,%d]\n",L,R);
	if(L>m)return 1;
	if(R<m)return -1;
	print(f[n]-(ii)ip*m);
	return 0;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&s[i]),s[i]+=s[i-1];
	ll L=0,R=1e18,mid;
	while(true){
		int tp=che(mid=(L+R)>>1);
		if(tp==-1)R=mid-1;
		if(tp==1)L=mid+1;
		if(!tp)break;
	}
	return 0;
}

VII.[八省联考2018]林克卡特树

一眼发现函数是凸的。然后思考发现直接一个树形DP就能进行二分的check：设 \(f_{i,0/1/2}\) 分别表示节点 \(i\)，其中 \(i\) 未被选/是一条链的链顶/被一条链经过，然后直接DP就行。

为什么二分边界要开到 \(10^{12}\) 呀

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,g[300100][3],head[300100],cnt;
ll f[300100][3],ip;//0:x is on nothing 1:x is currently on a path 2:x's path has been matched
struct node{int to,next,val;}edge[600100];
void ae(int u,int v,int w){
	edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
	edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
void trans(ll &F,int &G,ll ff,int gg){
	if(F<ff)F=ff,G=gg;
	else if(F==ff)G=min(G,gg);
}
void dfs(int x,int fa){
	f[x][0]=f[x][1]=f[x][2]=0,g[x][0]=g[x][1]=g[x][2]=0;
	for(int i=head[x],y,z;i!=-1;i=edge[i].next){
		y=edge[i].to,z=edge[i].val;
		if(y==fa)continue;
		dfs(y,x);
		
		f[x][2]+=f[y][2],g[x][2]+=g[y][2];
//		printf("%d,%d:%d,%d,%d,%d\n",x,y,f[x][1],f[y][1],z,-ip);
		trans(f[x][2],g[x][2],f[x][1]+f[y][1]+z-ip,g[x][1]+g[y][1]+1);
		
		f[x][1]+=f[y][2],g[x][1]+=g[y][2];
		
		trans(f[x][1],g[x][1],f[x][0]+f[y][1]+z,g[x][0]+g[y][1]);
		
		f[x][0]+=f[y][2],g[x][0]+=g[y][2];
	}
	trans(f[x][2],g[x][2],f[x][1]-ip,g[x][1]+1);
	trans(f[x][2],g[x][2],f[x][0],g[x][0]);
//	printf("%d:\n%d %d %d\n%d %d %d\n",x,f[x][0],f[x][1],f[x][2],g[x][0],g[x][1],g[x][2]);
}
int main(){
	scanf("%d%d",&n,&m),m++,memset(head,-1,sizeof(head));
	for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
	ll l=-1e12,r=1e12;
	while(l<r){
		ip=(l+r)>>1;
//		printf("%d------------\n",ip); 
		dfs(1,0);
		if(g[1][2]<=m)r=ip;
		else l=ip+1;
	}
	ip=l,dfs(1,0);
	printf("%lld\n",f[1][2]+1ll*l*m);
	return 0;
}

VIII.[MtOI2019]不可视境界线

一眼发现答案是凸的。那么套个 wqs 二分玩玩罢。

然后考虑 wqs 二分后应该怎么做：令 \(f_i\) 表示前 \(i\) 个圆的答案，则平方 DP 是简单的。

注意到两个圆的交的面积，随着圆心距离的拉远，是凸的。这意味着这个 DP 式满足四边形不等式，进而有决策单调性。

因为 DP 式是自己到自己的转移，所以用单调栈维护即可。

复杂度平方对数。

这里提一个醒，因为 double 的精度是 \(15\sim16\) 位，而二分的时候值域可能达到 \(10^9\)，故能留给小数部分的位数仅有 \(7\sim 8\) 位，进而如果把 eps 开得太小可能会因为 r-l 自动把过低位舍去而永远达不到 eps。解决方法是设一个二分次数上界，过了上界自动停止二分，就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
const double eps=1e-10;
int cmp(double x){if(x>eps)return 1;if(x<-eps)return -1;return 0;}
int n,K,R,a[100100];
double f[100100],S;int F[100100];
int id[100100],pos[100100];
double IN[20100];
double inter(int d){d=abs(d);return d>=(R<<1)?0:IN[d];}
bool cmp(int i,int j,int k){return cmp((f[i]-inter(a[k]-a[i]))-(f[j]-inter(a[k]-a[j])))==1;}
int DP(double c){
//	printf("%lf\n",c);
	int l=1,r=1;id[l]=0,f[0]=F[0]=0;
	for(int i=1;i<=n;i++){
		f[i]=f[id[l]]+S-c-inter(a[i]-a[id[l]]),F[i]=F[id[l]]+1;
//		for(int j=l;j<r;j++)printf("[%d:%d]",id[j],pos[j]);puts("");
//		printf("%d:%lf,%d\n",i,f[i],F[i]);
		while(l<r&&pos[l]<=i)l++;
		pos[l-1]=i;
		while(l<=r){
			if(pos[r-1]==n||cmp(i,id[r],pos[r-1]+1)){r--;continue;}
			int u=pos[r-1]+1,v=n;
			while(u<v){
				int w=(u+v+1)>>1;
				if(cmp(i,id[r],w))v=w-1;
				else u=w;
			}
			pos[r]=u;break;
		}id[++r]=i;
	}
	return F[n];
}
namespace FIFO{
char buf[1<<23],*p1=buf,*p2=buf;
#ifndef Troverld
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#else
#define gc() getchar()
#endif
template<typename T>void read(T&x){
	x=0;
	char c=gc();
	while(c>'9'||c<'0')c=gc();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=gc();
}
template<typename T>void print(T x){if(x<=9)putchar('0'+x);else print(x/10),putchar('0'+x%10);}
}using namespace FIFO;
int main(){
//	freopen("P5617_37.in","r",stdin);
	read(n),read(K),read(R);
	for(int i=0;i<(R<<1);i++){double theta=2*acos(0.5*i/R);IN[i]=(theta-sin(theta))*R*R;}
	a[0]=-(R<<1);for(int i=1;i<=n;i++)read(a[i]);
	double l=0,r=S=pi*R*R;int round=0;
	while(r-l>1e-8&&++round<=40){
		double mid=(l+r)/2;
		if(DP(mid)>=K)l=mid;else r=mid;
	}
	DP(l);
	printf("%.10lf\n",f[n]+l*K);
	return 0;
}

V.矩阵优化

事实上我个人不太想把矩阵优化归在此处，但是好像也没有更好的地方了……

I.[HNOI2010]公交线路

状压+矩乘的好题。

因为每\(p\)个位置中，每辆车就至少有\(1\)个位置，

所以我们可以状压一下。

设\(f[i][j]\)表示：

区间\([i,i+p-1]\)内的车站现在的规划情况是\(j\)的方案数。

显然，必有\(j\)的第\(p\)位是\(1\)，且\(j\)共有\(k\)位是\(1\)（\(j\)的第\(p\)位对应着\(i\)）。

则\(f[i][j]=\sum f[i-1][k]\)，其中\(k\)能转移到\(j\)。

那什么样的\(k\)能转移到\(j\)呢？

我们将\(k\)左移一位（即增加了 \(i+p-1\) 一位），然后删去第\(p\)位的数（即删去第 \(i-1\) 位），得到了一个\(k'\)。

如果\(k'\)和\(j\)只相差恰好\(1\)位，那么\(k\)就可以转移到\(j\)（第\(i-1\)位的车刚好跑到了着相差的一位）。

然后发现，对于每个\(f[i][j]\)，它的祖先的\(k\)都是完全一致的；因此可以矩乘优化，建立转移矩阵\(T[k][j]\)，如果状态\(k\)可以转移到\(j\)，则\(T[k][j]=1\)，否则为\(0\)。

则复杂度为\(S^3\log n\)，其中\(S\)是合法状态数量（即符合\(j\)的第\(p\)位是\(1\)，且\(j\)共有\(k\)位是\(1\)的\(j\)的数量）。我们有\(S=C_{p-1}^{k-1}\)，当\(p=10,k=5\ \operatorname{or}\ 6\)时取得最大值，有\(S=C_9^4\ \operatorname{or}\ C_9^5=126\)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=30031;
int n,m,p,len,sta[150];
struct mat{
	int g[150][150];
	mat(){memset(g,0,sizeof(g));}
	friend mat operator *(const mat &x,const mat &y){
		mat z;
		for(int i=0;i<len;i++)for(int j=0;j<len;j++)for(int k=0;k<len;k++)(z.g[i][j]+=x.g[i][k]*y.g[k][j])%=mod;
		return z;
	}
}X,I;
bool che(int x,int y){
	x<<=1,x-=(1<<p);
	return __builtin_popcount(x^y)<=1;
}
void ksm(int y){
	for(;y;X=X*X,y>>=1)if(y&1)I=I*X;
}
int main(){
	scanf("%d%d%d",&n,&m,&p);
	for(int i=(1<<(p-1));i<(1<<p);i++)if(__builtin_popcount(i)==m)sta[len++]=i;
	for(int i=0;i<len;i++)I.g[i][i]=1;
	for(int i=0;i<len;i++)for(int j=0;j<len;j++)X.g[i][j]=che(sta[i],sta[j]);
	ksm(n-m);
	printf("%d\n",I.g[len-1][len-1]);
	return 0;
} 

II.CF621E Wet Shark and Blocks

一眼，\(b\leq 10^9\)，矩阵快速幂。

再一眼，\(x\leq 100\)，\(x^3\)刚好，因此可以矩乘；

然后每个块里面的东西都是一样的，仍然可以矩乘；

然后OK。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,p,q,cnt[10];
struct mat{
	int a[110][110];
	mat(){memset(a,0,sizeof(a));}
	friend mat operator *(const mat &x,const mat &y){
		mat z;
		for(int i=0;i<q;i++)for(int j=0;j<q;j++)for(int k=0;k<q;k++)(z.a[i][j]+=1ll*x.a[i][k]*y.a[k][j]%mod)%=mod;
		return z;
	}
}I,X;
int main(){
	scanf("%d%d%d%d",&n,&m,&p,&q);
	for(int i=0,x;i<n;i++)scanf("%d",&x),cnt[x]++;
	for(int i=0;i<q;i++)for(int j=0;j<10;j++)X.a[i][(i*10+j)%q]+=cnt[j];
	for(int i=0;i<q;i++)I.a[i][i]=1;
	for(;m;X=X*X,m>>=1)if(m&1)I=I*X;
	printf("%d\n",I.a[0][p]);
	return 0;
} 

III.[NOI Online #1 入门组]魔法

我们可以构造出原图的转移矩阵 \(A\)，表示只走原图的边的代价。这个直接暴力上Floyd即可。

我们还可以构造出魔法的转移矩阵\(B\)。

则，可以想到，答案一定是

\[ABABABABAB\dots ABA \]

这种样子。

故我们用\(B\)左乘\(A\)得到\(C=(BA)\)。则计算\(AC^k\)，即为答案。

时间复杂度\(O(n^3\log k)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,p;
struct Matrix{
	ll a[110][110];
	void init(){memset(a,0x3f,sizeof(a));for(int i=1;i<=n;i++)a[i][i]=0;}
	ll* operator[](int x){return a[x];}
	friend Matrix operator *(Matrix &u,Matrix &v){
		Matrix w;w.init();
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)w[i][j]=min(w[i][j],u[i][k]+v[k][j]);
		return w;
	}
}a,b;
int main(){
	scanf("%d%d%d",&n,&m,&p);
	a.init(),b.init();
	for(int i=1,x,y,z;i<=m;i++)scanf("%d%d%d",&x,&y,&z),a[x][y]=min(a[x][y],1ll*z),b[x][y]=min(b[x][y],-1ll*z);
	for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
//	for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",a[i][j]);puts("");}
	b=b*a;
//	for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",b[i][j]);puts("");}
	for(;p;p>>=1,b=b*b)if(p&1)a=a*b;
	printf("%lld\n",a[1][n]);
	return 0;
}

V.CF917C Pollywog

萌萌小水题。

首先这个操作一看就可以状压；状压从最左边开始的 \(K\) 位，状态数为 \(\dbinom Kx\)。转移写成矩阵，然后在特殊的地方停下来手动转移即可。

通过预处理矩阵的幂次，我们可以做到 \(O\Bigg(\dbinom Kx^3\log n+\dbinom Kx^2q+K^2q\Bigg)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,K,c[10],m,q,lim,sta[130],id[1<<10];
typedef long long ll;
void chmn(ll&x,ll y){if(x>y)x=y;}
struct Matrix{
ll a[130][130];
Matrix(){memset(a,0x3f,sizeof(a));}
ll*operator[](const int&x){return a[x];}
friend Matrix operator*(const Matrix&u,const Matrix&v){
	Matrix w;
	for(int i=0;i<lim;i++)for(int j=0;j<lim;j++)for(int k=0;k<lim;k++)chmn(w.a[i][j],u.a[i][k]+v.a[k][j]);
	return w;
}
void print()const{for(int i=0;i<lim;i++,puts(""))for(int j=0;j<lim;j++)printf("%lld ",a[i][j]);}
}mat[30];
ll f[130],g[130];
map<int,ll>mp;
int p[30],pos=1;
void consider(const Matrix&v){
	for(int i=0;i<lim;i++)for(int j=0;j<lim;j++)chmn(g[j],f[i]+v.a[i][j]);
	for(int i=0;i<lim;i++)f[i]=g[i],g[i]=0x3f3f3f3f3f3f3f3f;
}
void trans(int len){
	len=max(len,0);
	for(int i=29;i>=0;i--)if(len&(1<<i))consider(mat[i]);
	pos+=len;
	// printf("tlen%d:",pos);for(int i=0;i<lim;i++)printf("%d ",f[i]);puts("");
}
void trans(){
	for(int i=0;i<lim;i++){
		if(!(sta[i]&1)){chmn(g[id[sta[i]>>1]],f[i]);continue;}
		for(int j=1;j<=K;j++)if(!(sta[i]&(1<<j)))
			chmn(g[id[(sta[i]|(1<<j))>>1]],f[i]+c[j]+mp[pos+j]);
	}
	for(int i=0;i<lim;i++)f[i]=g[i],g[i]=0x3f3f3f3f3f3f3f3f;
	pos++;
	// printf("tsin%d:",pos);for(int i=0;i<lim;i++)printf("%d ",f[i]);puts("");
}
int main(){
	scanf("%d%d%d%d",&n,&K,&m,&q);
	for(int i=1;i<=K;i++)scanf("%d",&c[i]);
	memset(id,-1,sizeof(id));
	for(int i=0;i<(1<<K);i++)if(__builtin_popcount(i)==n)sta[lim]=i,id[i]=lim,lim++;
	// for(int i=0;i<lim;i++)printf("%d:%d\n",i,sta[i]);
	for(int i=0;i<lim;i++){
		if(!(sta[i]&1)){mat[0][i][id[sta[i]>>1]]=0;continue;}
		for(int j=1;j<=K;j++)if(!(sta[i]&(1<<j)))
			// printf("%d,%d(%d=%d)\n",i,j,(sta[i]|(1<<j))>>1,id[(sta[i]|(1<<j))>>1]),
			mat[0][i][id[(sta[i]|(1<<j))>>1]]=c[j];
	}
	// mat[0].print();
	for(int i=1;i<30;i++)mat[i]=mat[i-1]*mat[i-1];
	for(int i=1,x,y;i<=q;i++)scanf("%d%d",&x,&y),p[i]=x,mp[x]+=y;
	sort(p+1,p+q+1);
	memset(f,0x3f,sizeof(f)),memset(g,0x3f,sizeof(g)),f[0]=0;
	for(int i=1;i<=q;i++){
		trans(max(0,p[i]-K-pos));
		while(pos<=p[i]&&pos<=m-n)trans();
	}
	trans(m-n-pos+1);
	printf("%lld\n",f[0]);
	return 0;
}

标签：return,int,mid,笔记,long,优化,DP,dis
From： https://www.cnblogs.com/Troverld/p/17583056.html