『妙不可言系列4』AtCoder ABC 158F Removing Robots

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

有$N$个机器人分布在数轴上不同的位置，初始为未激活状态，作为上帝，你可以手动激活任意数量的机器人。

当第$i$个机器人被激活时，它会向前走$D_i$个单位长度然后自爆，并且坐标区间在$[X_i,Di)$上的机器人也会被激活往前走，从而触发连锁激活。当你选定一些机器人激活后，最后剩下的机器人按编号组成集合$S$。问一共有多少个不同的集合$S$?

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

首先这是一个DAG模型，一个机器的激活可以引起另一个的激活，这样我们根据某一机器人向能够引起爆炸的另外一个机器人连边便可以得到一张有向无环图。

事实上，有向无环图我们很难建立而且很难在上面完成答案的计算；

因此题解中有一个很妙的思路：

• 将DAG中多余的边去掉，使其变成一个树结构。

我们将多于的边去掉首先需要保证的是不会影响答案的计算。

• 例如(A,B),(B,C),(A,C)这三条边中我们完全可以将(A,C)去掉，因为这两条路径是等价的。
• 因此我们对于每一节点，只需要向离节点最左边位置的节点连边即可。

在程序实现上，我们可以使用优先队列/栈来维护：

• 我们反向考虑，对于没有受到连边的节点放到一个容器使得容器的顶部位置最小。
  （为了能更容易的得到连边）
• 若当前可以向容器的顶部连边，则连边并弹出顶部，直到不能连边为止。

最优我们得到了一个森林结构，我们以每一个根为起点做树形DP。

我们设$f[i]$表示以$i$为根子树的选择方案。

• 当$i$启动是，子树都需要启动，方案为$1$。
• 当$i$不启动时，方案为子树的$f$值得积。
  $$f[x]=1+\prod _{y\in so{n}_x}f[y]$$

最后的答案是森林中每一个根的$f$值之积。

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <bits/stdc++.h>
#define int long longusing namespace std;
const int N = 2e5;
const int P = 998244353;int n;
int vis[N];
vector < int > G[N];
struct node {
    int x, d, id;friend bool operator < (node p1,node p2) {
    return p1.x > p2.x;}
};
node a[N];
priority_queue < node > q;int read(void)
{
    int s = 0, w = 0; char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return w ? -s : s;
}int dp(int x)
{
    int res = 1;for (int i=0;i<G[x].size();++i) {
    int y = G[x][i];res = res * dp(y) % P;}return (res + 1) % P;
}bool PigCute(node p1,node p2) {
    return p1.x > p2.x;
}signed main(void)
{
    n = read();for (int i=1;i<=n;++i) {
    a[i].x = read();a[i].d = read();a[i].id = i;}sort(a+1,a+n+1,PigCute);for (int i=1;i<=n;++i){
    while (q.size() && a[i].x + a[i].d > q.top().x) {
    G[a[i].id].push_back(q.top().id);vis[q.top().id] = 1;q.pop();}q.push(a[i]);}int res = 1;for (int i=1;i<=n;++i)if (vis[i] == 0) res = res * dp(i) % P;cout << res << endl;return 0;
}