14181번: 함수와 쿼리

https://www.acmicpc.net/problem/14181

$O(n\lg n+m(\lg n)^2)$

f(x,y)를 쉽게 생각해보자.
a[y]
a[y] a[y-1]
a[y] a[y-1] a[y-2]
...
a[y] a[y-1] a[y-2] ... a[y-x+2] a[y-x+1]
이런 삼각형 모양의 배열의 맨 위에 포인터 p가 있다하자.
p는 바로 아래 혹은 아래 오른쪽으로 움직인다.
맨 위에서 아래까지 움직일 때 p가 지나간 항들 합의 최소가 f(x,y)이다.

편의상 t=y-x+1, s[i]=a[1]+a[2]+...+a[i]라 하자.
잘 생각해보면 대각선으로만 움직이다 아래로만 내려가는 경로 중에 최적루트가 있다.
이때, 도착지점이 a[i]라 하면 a[i+1...y]>a[i]이다. ... (*)
즉, f(x,y)=min(t<=i<=t)(s[y]-s[i]+a[i]*(i-t+1))
min 안을 정리해서 다시 쓰면
-a[i]*t+(i+1)*a[i]-s[i]+s[y]
(*)에 의해 [t,y]에 있고 -a[i]가 단조 감소인 i에 대해 (기울기, y절편)=(-a[i],(i+1)*a[i]-s[i]) 직선들을 생각할 수 있다.
이들을 이용해 최솟값을 이루는 convex hull을 만들어 x=t인 지점의 함수값을 구하면 f(x,y)를 구할 수 있다.

다수의 쿼리 빠르게 처리하기 위해 세그먼트 트리를 이용한다.
트리의 [l,r] 구간에 해당하는 convex hull을 미리 만들어 놓고 쿼리 (a,b)가 들어오면 이에 해당하는 구간들의 x=a에서 함수값 중 최솟값을 출력한다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
typedef pair<double, double> line;
int n, m, sz[MXN * 4], a[MXN + 1], s[MXN + 1];
vector<line> v[MXN * 4];
vector<double> x[MXN * 4];
double cross(line i, line j) { return (i.second - j.second) / (j.first - i.first); }
void add(int h, int l, int r, int g, line t) {
    if (r < g || g < l) return;
    if (l^r) {
        add(h * 2 + 1, l, (l + r) / 2, g, t);
        add(h * 2 + 2, (l + r) / 2 + 1, r, g, t);
    }
    v[h].resize(r - l + 1);
    x[h].resize(r - l + 1);
    while (sz[h] && v[h][sz[h] - 1].first <= t.first || sz[h] > 1 && cross(v[h][sz[h] - 2], t)>cross(v[h][sz[h] - 1], t)) sz[h]--;
    if (sz[h]) x[h][sz[h] - 1] = cross(v[h][sz[h] - 1], t);
    v[h][sz[h]++] = t;
}
int query(int h, int l, int r, int gl, int gr) {
    if (r < gl || gr < l) return 1e9;
    if (gl <= l&&r <= gr) {
        int p = lower_bound(x[h].begin(), x[h].begin() + sz[h] - 1, gl) - x[h].begin();
        return v[h][p].first*gl + v[h][p].second;
    }
    return min(query(h * 2 + 1, l, (l + r) / 2, gl, gr), query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        s[i] = s[i - 1] + a[i];
        add(0, 1, n, i, { -a[i],(i + 1)*a[i] - s[i] });
    }
    scanf("%d", &m);
    for (int i = 0, u, v; i < m; i++) {
        scanf("%d%d", &u, &v);
        printf("%d\n", query(0, 1, n, v - u + 1, v) + s[v]);
    }
    return 0;
}