526互联

[USACO2021JAN] Minimum Cost Paths P

发布时间 2023-12-19 16:59:04作者: 灰鲭鲨

[USACO21JAN] Minimum Cost Paths P

题目描述

Farmer John 的牧草地可以看作是一个\(N×M\)（\(2≤N≤10^9, 2≤M≤2⋅10^5\)）的正方形方格组成的二维方阵（想象一个巨大的棋盘）。对于 \(x∈[1,N],y∈[1,M]\)，从上往下第 \(x\) 行、从左往右第 \(y\) 列的方格记为 \((x,y)\)。此外，对于每一个 \(y∈[1,M]\)，第 \(y\) 列拥有一个代价 \(c_y\)（\(1≤c_y≤10^9\)）。

Bessie 从方格 \((1,1)\) 出发。如果她现在位于方格 \((x,y)\)，则她可以执行以下操作之一：

  • 如果 \(y<M\)，Bessie 可以以 \(x^2\) 的代价移动到下一列（\(y\) 增加一）。
  • 如果 \(x<N\)，Bessie 可以以 \(c_y\) 的代价移动到下一行（\(x\) 增加一）。

给定 \(Q\)（\(1≤Q≤2⋅10^5\)）个独立的询问，每个询问给定 \((x_i,y_i)\)（\(x_i∈[1,N],y_i∈[1,M]\)），计算 Bessie 从 \((1,1)\) 移动到 \((x_i,y_i)\) 的最小总代价。

输入格式

输入的第一行包含 \(N\) 和 \(M\)。

第二行包含 \(M\) 个空格分隔的整数 \(c_1,c_2,…,c_M\)。

第三行包含 \(Q\)。

最后 \(Q\) 行每行包含两个空格分隔的整数 \(x_i\) 和 \(y_i\)。

输出格式

输出 \(Q\) 行，为每个询问的答案。

注意本题计算中所使用的整数大小可能需要使用 64 位整数型（例如，C/C++ 中的 long long）。

样例 #1

样例输入 #1

5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4

样例输出 #1

0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69

提示

样例 1 解释

输出以方阵形式表示如下：

    1  2  3  4
  *--*--*--*--*
1 | 0| 1| 2| 3|
  *--*--*--*--*
2 | 1| 5| 9|13|
  *--*--*--*--*
3 | 2|11|20|29|
  *--*--*--*--*
4 | 3|19|35|49|
  *--*--*--*--*
5 | 4|29|54|69|
  *--*--*--*--*

测试点性质：

  • 测试点 1-3 满足 \(N,M≤2000\)。
  • 测试点 4-8 满足 \(c_2>c_3>⋯>c_M\)。
  • 测试点 9-15 满足 \(N≤2⋅10^5\)。
  • 测试点 16-20 没有额外限制。

供题：Benjamin Qi

考虑如果我在某一时刻从第 \(i\) 列直接到达了第 \(j\) 列，那么我最好是从哪一行走了过去。列出二次函数之后，得到最优的行在 \(f(i,j)=\lfloor\frac{c_j-c_i}{j-i}\rceil\)（\(\lfloor\rceil\)表示四舍五入）发现这东西很像凸包。

大胆猜想，最后所有转移点就是 \(f(i,j)\) 的下凸包。证明可以用保序回归。那么考虑离线并扫描线 \(i\)，单调栈维护凸包，查询的时候在凸包上二分出来第一个超过 \(x\) 的点。在单调栈时预处理前缀和。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
int n,m,c[N],st[N],tp,q,x[N];
LL ans[N],s[N];
vector<int>g[N];
int ask(int l,int r)
{
	return min(max(1,(c[r]-c[l]+r-l)/(2*r-2*l)),n);
}
int find(int x)
{
	int l=1,r=tp-1;
	while(l<=r)
	{
		int md=l+r>>1;
		if(ask(st[md],st[md+1])<=x)
			l=md+1;
		else
			r=md-1;
	}
	return l;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d",c+i);
	scanf("%d",&q);
	for(int i=1,y;i<=q;i++)
		scanf("%d%d",x+i,&y),g[y].push_back(i);
	st[tp=1]=1;
	for(int j:g[1])
		ans[j]=1LL*c[1]*(x[j]-1);
	for(int i=2,ls,nw;i<=m;i++)
	{
		while(tp>1&&1LL*(c[i]-c[st[tp]])*(st[tp]-st[tp-1])<=1LL*(c[st[tp]]-c[st[tp-1]])*(i-st[tp]))
			--tp;
		st[++tp]=i;
		if(tp==2)
			ls=1;
		else
			ls=ask(st[tp-2],st[tp-1]);
		nw=ask(st[tp-1],st[tp]);
		s[tp]=s[tp-1]+c[st[tp-1]]*1LL*(nw-ls)+(st[tp]-st[tp-1])*1LL*nw*nw;
		for(int j:g[i])
		{
			int k=find(x[j]);
			if(k==1)
				ls=1;
			else
				ls=ask(st[k-1],st[k]);
			ans[j]=s[k]+(x[j]-ls)*1LL*c[st[k]]+1LL*x[j]*x[j]*(i-st[k]);
		}
	}
	for(int i=1;i<=q;i++)
		printf("%lld\n",ans[i]);
}