loj #3540. 「JOI Open 2018」山体滑坡 ( WC2022模拟赛25 t3 )

在 JOI 国有 \(n\) 个城镇，它们坐落于一个幽深峡谷中。城镇按到海洋的距离的顺序分别编号为 \(0,1,\cdots,n-1\) 。

I 先生是 JOI 国科学委员会的主席，他准备维护城镇之间双向连接的电缆。目前 JOI 国没有电缆。

I 先生有一个 \(C\) 天的电缆建设计划。第 \((i+1)(0\leq i\leq C-1)\) 天的计划用三个整数 \(T_i,X_i,Y_i\) 表示，分别表示：

• 如果 \(T_i=0\) , 他们会架设一段连接城镇 \(X_i\) 与城镇 \(Y_i\) 的电缆。保证在第 \((i+1)\) 天开始的时候城镇 \(X_i\) 与城镇 \(Y_i\) 之间没有电缆。
• 如果\(T_i=1\) ，他们会拆除一段连接城镇 \(X_i\) 与城镇 \(Y_i\) 的电缆。保证在第 \((i+1)\) 天开始的时候城镇 \(X_i\) 与城镇 \(Y_i\) 之间有电缆。

JOI 国经常发生山体滑坡。如果在城镇 \(x\) 与 \(x+1\ (0\leq x\leq n-2)\) 之间发生山体滑坡，则连接编号至多为 \(x\) 与编号至少为 \(x+1\) 城镇的电缆就不可用了。在 JOI 国，每当山体滑坡发生，他们就会选择一些城镇建设基站。基站应满足对于任意城镇，都可以通过一些可用的电缆与基站连通。

I 先生在建设阶段就在考虑山体滑坡发生时应建设多少基站。他有 \(q\) 个问题：第 \((j+1)\) 个问题用两个整数 \(W_j,P_j\) 表示，表示他想知道在 \((w_j+1)\) 天结束时，如果在城镇 \(P_j\) 和 \(P_j+1\) 之间发生山体滑坡，至少应该建立多少基站。

你作为 I 先生的助理，负责写一个程序去回答 I 先生的问题。

\(2\leq n\leq 10^5,1\leq c,q\leq 10^5\)

首先，联通块的个数 = 总点数 - 生成数的边数 .

那么，生成树的边数是一个联通性问题，可以用 \(\rm{dsu}\) 维护，又是那么熟悉的味道 . 所以考虑可撤销并查集 . 将操作分块 . 块的大小为 \(S\) .

此时 \(i\) 和 \(i+1\) 之间，相当于 \(\max(u,v)\leq i\) 加上 \(\max(u,v)\geq i+1\) . 因为这两个部分点集不会重合，所以可以分开处理 .

对于 \(\max(u,v)\leq i\) 的部分，首先从小到大加入 \((u,v)\) ，维护当前边的数量，对于时间在 \([l,l+S)\) 的询问，遍历操作，如何符合条件则加入，得到当前生成树变数之后在 \(\rm{dsu}\) 上撤销操作 . \(\max(u,v)\geq i+1\) 同理 .

时间复杂度 : \(O(qS\alpha(n)+\frac{n}{S}n\alpha(n))\)

空间复杂度 : \(O(n)\)

当块的大小取到 \(750\) 的时候最快 .

code

#include
#include "collapse.h"
using namespace std;
#define vi vector
#define pii pair
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N=1e5+10;
const int B=750;
int n,m,q;
class edge{public:int tp,u,v;}e[N];
vectorQ[N],qq[N];
map,int>Map;
int ed[N];
vectorv[N];
int ans[N];
int fa[N],sz[N],cmp=0,top=0;
pii s[N];
void init(){cmp=0;for(int i=0;isimulateCollapse(int NN,vi T,vi X,vi Y,vi W,vi P){
	n=NN;m=(int)T.size();q=(int)W.size();
	for(int i=0;i >ve;
		for(int i=0;i<=r;i++){
			if(ed[i]r)v[max(e[i].u,e[i].v)].pb(e[i]);
			else ve.pb(mp(e[i],mp(i,ed[i])));
		}
		for(int i=l;i<=r;i++)for(auto t:Q[i])qq[t.fi].pb(mp(i,t.se));
		init();
		for(int i=0;ir)v[min(e[i].u,e[i].v)].pb(e[i]);
			else ve.pb(mp(e[i],mp(i,ed[i])));
		}
		init();
		for(int i=n-1;i>=1;i--){
			for(auto t:v[i])cmp+=merge(t.u,t.v,0);
			for(auto x:qq[i-1]){
				int tm=x.fi,id=x.se;
				for(auto t:ve)if(min(t.fi.u,t.fi.v)>=i&&t.se.fi<=tm&&tm<=t.se.se)
					cmp+=merge(t.fi.u,t.fi.v,1);
				ans[id]+=cmp;
				undo();
			}
		}
	}
	vectorres;
	for(int i=0;i
#include 
int main(int argc, char *argv[]) {
	int N, C, Q;
	scanf("%d%d%d", &N, &C, &Q);
	std::vector T(C), X(C), Y(C);
	for(int i = 0; i < C; i++) {
		scanf("%d%d%d", &T[i], &X[i], &Y[i]);
	}
	std::vector W(Q), P(Q);
	for(int i = 0; i < Q; i++) {
		scanf("%d%d", &W[i], &P[i]);
	}
	auto res = simulateCollapse(N, T, X, Y, W, P);
	for(auto i : res) {
		printf("%d\n", i);
	}
}
#endif