题解 【SR2.5-T4】【第二次月面战争】

· · 题解

题解

先考虑一个简化的问题：

其实这玩意有两种思路，貌似都是对的（

想法

思路一

考虑让所有人同时沿着最短路向神社走去。可能发生的最糟糕的情况是，两个人挤占了同一个点，但是我们不知道他们什么时候相撞。但是事实上我们根本不需要考虑相撞的地点。只要假想一个时间轴，我们现在将第 i 个人插入到 dist_i 位置。如果已经被占用了，那就向后插入到第一个没有被插入的位置。最后一个被占用的位置所在的点就是答案。

至于为什么正确，感性理解吧。一个人 i 会停留在原地，当且仅当他要到达的下一个点被占用了。他后面可能有个人 j 也要到达 i 所在的位置，这样的前提是他的最短路和 \boldsymbol{i} 重叠。 j 可不可以绕路呢？事实上是不行的，因为 i 排队的原因是 i 要走的路被占掉了， j 试图包抄也会被阻挡。如果 j 能先于 i 到达被占用的节点，那就与 j 走的是最短路相不符，所以无论如何 j 都会被阻塞。

思路二

刚刚那个思路是屑波（@离散小波变换° ）想出来的，可谓是非常难以理解（）下面的思路是 \text{chenxinyang2006} 提供的。

考虑按照 dist_i 的大小，从大到小决定每个人。我们将“每个人走到神社”转换为“神社里的人走到相应的位置”。 dist 大的人显然不会阻拦 dist 小的人，如果 dist 相同，那就按照顺序出来。于是第 i 个人花费的时间应该是 dist_i+rank_i ，其中 rank_i 表示 dist_j 不小于 i 的 j 有多少个。显然这样是正确的（

事实上，出题人写了两个程序的暴力代码并且进行了一些对拍，并没有拍出不同的数据点。可以验证这两种思路都是对的。下面考虑如何实现。

求解

两种做法都可以用 \mathcal O(n\log n) 的时间复杂度实现。我们关心的是如何动态维护两个东西。

思路一

我们需要动态插入/删除一个人，并且找到最靠后的那个人。一种可行的做法是，维护一个数列 \{P_i\} ，其中 P_i 表示，在时间轴上仅考虑前 i 个点，从第 i 个位置起，还需要排多少个人才可以将积攒的人全部排完；如果当前第 i 个位置没有人，那就令 P_i=-1 （定义有点复杂……）考虑去维护。

插入一个人 i ，他的位置为 dist_i ，那么我们就要找到第一个空闲的位置（即，第一个满足 P_{j}=-1,j\ge dist_i 的那个 j） x ，然后让 P_{j}\gets P_{j}+1 (j=dist_i,dist_i+1,\cdots x) 。删除一个人 i ，我们就要找到他影响到的所有的 P_j ，然后令 P_{j}\gets P_j-1 。可以发现，这样的 j 就是满足 P_{j}=0,j\ge dist_i 的第一个 j 。

考虑如何去快速查询、快速区间修改。我们用一棵线段树维护 \{P_i\} ，每个节点存储该区间的最小值 ，以及用于区间加减的 \text{tag} 。食用方法和普通线段树差不多，只要维护就完事了。关键是查询。我们要查询 [dist_i,+\infty) 里第一个 0 和 -1 ，考虑线段树上二分。假设我们要求 [x,+\infty) 第一个 k ，目前在线段树上节点 p ，那就看它左侧的节点的最小值是否不超过 k ；如果是，就查询左节点，否则查询右节点。（因为本题的特殊性质， 0 必定在 -1 前面，所以维护最小值是正确的。）顺便完成区间修改就行了。

复杂度是 \mathcal O(q\log n) 的。

思路二

为了方便操作，我们使用值域线段树，用来维护每个 dist 的贡献 Q_i 。（其实也可以维护每个人的贡献，而这是 \rm cxy 代码的做法。这里仅讨论前者）初始时线段树上每个节点权值设为 0 ，当插入第 i 个人时，设 d=dist_i ，我们需要判断之前有没有点在 d ，如果没有，那就要对应的点的权值加上 d （根据贡献的计算式子），即 Q_d\gets Q_d+d 。以及他前面所有 dist 的贡献都要加上 1 ；删除第 i 个人，那就要判断删除后是否还存在点在 d ，如果是，那也要令 Q_d\gets Q_d-d 。同时让它前面的 dist 的贡献都减去 1 。每次操作完，查询全局最大值作为答案就行了。

具体操作非常简单，就不细讲了（

顺带一提， 10^5 的测试点是留给奇妙的 \mathcal O(q\log^2 n) 做法的。尽管我不大清楚是否真的有这样的算法（

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long LL;
const int INF =2147483647;
const int SIZ =1e6;
char buf[SIZ],*p1,*p2;
char readc(){
    if(p1==p2) p1=buf,p2=buf+fread(buf,1,SIZ,stdin);
    return *p1++;
}
int qread(){
    int w=1,c,r=0;
    while((c=readc())> '9'||c< '0') w=(c=='-'?-1:1); r=c-'0';
    while((c=readc())>='0'&&c<='9') r=r*10+c-'0';
    return r*w;
}
const int MAXN =1.05e6+3,MAXM=1.2e6+3;
namespace Gra{
    int H[MAXN],V[MAXM],N[MAXM],t,D[MAXN]; bool F[MAXN];
    void add(int u,int v){V[++t]=v,N[t]=H[u],H[u]=t;} 
    queue <int> Q;
    void bfs(int u){
        Q.push(u); while(!Q.empty()){
            int a=Q.front(); Q.pop(); for(int i=H[a],b;i;i=N[i]){
                if(!F[b=V[i]]) F[b]=true,Q.push(b),D[b]=D[a]+1;
            }
        }
    }
}
int n,l,m,q,t,C[MAXN];
namespace Seg{
    unsigned int W[MAXN*2],T[MAXN*2],M[MAXN*2],F[MAXN],w,t;
    inline void inc(unsigned int p){
        if(!F[p]) M[p|n]+=p; ++F[p],p|=n; ++M[p];
        up(1,l,i){
            if(p&1) ++T[p^1],++M[p^1]; M[p>>1]=max(M[p],M[p^1])+T[p>>1]; p>>=1;
        }
    }
    inline void dec(unsigned int p){
        --F[p];if(!F[p]) M[p|n]-=p; p|=n; --M[p];
        up(1,l,i){
            if(p&1) --T[p^1],--M[p^1]; M[p>>1]=max(M[p],M[p^1])+T[p>>1]; p>>=1;
        }
    }
}
bool O[MAXN];
int main(){
    n=qread(),m=qread(),q=qread(),t=qread();
    for(l=1;(1<<l)<=n;++l); n=1<<l;
    up(1,m,i){int u=qread(),v=qread();Gra::add(v,u);}
    Gra::D[t]=1,Gra::F[t]=true,Gra::bfs(t);
    up(1,q,i){
        int x=qread(); O[x]?Seg::dec(Gra::D[x]):Seg::inc(Gra::D[x]);
        O[x]^=1,printf("%d\n",Seg::M[1]-1);
    }
    return 0;
}