自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:30:32，当前版本为作者最后更新于2021-03-24 19:37:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解

先考虑一个简化的问题：

$k$ 个人，每个人距离 $t$ 的最近距离为 $dist_i$ 。然后我们要让他们到达神社。

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

想法

思路一

考虑让所有人同时沿着最短路向神社走去。可能发生的最糟糕的情况是，两个人挤占了同一个点，但是我们不知道他们什么时候相撞。但是事实上我们根本不需要考虑相撞的地点。只要假想一个时间轴，我们现在将第 $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;
}