题解：AT_arc073_d [ARC073F] Many Moves

happy_zero · 2024-08-29 14:58:23 · 题解

下文记 pos_i=x_i。

首先有 O(mV) 的 dp：f_{i,j} 表示第 i 次操作，一个棋子在 pos_i，另一个在 j 的最小操作，转移：

对应的分别是：将上一次在 pos_{i-1}/j 的棋子移到 pos_{i}。

初始化：f_{1,a}=|pos_1-b|,f_{1,b}=|pos_1-a|。

把 i 这维压掉，记 g=f_{i-1} 辅助转移：

发现第一个对应着全局加，打个全局 tag 即可（第二种转移记得减去 |pos_i-pos_{i-1}| 抵消）；

第二个对应着全局 \max 和单点修改，但由于有一个绝对值，拆开，就是要查询 \min_{1\le j\le pos_i}\{g_j-j\} 和 \min_{pos_i<j\le n}\{g_j+j\}。于是用线段树维护 f_j,f_j+j 和 f_j-j 即可。

复杂度 O(Q\log n)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
const int INF = 1e12;
int a, b, t[N << 2], t1[N << 2], t2[N << 2], pos[N];
void pushup(int k) {
    t[k] = min(t[k << 1], t[k << 1 | 1]);
    t1[k] = min(t1[k << 1], t1[k << 1 | 1]);
    t2[k] = min(t2[k << 1], t2[k << 1 | 1]);
}
void build(int k, int l, int r) {
    if (l == r) {
        if (l == a) t[k] = abs(pos[1] - b), t1[k] = t[k] + a, t2[k] = t[k] - a;
        else if (l == b) t[k] = abs(pos[1] - a), t1[k] = t[k] + b, t2[k] = t[k] - b;
        else t[k] = t1[k] = t2[k] = INF;
        return;
    }
    int m = l + r >> 1;
    build(k << 1, l, m);
    build(k << 1 | 1, m + 1, r);
    pushup(k);
}
void updata(int k, int l, int r, int x, int v, int v1, int v2) {
    if (l == r) return t[k] = min(t[k], v), t1[k] = min(t1[k], v1), t2[k] = min(t2[k], v2), void();
    int m = l + r >> 1;
    if (x <= m) updata(k << 1, l, m, x, v, v1, v2);
    else updata(k << 1 | 1, m + 1, r, x, v, v1, v2);
    pushup(k);
}
int query(int k, int l, int r, int L, int R, int op) {
    if (L <= l && r <= R) return (op == 1 ? t1[k] : (op == 2 ? t2[k] : t[k]));
    int m = l + r >> 1, res = INF;
    if (L <= m) res = query(k << 1, l, m, L, R, op);
    if (R > m) res = min(res, query(k << 1 | 1, m + 1, r, L, R, op));
    return res;
}
signed main() {
    int V, m; cin >> V >> m >> a >> b;
    for (int i = 1; i <= m; i++) 
        cin >> pos[i];
    build(1, 1, V); int lazy = 0;
    for (int i = 2; i <= m; i++) {
        lazy += abs(pos[i] - pos[i - 1]);
        int w1 = query(1, 1, V, 1, pos[i], 2) + pos[i];
        int w2 = query(1, 1, V, pos[i], V, 1) - pos[i];
        int w = min(w1, w2) - abs(pos[i] - pos[i - 1]);
        updata(1, 1, V, pos[i - 1], w, w + pos[i - 1], w - pos[i - 1]);
    }
    cout << query(1, 1, V, 1, V, 0) + lazy;
    //最后别忘了加上全局 tag 
    return 0;
}