题解：P14255 列车（train）

Eric998 · 2025-10-19 12:02:59 · 题解

设 las_i 为 i 一趟车能到的最近的点。观察到任意时刻 las_i 单调增，区间 \operatorname{chkmax} 就是区间赋值。维护简单。

考虑答案到底是什么。发现我们要么走到 r，要么走到 (r,n]。对于第一类，线段树二分出最右一个能到 r 的点即可。对于第二类，需要维护区间 p_{las_i}-p_i 的最小值，第二类的答案就是从最左一个不能到 r 的位置到 l 这段区间里 p_{las_i}-p_i 的最小值。

code:

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int L[N << 2], R[N << 2], tag[N << 2], mx[N << 2], mn[N << 2], P[N], n, q, pre, T;

inline void cov(int u, int v) {
    tag[u] = mx[u] = v, mn[u] = P[v] - P[R[u]];
}

inline void down(int u) {
    if (~tag[u])
        if (L[u]^R[u])
            cov(u * 2, tag[u]), cov(u * 2 + 1, tag[u]), tag[u] = -1;
}

inline void up(int u) {
    if (L[u]^R[u])
        mx[u] = max(mx[u * 2], mx[u * 2 + 1]), mn[u] = min(mn[u * 2], mn[u * 2 + 1]);
}

void build(int l, int r, int p) {
    L[p] = l, R[p] = r, tag[p] = -1, mx[p] = r + 1;
    int m = (l + r) / 2;
    if (l ^ r)
        build(l, m, p * 2), build(m + 1, r, p * 2 + 1), up(p);
    else
        mn[p] = P[r + 1] - P[l];
}

void modi(int l, int r, int p, int v) {
    if (l <= L[p] && r >= R[p])
        return cov(p, v);
    if (l > R[p] || r < L[p])
        return;
    down(p), modi(l, r, p * 2, v), modi(l, r, p * 2 + 1, v), up(p);
}

int que(int p, int v) {
    if (L[p] == R[p])
        return L[p];
    down(p);
    if (mx[p * 2] > v)
        return que(p * 2, v);
    else
        return que(p * 2 + 1, v);
}

int qmn(int l, int r, int p) {
    if (l <= L[p] && r >= R[p])
        return mn[p];
    if (l > R[p] || r < L[p])
        return 0x3f3f3f3f;
    down(p);
    return min(qmn(l, r, p * 2), qmn(l, r, p * 2 + 1));
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> P[i];
    P[n + 1] = 0x7f7f7f7f, build(1, n + 1, 1), pre = 1;
    while (q--) {
        int op, l, r, p;
        cin >> op >> l >> r;
        if (op == 1) {
            p = que(1, r);
            if (p > l)
                modi(l, p - 1, 1, r + 1);
            if (l == 1 && r == n)
                pre = 0;
        } else {
            if (!pre) {
                cout << "-1\n";
                continue;
            }
            p = que(1, r);
            int res = 0x3f3f3f3f;
            if (p ^ 1)
                res = P[r] - P[min(p - 1, l)]; //to r
            if (p <= l)
                res = min(res, qmn(p, l, 1)); //further
            cout << res << '\n';
        }
    }
}

main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
        solve();
}