自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:50:02，当前版本为作者最后更新于2023-09-10 17:20:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9604 [IOI2023] 超车

如果 $x$ 被 $y$ 堵住了，那么 $x$ 的速度一定大于 $y$：如果 $W_x > W_y$，则存在 $W_z > W_x$ 使得 $y$ 被 $z$ 堵住了，否则 $y$ 不会把 $x$ 堵住。简单地说，如果车辆 $i$ 从 $j - 1$ 到 $j$ 的过程中并非全速行驶（$t_{i, j} > e_{i, j}$），那么存在 $k$ 使得 $k$ 到达 $j - 1$ 的时间严格早于 $i$（$t_{k, j - 1} < t_{i, j - 1}$），且 $k$ 到达 $j$ 的时间严格晚于 $i$（$e_{k, j} > e_{i, j}$），这说明 $k$ 的速度小于 $i$（$W_k > W_i$）。

这说明，在考虑 $i$ 到达每个调度站的时间的时候，速度不小于 $i$ 的车辆不产生影响：如果 $i$ 被堵住，那么 $i$ 所在的 “堵车集团” 一定是被它们当中速度最慢的车堵住的，可以认为 $i$ 被这辆车堵住了，而如果这辆车的速度和 $i$ 相同，那么可以认为 $i$ 是在正常行驶，没有被堵住。因为我们只关心 $N$ 到达调度站的时间，所以先忽略掉所有速度不小于 $N$ 的车，即 $W_i \leq X$ 的所有 $i$。以下设 $W_i > X$。

我们尝试对所有 $0\leq i < N$ 和 $0 \leq j < M$ 求出 $t_{i, j}$。首先有 $t_{i, 0} = T_i$。在 $t_{*, j - 1}\to t_{*, j}$ 时，直接按照题目给出的方式暴力转移的时间复杂度是 $\mathcal{O}(N ^ 2)$，无法接受。按照 $t_{i, j - 1}$ 从小到大枚举 $i$，同时维护所有 $t_{k, j - 1} < t_{i, j - 1}$ 的 $e_{k, j}$ 的最大值即可做到 $\mathcal{O}(N\log N)$。如果 $t_{i, j - 1}$ 相同的 $i$ 按照速度从快到慢枚举，则有先枚举的 $i$ 先到达 $j$ 的性质：后到达 $j - 1$ 的车不会比先到达 $j - 1$ 的车早到达 $j$，而同一时刻到达 $j - 1$ 的车，排在前面的速度更快，更早到达 $j$。在这种枚举顺序下，我们可以认为 $i$ 到达 $j$ 的时间受到的限制是比它先枚举的 $k$ 到达 $j$ 的 实际时间 $t_{k, j}$，而非 期望时间 $e_{k, j}$（因为限制到 $i$ 的 $k$ 一定满足实际时间等于期望时间），也就是令 $t_{i, j} \gets t_{i, j - 1} + W_i(S_j - S_{j - 1})$ 之后，对 $t_{*, j}$ 做 "前缀" $\max$。

$\mathcal{O}(NM)$ 算出 $t_{i, j}$ 之后，我们有 $\mathcal{O}(M\log N)$ 回答单次询问的做法：二分求出 $t_{N, j - 1}$ 在 $t_{*, j - 1}$ 中的位置，可以直接算出 $t_{N, j}$。而 $N$ 的速度大于其它车辆，所以 $N$ 不会对 $t_{i, j}$ 产生任何影响。可以获得 $65$ 分。

为了做到单组询问优于 $\mathcal{O}(M)$，我们尝试预处理所有可能的询问的答案。如果不这样做，对每组询问直接模拟，则无论如何都需要至少 $\mathcal{O}(M)$ 的时间复杂度。

考虑每个 $t_{i, j}$ 的限制：如果 $t_{N, j - 1} > t_{i, j - 1}$，那么 $t_{N, j}$ 对 $t_{i, j}$ 取 $\max$。这样问题就变成了：查询第一个权值大于 $v$ 的位置，全局加法，区间取 $\max$。注意在 $t_{*, j - 1}\to t_{*, j}$ 的过程中，区间 $\max$ 要在查询完所有第一个权值大于某个值的位置之后才能进行。全局加法可以直接打标记，剩下部分可以使用动态开点线段树维护，下标表示出发时间，值表示到达当前调度站的时间。

