题意

题目链接。

题意有点复杂，大意是有一个猎杀游戏，有 $m$ 名玩家，每名玩家初始有 $3$ 点生命。有 $n$ 个时刻，每个时刻会发生形如 $u_i$ 杀 $v_i$ 的事件，若 $u_i$ 和 $v_i$ 都存活，则 $v_i$ 生命值减 $1$，若生命值为 $0$ 则死亡。现在发生了一次特殊事件：穿越者穿越到某一次追杀后（可以是第 $0$ 次也可以是最后一次）对某一名玩家造成一点伤害。求对于每一个 $x \in[0,m]$，有多少种穿越方案使最后有 $x$ 名玩家活着。

解析

记穿越者编号为 $0$。我们发现一件事情，对于一个事件 $(u_i,v_i)$，若 $x$ 不为 $u_i$ ,在它之前插入 $(0,x)$ 和在它之后插入 $(0,x)$ 是等价的。证明：若 $x$ 为 $v_i$ 相当于依次攻击 $v_i$，是谁攻击的是没有区别的，因此与 $(0,x)$ 的位置前后无关；若 $x$ 不为 $u_i$ 且不为 $v_i$，则该事件与 $u_i,v_i$ 均无关，显然也是等价的。

因此，我们考虑在每一个事件前尝试插入 $(0,u_i)$，容易发现每一次插入后模拟进程的复杂度是 $O(n)$。再考虑一个显然的优化：如果 $u_i$ 或 $v_i$ 已死亡，则不用尝试。我们称 $u_i$ 和 $v_i$ 均未死亡发生的事件为有效事件，则至多进行 $3m-1$ 个有效事件（最后只剩一个人活着且只有 $1$ 滴血）。因此最终时间复杂度为 $O(mn)$。

接着考虑统计答案，我们可以用 $now$ 数组记录每一个玩家当前已统计到的位置，然后每次插入后，更新 $now_x$（$x$ 为尝试攻击的玩家），并将对应的答案加上 $p-now_x $（$p$ 为插入位置）。最后再在所有操作结束之后尝试攻击每一个人，并将对应的答案加上 $n+1-now_x$。因为除了插入位置以外，其他位置都等价于在其下一个位置插入，所以对应答案可以直接用当前位置减去上一个插入的位置（即 $now_x$）。详见代码，配有注释。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=6e4+5;
int n,m,v[N],u[N],a[N],ans[N],b[N],now[N];
inline void attack(int p,int x){
    for(int i=1;i<=m;i++) b[i]=a[i];
    b[x]--;//插入的攻击
    for(int i=p;i<=n;i++) if(b[u[i]]&&b[v[i]]) b[v[i]]--;//简单的模拟
    int t=0;
    for(int i=1;i<=m;i++) if(b[i]) t++;//统计存活人数
    ans[t]+=(p-now[x]);now[x]=p;//更新对应答案和 now[x]
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&u[i],&v[i]);
    for(int i=1;i<=m;i++) a[i]=3;//初始生命值
    for(int i=1;i<=n;i++){
        if(a[u[i]]&&a[v[i]]){//如果是有效攻击
            attack(i,u[i]);//尝试插入
            a[v[i]]--;//血量减 1
        }
    }
    int t=0;
    for(int i=1;i<=m;i++) if(a[i]) t++;
    for(int i=1;i<=m;i++){//最后再尝试攻击每一个人
        if(a[i]==1) ans[t-1]+=n+1-now[i];
        else ans[t]+=n+1-now[i];
    }//至此，所有可能的情况都被统计完了
    for(int i=0;i<=m;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}