P14255 列车（train）

Kingna · 2025-10-19 10:54:36 · 题解

P14255 列车（train）

定义 f_i 表示从 i 开始的列车可以到达的第一个站。那么对于一个修改操作，我们执行对于 i∈[x,y] 执行 f_i\leftarrow \max\{f_i,y+1\}。可以发现 f_i 单调递增且 [f_i,n] 的所有站台均可从 i 到达。

对于一个询问查询从 x\to y 的最小花费，本意是寻找一个包含 [x,y] 区间的列车的最小长度。答案可以描述为 \min\limits _{i=1}^x p_{\max(f_i,y)}-p_{i}。

对于这个式子拆开 \max：

• 对于所有 f_i\leq y 的 i，我们求 p_y-p_i 的最小值，我们找到最后一个 f_i\leq y 的 i 计算答案即可。
• 对于 f_i>y 的 i，我们求 p_{f_i}-p_i 的最小值。因为修改操作是对 f 区间取 \max，不好维护。但是注意到区间取 \max 的本质是对小于 y+1 的那些数区间赋值为 y+1。所以现在转化为了区间赋值操作，若对区间 [l,r] 赋值为 x。则这个区间的最小值则为 p_x-p_r。直接上线段树维护。

复杂度 O(n\log n)。

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define PII pair<int, int>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define _pfor(i, a, b) for (int i = (a); i >= (b); i--)

const int N = 1e5 + 5, INF = 2e18;

int T, n, m, P[N];

struct edge {
  int l, r, minn, mf, lazy;
}tree[N * 4];

void push_up(int p) {
  tree[p].minn = min(tree[p << 1].minn, tree[p << 1 | 1].minn);
  tree[p].mf = min(tree[p << 1].mf, tree[p << 1 | 1].mf);
}

void push_down(int p) {
  if (tree[p].lazy) {
    tree[p << 1].lazy = tree[p].lazy; tree[p << 1].minn = tree[p].lazy;
    tree[p << 1].mf = P[tree[p].lazy] - P[tree[p << 1].r];
    tree[p << 1 | 1].lazy = tree[p].lazy; tree[p << 1 | 1].minn = tree[p].lazy;
    tree[p << 1 | 1].mf = P[tree[p].lazy] - P[tree[p << 1 | 1].r];
    tree[p].lazy = 0;
  }
}

void build(int p, int l, int r) {
  tree[p].minn = l + 1; tree[p].lazy = 0;
  tree[p].l = l, tree[p].r = r;
  if (l == r) {
    tree[p].mf = P[l + 1] - P[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
//  push_up(p);

  tree[p].mf = min(tree[p << 1].mf, tree[p << 1 | 1].mf);
}

void modify(int p, int L, int R, int l, int r, int x) {
  if (l <= L && R <= r) {
    tree[p].lazy = x; tree[p].minn = x;
    tree[p].mf = P[x] - P[tree[p].r];
    return;
  }
  push_down(p);
  int mid = (L + R) >> 1;
  if (l <= mid) modify(p << 1, L, mid, l, r, x);
  if (r > mid) modify(p << 1 | 1, mid + 1, R, l, r, x);
  push_up(p);
}

int query1(int p, int L, int R, int x, int y) {
  if (tree[p].minn > y) return -1;
  if (L == R) return L;
  int mid = (L + R) >> 1;
  push_down(p);
  if (x <= mid) return query1(p << 1, L, mid, x, y);
  int tmp = query1(p << 1 | 1, mid + 1, R, x, y);
  if (tmp == -1) return query1(p << 1, L, mid, x, y);
  return tmp;
}

int query2(int p, int L, int R, int l, int r) {
  if (l <= L && R <= r) return tree[p].mf;
  int mid = (L + R) >> 1, res = INF; push_down(p);
  if (l <= mid) res = min(res, query2(p << 1, L, mid, l, r));
  if (r > mid) res = min(res, query2(p << 1 | 1, mid + 1, R, l, r));
  return res;
}

int read() {
  char c = ' ';
  int f = 1, x = 0;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}

signed main() {
//  freopen("train8.in", "r", stdin);
//  freopen("train8.out", "w", stdout);
  cin >> T;
  while (T--) {
    cin >> n >> m;
    _for(i, 1, n) P[i] = read(); P[n + 1] = INF;
    build(1, 1, n);
    while (m--) {
      int op, x, y;
      op = read(), x = read(), y = read();
      if (op == 1) {
        int p = query1(1, 1, n, n, y + 1);
        if (p >= x) modify(1, 1, n, x, min(p, y), y + 1);
      }
      else {
        int tmp = query1(1, 1, n, x, y), res = INF;
        if (tmp != -1) res = min(res, P[y] - P[tmp]);
        if (max(1ll, tmp + 1) <= x) res = min(res, query2(1, 1, n, max(1ll, tmp + 1), x));
        if (res >= 1e10) puts("-1");
        else cout << res << '\n';
      }
    }
  }
}