简略题意：给出n个数 a[i] ，回答 m 次询问(xi,yi)，每次回答 f(xi,yi) 是多少。 ∗f(1,j)=a[j],1≤j≤n. ∗f(i,j)=min(f(i−1,j),f(i−1,j−1))+a[j],2≤i≤n,i≤j≤n.
考虑暴力，对于一个询问 (i,j) , 必然会递归到底层的某个位置，设为 (1,s) ，则 a[s] 必然是 [s,j] 区间的最小值，且被选择的次数最多。 *简略证明：如果存在某个 t 满足t<s,a[t]>a[s]，则这样得到的值必然大于在 s 处的值。并且对于能到达同样结尾的值，选择小值次数多的必然更小。
那么假定我们已知(1,s),想求f(x, y)，则答案为 ans=sum[y]−sum[s]+(x−(y−s))∗a[s] . 转化一下形式得 ans−sum[y]=(x−y)∗a[s]+s∗a[s]−sum[s] ，会发现这是一个形如 y=kx+b的形式 ， a[s],s∗a[s]−sum[s] 都是可以预处理的定值，那么给出一组 (x,y) ，相当于已知 x ,给出若干条线段，求最大的y。
我们就把问题转化成了Convex hull trick可以处理的问题。
线段树存Cht, 每个区间拆开单独询问即可, 复杂度 O(nlognlogn) 。
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() using namespace std; typedef long long LL; const int maxn = 110000; int n; struct line { LL k, b; LL getval(LL x) { return k * x + b; } bool operator < (const line & rhs) const { return k > rhs.k || (k == rhs.k && b < rhs.b); } } ll[maxn]; LL a[maxn], sum[maxn]; double pos(line a, line b) { return 1.0*(b.b-a.b)/(a.k-b.k); } LL ans, px; struct A { vector<line> V; void getx(LL x) { LL L = 0, R = V.size() - 1, M; while(L < R) { M = (L + R) >> 1; M++; if(pos(V[M-1], V[M]) > px) R = M - 1; else L = M; } ans = min(ans, V[L].getval(px)); } void show() { for(int i = 0; i < V.size(); i++) cout<<V[i].k<<" "<<V[i].b<<endl; } } tr[maxn<<2]; void build(int l, int r, int rt) { vector<line> ss; for(int i = l; i <= r; i++) ss.push_back(ll[i]); sort(all(ss)); auto &buf = tr[rt].V; buf.push_back(ss[0]); for(int i = 1; i < ss.size(); i++) { if(ss[i].k < ss[i-1].k) { while(buf.size() >= 2 && pos(buf[buf.size()-2], buf[buf.size()-1]) >= pos(buf[buf.size()-2], ss[i])) buf.pop_back(); buf.push_back(ss[i]); } } if(l == r) return ; int m = (l + r) >> 1; build(l, m, rt<<1); build(m+1, r, rt<<1|1); } void ask(int L, int R, int l, int r, int rt) { if(L <= l && R >= r) { tr[rt].getx(px); return ; } int m = (l + r) >> 1; if(L <= m) ask(L, R, l, m, rt<<1); if(R > m) ask(L, R, m+1, r, rt<<1|1); } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%lld", &a[i]), sum[i] = sum[i-1] + a[i], ll[i].k = a[i], ll[i].b = i*a[i]-sum[i]; build(1, n, 1); int q; scanf("%d", &q); while(q--) { LL x, y; scanf("%lld%lld", &x, &y); ans = 1e18, px = x - y; ask(y-x+1, y, 1, n, 1); printf("%lld\n", ans + sum[y]); } return 0; }