【CF1580E】Railway Construction 题解

题目大意

  给定一幅 $n$ 个点 $m$ 条边的带权无向图（权值表示距离），现在想要加一些单向边，权值自定（需是正整数），使得：

• 从 $1$ 号点到每个点的最短路长度不变；
• 从 $1$ 号点到每个点都有至少两条点不相交的最短路径。

  新建一条从 $u$ 号点出发的单向边代价为 $w_u$。求最小代价。
  以及有 $q$ 次修改操作，每次选择一个点 $k$ 把 $w_k$ 增加 $x$。

  $n \le 2 \times 10^5,\ m \le 3 \times 10^5,\ q \le 2 \times 10^5$
  $1 \le w_i \le 10^9$，初始边权 $d$ 满足 $1 \le d \le 10^9$，每次操作增加的代价 $x_i$ 满足 $1 \le x_i \le 4 \times 10^8$。
  2.5s

$$\\$$ $$\\$$ $$\\$$

题解

  中国特色数据结构题

  首先考虑无修改怎么做。这种情况的推导是自然流畅的：
  原始图做了最短路之后可以得到一幅最短路图（只保留最短路边的 DAG），后面就都在这个最短路图上讨论了。稍加观察可以发现，如果一个点的入度至少为 $2$，那么当它的前驱满足了“至少有两条点不相交的最短路径”之后，它也会自然满足这个条件。简单证明：如下图，对于点 $x$，假设它有前驱 $y$ 和 $z$，其中 $y$ 不是 $z$ 的必经点（否则交换 $y$ 和 $z$），$y$ 有两条点不相交的最短路径 $p_1,p_2$。任取一条从 $1$ 到 $z$ 不经过 $y$ 的路径，假设最后与 $p_1,p_2$ 交在点 $v$，那么 $1 \to p_1 \to y \to x$ 和 $1 \to p_2 \to v \to z \to x$ 就是 $x$ 的两条点不相交的最短路。

  这样一来，就只有最短路图上入度为 $1$ 的点是需要关注的关键点了。对于每个关键点，当然是在最短路长度 $dis$ 比它小的点里找 $w$ 最小的连过来了（这样就能使它入度 $>1$ 了），但如果这个点是它的直接父亲且不为 $1$，那就要找 $w$ 次小的了。
  所以无修改的版本就是把点按 $dis$ 排序，每个点在前面找 $w$ 的最小和次小。

  带修改就有点米奇妙妙屋了。
  首先倒序处理操作，把增加代价变成减少代价，要好做些，因为增加代价是把最小值和次小值分散出去，而减少代价是把最小值和次小值聚集过来。
  这里的分段现象比较明显（连续一段数最(次)小值值相同），考虑用 set 维护这些段，用 $S_1$ 维护最小值相同的连续段及段内需要使用最小值的关键点数量，用 $S_2$ 维护次小值相同的连续段及段内需要使用次小值的关键点数量。当减小点 $k$ 的代价 $w_k$ 时，从第一个 $>dis_k$ 的点开始，先修改 $S_1$，即把最小值 $>w_k$ 的段合并起来并且把这个原最小值变为次小值丢到 $S_2$ 里；再修改 $S_2$，即把次小值 $>w_k$ 的段合并起来。维护关键点数量需要 lower_bound 之类的求一个节点在一个区间内的儿子数量，用关键点数量就可以维护答案了。
  分析一下时间复杂度。初始每个 set 最多有 $n$ 个段，每次修改操作，可能要在初始位置把一个段给断开（即新增一个段）。对于 $S_1$，剩下的就都是合并操作了，所以总段数是 $O(n+q)$ 的，复杂度 $O((n+q) \log (n+q))$。对于 $S_2$，还会在更新最小值的时候产生次小值的新段，但每个最小值段最多只会贡献一个次小值段（贡献完它就被合并了），所以总段数仍然是 $O(n+q)$ 的，复杂度 $O((n+q) \log (n+q))$。

  注意，有一种写法是按“最小值与次小值都相同”对序列分段，只用一个 set。这个复杂度是不对的，如果有很多很多段，这些段的最小值相同，次小值不同，而每次操作都把这个最小值再减小，那就每次操作都要把这些段都遍历一遍了。

  注意一些细节，比如如果最小值次小值记录的是节点标号而不是具体的值，就要注意最小值来源不变但值减少了的情况；比如答案会爆 long long，要 unsigned long long。

扯淡

  可能可以把一些 set 操作换成线段树？就像题解写的那样。

  比较搞笑的是，在我本地拍的时候，上面说的“只用一个 set 维护最小值和次小值都相同的段”的写法跑得比分开两个 set 的写法还要快。。。不过前者交上去就 T 了。
  （并且在拍的过程中还卡 T 了一个跑得飞快的老哥。。。可惜现在不能 hack 了 QAQ

代码

// 实现细节比较多，修修补补会变得特别丑，建议少看（x

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const int maxn=2e5+5, maxq=2e5+5;

struct SEG {
	int l,r,minw,num;
	SEG(int l0,int r0,int minw0,int num0) {l=l0, r=r0, minw=minw0, num=num0;}
};
bool operator < (const SEG &a,const SEG &b) {return a.r<b.r;}

int n,m,q,qk[maxq],qx[maxq];
vector<pair<int,int>> e[maxn];
ULL w[maxn];

LL dis[maxn];
int d[maxn],d0;
void dijkstra() {
	memset(dis,127,sizeof(dis));
	dis[1]=0;
	priority_queue<pair<LL,int>> Q;
	Q.push(make_pair(0ll,1));
	while (!Q.empty()) {
		auto tp=Q.top(); Q.pop();
		int cur=tp.second;
		if (-tp.first!=dis[cur]) continue;
		d[++d0]=cur;
		for(auto go:e[cur]) if (dis[go.first]>dis[cur]+go.second) {
			dis[go.first]=dis[cur]+go.second;
			Q.push(make_pair(-dis[go.first],go.first));
		}
	}
}

