[AGC061C] First Come First Serve 题解

Description

有 \(n\) 个人来过，第 \(i\) 个人在 \(a_i\) 时刻来在 \(b_i\) 时刻走，每个人可以在来时或走时登记，问可能的登记顺序有多少种。

\(n\leq 5\times 10^5\)，\(a_i,b_i\) 互不相同，\(\forall i<n,a_i<a_{i+1},b_{i}<b_{i+1}\)。

Solution

首先如果每个人随便选，有 \(2^n\) 种方案。但这显然会算重。考虑构造一种方案使得选的方案和最终排列一一对应。

按照排列从小到大的顺序，如果当前 \((a_i,b_i)\) 中有数，则选 \(a_i\)，否则选 \(b_i\)，容易发现这样做一定能够一一对应。

这时一个选择不合法当且仅当对于某个 \(i\)，\((a_i,b_i)\) 中没数但 \(i\) 选了 \(b_i\)，可以对不合法的位置数进行容斥。

具体的，如果选了 \(a_i\) 或 \(b_i\)，则系数为 \(1\)，\((a_i,b_i)\) 中没数且选 \(b_i\)，则系数为 \(-1\)。

容易发现对于任意两个钦定了不合法的位置 \(i,j\)，\([a_i,b_i]\) 和 \([a_j,b_j]\) 一定不相交。并且如果设 \(pre_i\) 表示最大的 \(b_j<a_i\) 的 \(j\)，\(nxt_i\) 表示最小的 \(a_j>b_i\) 的 \(j\)，那么如果 \(i\) 不合法，\((pre_i,i)\) 和 \((i,nxt_i)\) 选择一定是固定的。这样就可以 dp 了。

设 \(f_i\) 表示前 \(i\) 个数的系数之和。那么 \(f_i=2f_{i-1}-\sum_{nxt_j+1=i}{f_{pre_j}}\)。

时间复杂度：\(O(n)\)。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 5e5 + 5, kMod = 998244353;

int n;
int a[kMaxN], b[kMaxN], pre[kMaxN], nxt[kMaxN], f[kMaxN];
std::vector<int> vec[kMaxN];

constexpr int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> a[i] >> b[i];
  for (int i = 1, j = 0; i <= n; ++i) {
    for (; b[j] < a[i]; ++j) {}
    pre[i] = j;
  }
  a[n + 1] = b[n + 1] = 2 * n + 1;
  for (int i = n, j = n + 1; i; --i) {
    for (; a[j] > b[i]; --j) {}
    nxt[i] = j;
  }
  for (int i = 1; i <= n; ++i) vec[nxt[i]].emplace_back(pre[i] - 1);
  f[0] = 1;
  for (int i = 1; i <= n; ++i) {
    f[i] = 2ll * f[i - 1] % kMod;
    for (auto j : vec[i]) dec(f[i], f[j]);
  }
  std::cout << f[n] << '\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;
}