P9331 [JOISC 2023] 护照 题解

Description

护照是旅行家进入他国时使用的证件。

在一个星球上有 $N$ 个国家，从 $1$ 到 $N$ 编号。每个国家都签发一种护照。当旅行家获得由国家$i \ (1 \le i \le N)$ 签发的护照后，他能够进入国家 $L_i, L_{i + 1}, \dots, R_i$。这里保证旅行家能够进入其签证的签发国。形式上地说, $L_i \le i \le R_i$ 必然成立。

你有一个爱旅行的朋友。即使他奢望能环游世界，但他最初一种护照也没有。因此，他想通过一下重复以下两项行为来环游这 $N$ 个国家。

• 获得他当前所在国家签发的护照。
• 用他现有的护照进入某个国家。

知道他的计划后，你想知道这个计划的是否可行，和如果可行的话，他最少需要的护照数量。因为你并不清楚他现在身处何国，所以你预测了 $Q$ 个他可能正居住在那的国家 $X_1, X_2, \dots, X_Q$。

现在给定各国护照的信息 $L_i, R_i$ 和他可能居住的 $Q$ 个国家，您需要写一个程序，对于每一个可能居住的国家，判断他是否可能环游这 $N$ 个国家，如果可能的话，计算出他需要的最少护照种数。

$2 \le N \le 2 \times 10 ^ 5$，$1 \le L_i \le i \le R_i \le N$。

Solution

首先能到的国家一定是一段区间，如果设当前区间为 $[L,R]$，则每次相当于是选择一个 $i\in [L,R]$，让 $L\leftarrow\min\{L,l_i\},R\leftarrow\max\{R,r_i\}$。

然后有个观察是在当前的 $[L,R]$ 里最多选择两个区间进行拓展，并且拓展后就再也不会选择 $[L,R]$ 内的区间了，否则提前选一定更优。

设 $f_i$ 表示区间为 $[l_i,r_i]$ 的最小答案。

如果当前只选一个区间，则 $f_i\leftarrow f_j+1\ (j\in[l_i,r_i])$。

如果选择两个区间 $[l_x,r_x],[l_y,r_y]$，则一定满足 $l_x\leq l_i,r_y\geq r_i$，此时由于 $[l_i,r_i]$ 不会再选了，那么 $x$ 和 $y$ 一定是一个拓展左端点到 $1$，另一个是拓展右端点到 $n$，否则一个在拓展的过程中一定会拓展到另一个。

这样的话如果求出 $dis1_i$ 表示将 $[l_i,r_i]$ 左端点拓展到 $1$ 的答案，$dis2_i$ 表示将右端点拓展到 $n$ 的答案，就可以让 $f_i\leftarrow dis1_x+dis2_y+1$ 即可。

考虑怎么求出 $dis1_i$ 和 $dis2_i$。下面只考虑求 $dis1_i$。

由于此时只需要单方向拓展，所以只要让 $dis1_i\leftarrow dis1_j+1\ (j\in [l_i,r_i])$ 即可。

两部分都可以用线段树优化建图和 Dijkstra 求。

时间复杂度：$O(n\log^2 n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 2e5 + 5;

int n, q;
int l[kMaxN], r[kMaxN], f[kMaxN], dis1[kMaxN], dis2[kMaxN], idx[kMaxN];
std::vector<std::pair<int, int>> G[kMaxN * 4];

struct SGT {
  int N;
  std::pair<int, int> mx[kMaxN * 4];
  void pushup(int x) { mx[x] = std::max(mx[x << 1], mx[x << 1 | 1]); }
  void build(int n, int *arr, int op = 1) {
    for (N = 1; N <= n + 1; N <<= 1) {}
    for (int i = 1; i <= n; ++i) mx[i + N] = {op * arr[i], i};
    for (int i = N - 1; i; --i) pushup(i);
  }
  std::pair<int, int> query(int l, int r) {
    std::pair<int, int> ret = {-1e9, 0};
    for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (~l & 1) ret = std::max(ret, mx[l ^ 1]);
      if (r & 1) ret = std::max(ret, mx[r ^ 1]);
    }
    return ret;
  }
} sgtl, sgtr;

void build(int x, int l, int r) {
  if (l == r) return void(idx[l] = x);
  int mid = (l + r) >> 1;
  build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  G[x << 1].emplace_back(x, 0), G[x << 1 | 1].emplace_back(x, 0);
}

void update(int x, int l, int r, int ql, int qr, int p) {
  if (l > qr || r < ql) return;
  else if (l >= ql && r <= qr) return void(G[x].emplace_back(idx[p], 1));
  int mid = (l + r) >> 1;
  update(x << 1, l, mid, ql, qr, p), update(x << 1 | 1, mid + 1, r, ql, qr, p);
}

void dijkstra1(int s, int *res) {
  static int dis[kMaxN * 4];
  static bool vis[kMaxN * 4];
  std::fill_n(dis + 1, 4 * n, 1e9);
  std::fill_n(vis + 1, 4 * n, 0);
  std::priority_queue<std::pair<int, int>> q;
  for (int i = 1; i <= n; ++i)
    if (l[i] <= s && s <= r[i])
      dis[idx[i]] = 0, q.emplace(0, idx[i]);
  for (; !q.empty();) {
    int u = q.top().second; q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto [v, w] : G[u]) {
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w, q.emplace(-dis[v], v);
      }
    }
  }
  for (int i = 1; i <= n; ++i) res[i] = dis[idx[i]];
}

void dijkstra2() {
  static int dis[kMaxN * 4];
  static bool vis[kMaxN * 4];
  std::fill_n(dis + 1, 4 * n, 1e9);
  std::fill_n(vis + 1, 4 * n, 0);
  std::priority_queue<std::pair<int, int>> q;
  for (int i = 1; i <= n; ++i) {
    dis[idx[i]] = f[i];
    q.emplace(-dis[idx[i]], idx[i]);
  }
  for (; !q.empty();) {
    int u = q.top().second; q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto [v, w] : G[u]) {
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w, q.emplace(-dis[v], v);
      }
    }
  }
  for (int i = 1; i <= n; ++i) f[i] = dis[idx[i]];
}

void prework() {
  build(1, 1, n);
  for (int i = 1; i <= n; ++i) update(1, 1, n, l[i], r[i], i);
  dijkstra1(1, dis1), dijkstra1(n, dis2);
}

void getf() {
  sgtl.build(n, dis1, -1), sgtr.build(n, dis2, -1);
  for (int i = 1; i <= n; ++i) {
    if (l[i] > 1) f[i] += dis1[sgtl.query(l[i], r[i]).second] + 1;
    if (r[i] < n) f[i] += dis2[sgtr.query(l[i], r[i]).second] + 1;
    // std::cerr << f[i] << " \n"[i == n];
  }
  dijkstra2();
}

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i)
    std::cin >> l[i] >> r[i];
  prework(), getf();
  std::cin >> q;
  for (int i = 1; i <= q; ++i) {
    int x;
    std::cin >> x;
    std::cout << (f[x] > n ? -1 : f[x] + 1) << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}