problem
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)\) 的最小总代价。
solution \(c_2>c_3>c_4>\cdots>c_m\)
大概就是路径形如 \((1, 1)\to(p, 1)\to(p, y)\to(x, y)\)，然后二次函数求个最小值。注意整型溢出。推荐一个 auto safemul = [&](LL x, LL y) { return x && y && bitclz(x) + bitclz(y) < 67 ? (LL)2e18 : x * y; }
solution
有 dp：
\[f(i, j) = \min(f(i - 1, j) + c[j], f(i, j - 1) + i ^ 2) \]有点太简单了。
稍微跳跃一下，受到部分分的启发，我们考虑沿着 \(y\) 增加的方向扫描线，观察 dp 数组 \(f_y(x)\) 的变化：
- 首先全部 \(x\) 会 \(f_y(x)=f_{y-1}(x)+x^2\)。
- 然后逐个 \(x\geq 2\) 进行 \(f_y(x)\) 与 \(f_y(x-1)+c_y\) chkmin 的操作。
- （注意特判 \(x=1\) 和 \(y=1\) 显然可以直接计算。）
因为这个 \(x^2\) 素质很差，但是它的差分 \(x^2-(x-1)^2=2x-1\) 素质还行，考虑对 \(f_y\) 做差分记为 \(g_y(x)=f_y(x)-f_y(x-1)\)（对 \(x=1\) 未定义）。这样，这个没有素质的 \(x^2\) 就变成了 \(g_y(x)=g_{y-1}(x)+2x-1\)，是全局加等差数列。
进一步的我们发现这个 chkmin 的操作是很好做的。不妨假设 \(g_y\) 单调不减，归纳证明：\(x=1\) 是常函数 \(g_1(x)=c_y\)，往后，首先 \(g_y(x)=g_{y-1}(x)+2x-1\)，两个单调不减的函数相加，还是单调不减，然后从前往后考虑每个 \(g_y\)，如果有一个 \(g_y(x)>c_y\)，说明 \(f_y(x-1)+c_y<f_y(x)\)，\(f_y(x)\) 的素质很差，可以取到 \(f_y(x-1)+c_y\)，他今天必须取到这个值，直接把 \(g_y(x)\) 改为 \(c_y\)；这一步 \(g\) 还是单调不减，因为从前往后。完了以后就说明了 \(g_y\) 是单调不减的。实际上 \(f_y\) 是下凸壳，chkmin 操作就是把斜率为 \(c_y\) 的直线切一刀凸壳，并把切掉的部分干掉改直。
于是我们考虑维护 \(g_y\)，操作有：
- 全局加 \(2x-1\)。
- 全局 chkmin \(c_y\)。
- 有性质 \(g_y\) 单调不减。
考虑使用珂朵莉树维护，每一段的 \(g\) 都是等差数列（或者说直线），全局加就是全局记一下，chkmin 就从尾端开始拿出一段和他 chkmin，做一个区间推平的操作。因为只有区间推平，所以复杂度是对的。
考虑询问是查询珂朵莉树上一段前缀的 \(g\) 的总和，使用普通平衡树维护。如果你想要细节就看看代码。
\(O(n\log n)\)。
code
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
typedef long long LL;
struct func {
LL k, b;
func operator+(const func& g) const { return { k + g.k, b + g.b }; }
func& operator+=(const func& g) { return *this = *this + g; }
LL operator()(LL x) { return k * x + b; }
LL getsum(LL l, LL r) {
auto& f = *this;
return (f(l) + f(r)) * (r - l + 1) / 2;
}
};
template <int N>
struct fhqtreap {
func val[N + 10], tag[N + 10];
LL sum[N + 10];
int Ls[N + 10], Rs[N + 10], Lt[N + 10], Rt[N + 10];
// L/R self, L/R subtree
int ch[N + 10][2], tot, pri[N + 10];
mt19937 rng{ random_device{}() };
int newnode(int l, int r, func f) {
int p = ++tot;
pri[p] = rng();
ch[p][0] = ch[p][1] = 0;
Ls[p] = Lt[p] = l;
Rs[p] = Rt[p] = r;
val[p] = f;
sum[p] = f.getsum(l, r);
tag[p] = { 0, 0 };
return p;
}
void maintain(int p) {
sum[p] = sum[ch[p][0]] + sum[ch[p][1]] + val[p].getsum(Ls[p], Rs[p]);
Lt[p] = ch[p][0] ? Lt[ch[p][0]] : Ls[p];
Rt[p] = ch[p][1] ? Rt[ch[p][1]] : Rs[p];
}
void spread(int p, func f) {
if (!p)
return;
val[p] += f, tag[p] += f, sum[p] += f.getsum(Lt[p], Rt[p]);
}
void pushdown(int p) { spread(ch[p][0], tag[p]), spread(ch[p][1], tag[p]), tag[p] = { 0, 0 }; }
// 以 Ls 为关键字进行排序
void split(int p, int v, int& x, int& y) {
if (!p)
return x = y = 0, void();
pushdown(p);
if (Ls[p] <= v)
x = p, split(ch[p][1], v, ch[p][1], y);
else
split(ch[p][0], v, x, ch[p][0]), y = p;
maintain(p);
}
int merge(int p, int q) {
if (!p || !q)
return p + q;
pushdown(p);
pushdown(q);
if (pri[p] < pri[q]) {
ch[p][1] = merge(ch[p][1], q);
maintain(p);
return p;
} else {
ch[q][0] = merge(p, ch[q][0]);
maintain(q);
return q;
}
}
int getLast(int p) {
pushdown(p);
return ch[p][1] ? getLast(ch[p][1]) : p;
}
int root;
void erase(int p) {
int x, y, z;
split(root, Ls[p] - 1, x, y);
split(y, Ls[p], y, z);
assert(y == p);
root = merge(x, z);
}
void insert(int p) {
int x, y;
split(root, Ls[p] - 1, x, y);
root = merge(x, merge(p, y));
}
LL find(int r, int p) {
if (!p)
return 0;
pushdown(p);
if (Rs[p] <= r)
return sum[p] - sum[ch[p][1]] + find(r, ch[p][1]);
else if (r < Ls[p])
return find(r, ch[p][0]);
else
return sum[ch[p][0]] + val[p].getsum(Ls[p], r);
}
void dfs(int p) {
if (!p)
return;
pushdown(p);
dfs(ch[p][0]);
debug("[%d, %d, y = %lldx + %lld], ", Ls[p], Rs[p], val[p].k, val[p].b);
dfs(ch[p][1]);
}
};
int n, m, q;
LL c[200010], ans[4000010];
LL d[200010];
vector<pair<int, int>> qry[200010];
fhqtreap<800010> t;
void ynycoding() {
int& root = t.root = t.newnode(2, n, { 0, c[1] });
// for (int i = 2; i <= n; i++) d[i] = c[1];
for (int y = 2; y <= m; y++) {
// ++d[1]; // d[1] = y - 1
// for (int x = 2; x <= n; x++) d[x] = min(d[x] + 2 * x - 1, c[y]);
t.spread(root, { 2, -1 });
int last = n + 1;
while (int p = t.getLast(root)) {
int l = t.Ls[p], r = t.Rs[p];
auto& f = t.val[p];
if (f(r) <= c[y])
break;
else if (f(l) >= c[y])
t.erase(p), last = t.Ls[p];
else {
int ans = l;
for (int mid = (l + r) >> 1; l <= r; mid = (l + r) >> 1) {
if (f(mid) <= c[y])
ans = mid, l = mid + 1;
else
r = mid - 1;
}
t.erase(p);
t.Rs[p] = ans;
t.insert(p);
last = ans + 1;
break;
}
}
if (last <= n)
t.insert(t.newnode(last, n, { 0, c[y] }));
#ifdef LOCAL
debug("y = %d\n", y);
t.dfs(root);
debug("\n");
#endif
for (auto elem : qry[y]) {
ans[elem.second] += t.find(elem.first, root);
// for (int i = 2; i <= elem.first; i++) ans[elem.second] += d[i];
}
}
}
int main() {
#ifndef LOCAL
freopen("chess.in", "r", stdin);
freopen("chess.out", "w", stdout);
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> c[i];
cin >> q;
for (int i = 1; i <= q; i++) {
int x, y;
cin >> x >> y;
if (x == 1)
ans[i] = y - 1;
else if (y != 1)
qry[y].emplace_back(x, i), ans[i] = y - 1;
else
ans[i] = c[1] * (x - 1);
}
ynycoding();
for (int i = 1; i <= q; i++) cout << ans[i] << endl;
return 0;
}