StormWind
时间：4s 空间：512M
题目描述：
风暴城建造的防线错综复杂，可以抽象成一个有$n$个点$m$条边的有向拓扑图，暴风城的最长防线定义为以任意一个点开始能走的最长路径的边数。
由于部落的进攻有所侧重，所以安度因每天会临时下一些命令来调整防线。
第一种 $ty = 1$ $x$点不能被经过。
第二种 $ty = 2$ 必须经过$x$点。
第三种 $ty = 3$ 必须经过输入顺序的第$x$条边。
每一天的调整不会影响到下一天。
求每一天下完命令之后的最长防线。
输入格式：
第一行三个数$n$,$m$,$k$. 分别表示点数、边数、天数。
以后$m$行每行数$x$，表示$x ->y$ 有一条边。以后k行每行两个数$ty,x$;
输出格式：
对于每个询问 输出一行表示其结果
样例输入：
6 5 3
1 2
1 3
1 4
1 5
2 3
1 2
3 1
2 5
样例输出：
1
2
1
数据范围:
对于$20\%$的数据
$n,m,k<=5000$
另有$20\%$的数据
保证 对于 $1<=i<n$, $i$ 与 $i + 1$ 之间有边。
另有$10\%$的数据 没有操作$1$、$2$
对于$100\%$的数据
$n,m,k<=2e5$
拓扑排序
首先先加一个超级源点和超级汇点，可以发现最长路径一定会从超级源点出发，或者结束于超级汇点
首先考虑第二个和第三个操作，要处理出来从源点出发到这个点的最长路$ds[i]$，和从这个点到汇点的最长路$dt[i]$，这个可以通过拓扑序DP更新
对于第二个操作，那么要强制经过这个点，那么答案就是$ds[i]+dt[i]$
对于第三个操作，那么要强制经过边两端的端点，那么答案就是$ds[u]+dt[v]+1$
主要是难以对第一个操作进行处理，考虑钦定某一个点不能经过，最长路径的贡献来自三个部分，这个点“左边”（拓扑序小于这个点的拓扑序）的点，可以贡献从源点到这些点最长的路径；在这个点“右边”（拓扑序大于这个点的拓扑序）的点，可以贡献从这点到汇点最长的路径；还有就是“左边”连到“右边” 的点，贡献就是$ds[i]+dt[j]+1$
考虑如何计算对于每一个点的贡献
从左边推到右边，枚举到第i个点时，要去除$ds[i]$的贡献和连向这个点的边的贡献，就是$ds[j]+1+dt[i]$（存在$j->i$的边），然后加上$dt[i]$的贡献
这个可以用set来维护
#include <bits/stdc++.h> using namespace std; const int N=2*1e5+100; int n,m,k,ds[N],dt[N],s,t,dg[N]; int dout[N],din[N],vi[N],a[N],w; int ans[N],premax[N],sucmax[N],id[N]; queue <int> q; multiset <int> S; multiset <int> :: iterator it; struct node { int u,v; }sh[N]; vector <int> e[N],E[N],p; void get() { for (int i=1;i<=n;i++) { for (int j=0;j<(int)E[i].size();j++) dg[E[i][j]]++; } for (int i=1;i<=n;i++) { if (dg[i]==0) { q.push(i); vi[i]=1; } } while (!q.empty()) { int x=q.front(); q.pop(); a[++w]=x; for (int i=0;i<(int)E[x].size();i++) { int u=E[x][i]; if (vi[u]) continue; dg[u]--; if (dg[u]==0) q.push(u),vi[u]=1; } } dt[t]=0; for (int i=1;i<=n;i++) { int x=a[i]; for (int j=0;j<(int)E[x].size();j++) { int u=E[x][j]; dt[u]=max(dt[u],dt[x]+1); } } memset(dg,0,sizeof(dg)); memset(vi,0,sizeof(vi)); for (int i=1;i<=n;i++) { for (int j=0;j<(int)e[i].size();j++) dg[e[i][j]]++; } for (int i=1;i<=n;i++) { if (dg[i]==0) { q.push(i); vi[i]=1; } } w=0; while (!q.empty()) { int x=q.front(); q.pop(); a[++w]=x; for (int i=0;i<(int)e[x].size();i++) { int u=e[x][i]; if (vi[u]) continue; dg[u]--; if (dg[u]==0) q.push(u),vi[u]=1; } } ds[s]=0; for (int i=1;i<=n;i++) { int x=a[i]; for (int j=0;j<(int)e[x].size();j++) { int u=e[x][j]; ds[u]=max(ds[u],ds[x]+1); } } for (int i=1;i<=n;i++) id[a[i]]=i; for (int i=1;i<=n;i++) premax[i]=max(premax[i],ds[a[i]]); for (int i=n;i>=1;i--) sucmax[i]=max(sucmax[i+1],dt[a[i]]); } inline void del(int x) { it=S.lower_bound(x); S.erase(it); } int main() { scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=m;i++) { scanf("%d%d",&sh[i].u,&sh[i].v); dout[sh[i].u]++;din[sh[i].v]++; e[sh[i].u].push_back(sh[i].v); E[sh[i].v].push_back(sh[i].u); } s=n+1;t=n+2; for (int i=1;i<=n;i++) { if (din[i]==0) e[s].push_back(i),E[i].push_back(s); if (dout[i]==0) e[i].push_back(t),E[t].push_back(i); } n+=2; get(); for (int i=1;i<=n;i++) { for (int j=0;j<(int)E[a[i]].size();j++) { int u=E[a[i]][j]; del(ds[u]+dt[a[i]]+1); } if (!S.empty())it=S.end(),it--,ans[a[i]]=(*it)-2; ans[a[i]]=max(ans[a[i]],premax[i-1]-1); ans[a[i]]=max(ans[a[i]],sucmax[i+1]-1); for (int j=0;j<(int)e[a[i]].size();j++) { int u=e[a[i]][j]; S.insert(ds[a[i]]+dt[u]+1); } } while (k--) { int ty,x; scanf("%d%d",&ty,&x); if (ty==1) printf("%d ",ans[x]); if (ty==2) printf("%d ",ds[x]+dt[x]-2); if (ty==3) printf("%d ",ds[sh[x].u]+dt[sh[x].v]-1); } }