【luogu P7294】Minimum Cost Paths P（二分）（單調棧）（斜率）

Minimum Cost Paths P

題目連結：luogu P7294

題目大意

給你一個 n*m 的矩陣，一開始你在 (1,1)。

如果你在 (x,y)，你可以花費 x^2 的費用走到 (x,y+1)，也可以花費 cy 的費用走到 (x+1,y)。

然後多組詢問，每次問你要走到 (x,y) 的最小費用。

思路

由于 n n n 很大， m m m 比較小，我們考慮離線，然後把詢問按 m m m 從小到大排。

那我們考慮 m m m 多了 1 1 1 會怎麼樣，就會要有一個位置從 m − 1 m-1 m−1 向下走，然後剩下全部往右走。

那我們就考慮一開始全部往右走，那貢獻就是 x − 1 x-1 x−1。

然後考慮在一個地方 ( x , y ) (x,y) (x,y) 往下走新多的貢獻。（後面的還是全部往右）

首先是 c y c_y cy​，然後剩下的往右走是 ( m − y ) ∗ ( x + 1 ) 2 (m-y)*(x+1)^2 (m−y)∗(x+1)2，然後之前剩下的往右走是 ( m − y ) ∗ x 2 (m-y)*x^2 (m−y)∗x2，相減就是 ( m − y ) ∗ ( 2 x + 1 ) (m-y)*(2x+1) (m−y)∗(2x+1)，是以新多的就是 c y + ( m − y ) ∗ ( 2 x + 1 ) c_y+(m-y)*(2x+1) cy​+(m−y)∗(2x+1)。

然後拆開移一下： c y − y − 2 x y + 2 x m + m c_y-y-2xy+2xm+m cy​−y−2xy+2xm+m。

那右邊的 2 x m + m 2xm+m 2xm+m 都是遲早都要，可以單獨拿出來，最後再算貢獻。

那有關的就是 c y − y − 2 x y c_y-y-2xy cy​−y−2xy，然後發現你可以看做是 ( − 2 y ) x + ( c y − y ) (-2y)x+(c_y-y) (−2y)x+(cy​−y)。

（考慮算最小值）

那就是一條直線，單調下降。

然後你要每次選的 y y y 遞增，那就是要維護一個上凸殼。（用單調棧維護）

至于裡面的直線，你考慮維護它在 x x x 為那個區間範圍的時候最優，然後你詢問你就二分出這個直線，前面的提前字首和統計好，然後這條之間再算一次，就可以了。

（記得加上之前省略的值）

代碼

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

struct ask {
	ll x, y, num;
	ll ans;
}qq[200001];
ll n, m, q, sta[200001], top;
ll l[200001], r[200001];
ll c[200001], sum[200001];
ll k[200001], b[200001];

bool cmp1(ask x, ask y) {
	return x.y < y.y;
}

bool cmp2(ask x, ask y) {
	return x.num < y.num;
}

ll met(ll x, ll y) {//算出兩條直線的交點（向上取整）
	return (b[y] - b[x] + (k[x] - k[y] - 1)) / (k[x] - k[y]);
}

bool worse(ll i, ll j) {
	if (met(i, j) <= l[i]) return 1;
	return 0;
}

ll get_line(ll x, ll l, ll r) {//算一整條的貢獻
	return (l + r) * (r - l + 1) / 2 * k[x] + (r - l + 1) * b[x];
}

int main() {
	scanf("%lld %lld", &n, &m);
	for (ll i = 1; i <= m; i++) {
		scanf("%lld", &c[i]);
		b[i] = c[i] - i; k[i] = -2 * i;
	}
	scanf("%lld", &q);
	for (ll i = 1; i <= q; i++) {
		scanf("%d %d", &qq[i].x, &qq[i].y);
		qq[i].num = i;
	}
	sort(qq + 1, qq + q + 1, cmp1);
	
	ll now = 1;
	for (ll i = 1; i <= m; i++) {
		r[i] = n;
		while (top && worse(sta[top], i)) top--;
		if (top) l[i] = max(1ll, met(sta[top], i));
			else l[i] = 1;
		if (l[i] <= r[i]) {
			r[sta[top]] = l[i] - 1;
			sta[++top] = i;
			sum[top - 1] = ((top - 1) ? sum[top - 2] : 0) + get_line(sta[top - 1], l[sta[top - 1]], r[sta[top - 1]]);
			sum[top] = sum[top - 1] + get_line(sta[top], l[sta[top]], r[sta[top]]);
		}
		
		while (now <= q && qq[now].y == i) {
			ll ans = -1, lll = 0, rr = top;
			while (lll <= rr) {
				ll mid = (lll + rr) >> 1;
				if (r[sta[mid]] >= qq[now].x - 1) rr = mid - 1;
					else lll = mid + 1, ans = mid;
			}
			qq[now].ans = sum[ans] + get_line(sta[ans + 1], l[sta[ans + 1]], qq[now].x - 1);
			qq[now].ans += (qq[now].x - 1) * (qq[now].x + 1) * qq[now].y;
			qq[now].ans += qq[now].y - 1;//後面兩個是把之前沒有算的貢獻全部加上
			now++;
		}
	}
	
	sort(qq + 1, qq + q + 1, cmp2);
	for (ll i = 1; i <= q; i++) printf("%lld\n", qq[i].ans);
	
	return 0;
}