vector<int> son[maxn];
set<SEG> S1,S2;
int indg[maxn],fa[maxn],st[maxn],keynum[maxn];
ULL ans;
void init() {
	fo(i,1,n)
		for(auto go:e[i]) if (dis[i]+go.second==dis[go.first]) {
			indg[go.first]++;
			fa[go.first]=i;
		}
	
	SEG min1(1,1,1,0), min2(1,1,1,0);
	int j=1;
	memset(st,127,sizeof(st));
	fo(i,2,n) {
		int cur=d[i];
		int minw1=min1.minw, minw2=min2.minw;
		for(; j<=n && dis[d[j]]<dis[cur]; j++) {
			st[d[j]]=i;
			if (w[d[j]]<w[minw1]) minw2=minw1, minw1=d[j];
				else if (w[d[j]]<w[minw2]) minw2=d[j];
		}
		if (minw1!=min1.minw || minw2!=min2.minw) {
			if (min2.l<=min2.r) S2.insert(min2);
			min2=SEG(min2.r+1,i,minw2,0);
		}
		if (minw1!=min1.minw) {
			if (min1.l<=min1.r) S1.insert(min1);
			min1=SEG(min1.r+1,i,minw1,0);
		}
		keynum[i]=keynum[i-1]+(indg[cur]==1);
		if (indg[cur]==1) {
			son[fa[cur]].push_back(i);
			if (fa[cur]!=1 && fa[cur]==minw1) {
				min2.num++;
				ans+=w[minw2];
			} else {
				min1.num++;
				ans+=w[minw1];
			}
		}
		min1.r=min2.r=i;
	}
	S1.insert(min1);
	S2.insert(min2);
}

int get_num(int l,int r,int minw) {
	return (minw==1) ?0 :upper_bound(son[minw].begin(),son[minw].end(),r)-upper_bound(son[minw].begin(),son[minw].end(),l-1);
}

void cut_cur(set<SEG> &S,int pos,int ty) {
	set<SEG>::iterator it=S.lower_bound(SEG(0,pos,0,0));
	if (it==S.end() || it->l==pos) return;
	SEG t=*it;
	S.erase(it);
	if (ty==1) {
		S.insert(SEG(t.l, pos-1, t.minw, keynum[pos-1]-keynum[t.l-1]-get_num(t.l,pos-1,t.minw)));
		S.insert(SEG(pos, t.r, t.minw, keynum[t.r]-keynum[pos-1]-get_num(pos,t.r,t.minw)));
	} else {
		S.insert(SEG(t.l, pos-1, t.minw, get_num(t.l,pos-1,(S1.lower_bound(SEG(0,t.l,0,0)))->minw)));
		S.insert(SEG(pos, t.r, t.minw, get_num(pos,t.r,(S1.lower_bound(SEG(0,pos,0,0)))->minw)));
	}
}

ULL Ans[maxn],w_old[maxn];
int main() {
	scanf("%d %d %d",&n,&m,&q);
	fo(i,1,n) {
		LL x;
		scanf("%lld",&x);
		w[i]=x;
	}
	fo(i,1,m) {
		int u,v,d;
		scanf("%d %d %d",&u,&v,&d);
		e[u].push_back(make_pair(v,d)), e[v].push_back(make_pair(u,d));
	}
	fo(i,1,q) {
		scanf("%d %d",&qk[i],&qx[i]);
		w[qk[i]]+=qx[i];
	}
	
	dijkstra();
	init();
	
	memcpy(w_old,w,sizeof(w));
	fd(i,q,1) {
		Ans[i]=ans;
		int cur=qk[i];
		w[cur]-=qx[i];
		
		cut_cur(S1,st[cur],1);
		cut_cur(S2,st[cur],2);
		
		// minw1
		int tl=st[cur], tr=tl-1, tnum=0;
		set<SEG>::iterator it=S1.lower_bound(SEG(0,tl,0,0));
		while (it!=S1.end() && w[cur]<w_old[it->minw]) {
			SEG t=*it;
			if (t.minw==cur) {
				ans-=(ULL)t.num*qx[i];
				it++;
				tl=t.r+1, tr=t.r;
				continue;
			}
			ans-=t.num*w_old[t.minw];
			S1.erase(it++);
			set<SEG>::iterator it2=S2.lower_bound(SEG(0,t.l,0,0));
			while (it2!=S2.end() && it2->l<=t.r) {
				ans-=w_old[it2->minw]*it2->num;
				S2.erase(it2++);
			}
			int num=get_num(t.l,t.r,cur);
			ans+=w[t.minw]*num;
			S2.insert(SEG(t.l,t.r,t.minw,num));
			tnum+=keynum[t.r]-keynum[t.l-1]-num;
			tr=t.r;
		}
		if (tl<=tr) {
			ans+=tnum*w[cur];
			S1.insert(SEG(tl,tr,cur,tnum));
		}
		
		// minw2
		tl=tr+1;
		tnum=0;
		it=S2.lower_bound(SEG(0,tl,0,0));
		while (it!=S2.end() && w[cur]<w_old[it->minw]) {
			tr=it->r;
			tnum+=it->num;
			ans-=it->num*w_old[it->minw];
			S2.erase(it++);
		}
		if (tl<=tr) {
			ans+=tnum*w[cur];
			S2.insert(SEG(tl,tr,cur,tnum));
		}
		
		w_old[cur]-=qx[i];
	}
	Ans[0]=ans;
	
	fo(i,0,q) printf("%llu\n",Ans[i]);
}