这个做法不仅难写，而且值域大空间紧。一个常用技巧是：根据单调性，将区间取 $\max$ 变成区间赋值。我们算出赋值的具体情况。不妨设 $i$ 是按照 $0\sim N - 1$ 的顺序枚举的（根据分析，对 $0 < i < N$ 有 $t_{i - 1, j - 1} \leq t_{i, j - 1}$ 且 $t_{i - 1, j} \leq t_{i, j}$），那么对于一段极长的 $t_{i, j}$ 相同的 $i$ 连续段 $[l, r]$：

• 它相当于将 值 区间 $(t_{l, j - 1}, +\infty)$ 对 $t_{l, j}$ 取 $\max$。
• 因为若 $t_{N, j - 1} > t_{l, j} - X(S_j - S_{j - 1})$，那么 $t_{N, j}$ 一定大于 $t_{l, j}$，所以 值 区间缩小为 $(t_{l, j - 1}, t_{l, j} - X(S_j - S_{j - 1})]$。这一步是为了防止原来较大的值被赋小了。
• 因为若 $r < N - 1$ 且 $t_{N, j - 1} > t_{r + 1, j - 1}$，那么 $t_{N, j}$ 会和更大的值取 $\max$，所以 值 区间缩小为 $(t_{l, j - 1}, \min(t_{l, j} - X(S_j - S_{j - 1}), t_{r + 1, j - 1})]$。注意当 $r = N - 1$ 时忽略 $\min$ 的第二项。这一步是为了防止不同的取 $\max$ 操作之间变成赋值之后互相干扰。

最终得到的所有操作的值区间两两无交，可以用维护值区间以及对应下标区间的 set 维护（ODT）。查询时直接二分即可。

时间复杂度 $\mathcal{O}((NM + Q)\log (NM))$。

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

constexpr int MAXN = 1e3 + 5;
constexpr int MAXM = 1e3 + 5;
constexpr ll inf = 2e18;

ll delt, f[MAXN][MAXM];
struct oper {ll l, r, v;};

struct itv {
  ll l, r, _l, _r;
  bool operator < (const itv &z) const {
    if(l != z.l) return l < z.l;
    if(r != z.r) return r < z.r;
    return _l < z._l;
  }
};
set<itv> s;
vector<itv> res;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
  for(int i = 0; i < N; i++) {
    if(W[i] <= X) {
      W.erase(W.begin() + i);
      T.erase(T.begin() + i);
      N--, i--;
    }
  }
  for(int i = 0; i < N; i++) f[i][0] = T[i];
  s.insert({-inf, inf, -inf, inf});
  for(int t = 1; t < M; t++) {
    vector<int> id(N);
    for(int i = 0; i < N; i++) id[i] = i;
    sort(id.begin(), id.end(), [&](int x, int y) {
      if(f[x][t - 1] != f[y][t - 1]) return f[x][t - 1] < f[y][t - 1];
      return W[x] < W[y];
    });
    ll d = S[t] - S[t - 1];
    for(int i = 0; i < N; i++) {
      f[id[i]][t] = f[id[i]][t - 1] + W[id[i]] * d;
      if(i) f[id[i]][t] = max(f[id[i]][t], f[id[i - 1]][t]);
    }
    auto split = [&](ll p) {
      auto pt = --s.lower_bound({p + 1, -inf});
      if(pt->l == p || pt->r < p) return;
      s.insert({pt->l, p - 1, pt->l, p - 1});
      s.insert({p, pt->r, p, pt->r});
      s.erase(pt);
    };
    ll nxt = delt + X * d;
    vector<itv> add;
    for(int i = 0; i < N; ) {
      int j = i;
      while(j < N && f[id[j]][t] == f[id[i]][t]) j++;
      if(W[i] > X) {
        ll st = f[id[i]][t - 1] + 1 - delt;
        ll ed = min(f[id[i]][t] - X * d, j < N ? f[id[j]][t - 1] : inf) - delt;
        ll p = f[id[i]][t] - nxt;
        ll L = -inf, R = -1;
        split(st), split(ed + 1);
        while(1) {
          auto pt = s.lower_bound({st, -inf});
          if(pt == s.end() || pt->l > ed) break;
          if(L == -inf) L = pt->_l;
          R = pt->_r;
          s.erase(pt);
        }
        if(L != -inf) add.push_back({p, p, L, R});
      }
      i = j;
    }
    for(itv it : add) s.insert(it);
    delt = nxt;
  }
  for(itv it : s) res.push_back(it);
}

ll arrival_time(ll Y) {
  int l = 0, r = res.size() - 1;
  while(l < r) {
    int m = l + r + 2 >> 1;
    if(res[m]._l <= Y) l = m;
    else r = m - 1;
  }
  if(res[l].l < res[l].r) return Y + delt;
  return res[l].l + delt;
}