题解：P11456 [USACO24DEC] Interstellar Intervals G

lalaouye · 2024-12-24 11:55:29 · 题解

首先这道题肯定可以设 f_i 表示前 i 位的答案，转移就是枚举一段红加一段蓝，并 check 能否转移，这样可以简单做到 \mathcal{O}(n^2)。而对于转移怎么 check 呢？首先红色点对于无解的影响是好处理的，问题是蓝点怎么处理。我们考虑对于所有蓝点独立处理不能转移的段，那么不能转移的段即为所有蓝点不能处理的段的并。

我们注意到 i 每往后一次，每个蓝点的影响就会往前扩展一位。那么这个东西显然可以均摊处理，我们维护所有不合法段的左端点，如果左端点到了已经不合法的点就删除这个左端点，因为它没有存在的必要。然后用树状数组维护所有 f_j 的贡献，每扩展到一位就减去这一位的 dp 值即可。

时间复杂度 \mathcal{O}(n\log n)，\log n 来自于树状数组，感觉 n 开到 5\times 10^6 不是问题！

代码：

class BIT {
  public:
    int c[N];
    int lb (int x) {
      return x & -x;
    }
    void upd (int x, int y) {
      ++ x;
      for (; x <= n; x += lb (x)) c[x] += y;
    }
    int qry (int x) {
      int ret = 0; ++ x;
      for (; x; x -= lb (x)) ret += c[x];
      return ret;
    }
    int qry (int l, int r) { return qry (r) - qry (l - 1); }
} t[2];
void insert (int x) {
  nxt[pre[n + 1]] = x;
  pre[x] = pre[n + 1];
  pre[n + 1] = x;
  nxt[x] = n + 1;
}
void erase (int x) {
  pre[nxt[x]] = pre[x];
  nxt[pre[x]] = nxt[x];
}
int32_t main () {
  n = rd ();
  nxt[0] = n + 1, pre[n + 1] = 0;
  scanf ("%s", s + 1);
  int l1 = 0;
  f[0] = 1;
  t[0].upd (0, 1);
  rep (i, 1, n) {
    for (int x = nxt[0]; x <= n; x = nxt[x]) {
      del[now[x]] = 1;
      t[now[x] & 1].upd (now[x], - f[now[x] - 1]);
    }
    for (int x = nxt[0]; x <= n; x = nxt[x]) {
      if (del[-- now[x]] || now[x] < 1) erase (x);
    }
    if (s[i] == 'R') l1 = i;
    else if (s[i] == 'B' && ! del[i]) {
      insert (i), now[i] = i;
    }
    f[i] = t[i & 1 ^ 1].qry (max (1ll, l1 * 2 - i + 1), i) % P;
    if (s[i] == 'X') f[i] = (f[i] + f[i - 1]) % P;
    t[i & 1].upd (i, f[i - 1]);
  }
  cout << (f[n] + P) % P;
}