首页 > 其他分享 >Kruskal 重构树 学习笔记

Kruskal 重构树 学习笔记

时间：2022-10-22 16:16:26浏览次数：78  
标签：重构 le return int Kruskal 笔记 maxn

参考资料：Kruskal 重构树学习笔记 - ImmortalWatcher

定义

顾名思义，Kruskal 重构树就是用 Kruskal 生成树算法在无向图上得到的树所构建出的新树。

Kruskal 重构树具有良好的性质，在一些特定的问题上能够帮助我们解决问题。

构造

这里以 Kruskal 最小生成树为例。

将所有边按升序排序，用 Kruskal 算法跑出最小生成树。

接着，将最小生成树上的边逐个取出，设当前边为 \((x,y)\)，若 \(x,y\) 在新树上尚未连通，就新建一个节点 \(new\)，令 \(new\) 分别于 \(x,y\) 在新树上的根节点（初始时为它本身）连边。

这个过程可以在最小生成树的计算中同步完成。

	for(int i = 1;i <= n * 2;++ i)
		pre[i] = i;
	std::sort(E + 1 , E + 1 + m , [&](const node& p,const node& q) {
		return p.t < q.t;
	});
	cnt = n;
	for(int i = 1;i <= m;++ i) {
		int u = find(E[i].u),v = find(E[i].v);
		if(u == v)continue ;
		pre[u] = pre[v] = ++ cnt;
		val[cnt] = E[i].t;
		G[cnt].pb(u);
		G[cnt].pb(v);
		if(cnt == 2 * n - 1)break ;
	}

性质

  • 是一棵二叉树。

  • 可以将其视作一个堆。

  • 关键性质：原图中两个点间所有路径上的边最大权值的最小值 \(=\) 最小生成树上两点简单路径的边最大权值 \(=\) Kruskal 重构树上两点 LCA 的点权。

如果我们要找到从 \(x\) 出发经过权值不超过 \(val\) 的边所能到达的点 \(y\) 的集合，只需要建出 Kruskal 重构树，倍增找出点权 \(\le val\) 的最浅节点，它的子树内叶子结点即是 \(y\) 的集合。

类似地，如果要使最小边权最大化，只需用 Kruskal 建立最大生成树的重构树即可。

例题

[BZOJ#3732]Network

给定 \(n\) 个结点，\(m\) 条边的无向图，\(Q\) 次询问，每次问 \(a\to b\) 路径上最大边权最小值。

\(1\le n\le 1.5\times 10^4,1\le m\le 3\times 10^4,1\le Q\le 2\times 10^4\)

根据 Kruskal 重构树的性质，直接建出最小生成树的重构树，跑倍增 LCA 即可。

不知道是什么题

给定一个带权树。定义 \(d(x,y)\) 为 \(x\to y\) 路径上的最小边权。对于 \(1\sim n\)，求 \(f(i)=\sum\limits_{x\in [1,n]} d(x,i)\)

建出 Kruskal 重构树。

根据性质中的结论，两点间路径上边权最小值即为重构树上两点间 LCA 的点权。

那么我们枚举每个新点，显然它的左子树和右子树间互相有贡献，树上差分一波就行。

（因为这道题不知道是哪的，我也没写代码，以上为纯口胡，如果错了请见谅 qwq）

[ONTAK2010] Peaks 加强版

给定一张 \(n\) 个点，\(m\) 条边的带权无向图，第 \(i\) 个点的点权为 \(a_i\)。

\(Q\) 次询问，强制在线，每次询问点 \(u\) 经过权值不超过 \(x\) 的边所能到达的点的点权的 \(k\) 大值。

\(1\le n\le 10^5,1\le m,Q\le 5\times 10^5\)

构建最小生成树的重构树，用性质中提到的方法倍增求出 \(u\) 能到达的节点集合。

离散化一下 \(a\)，跑出 dfs 序，用主席树维护区间第 \(k\) 大即可。

（在非加强版中，这个也可以用线段树合并离线解决）

// Problem: P7834 [ONTAK2010] Peaks 加强版
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7834
// Memory Limit: 128 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back

const int maxn = 1e5 + 5;
const int maxm = 5e5 + 5;
std::vector<int> G[maxn << 1];
struct node {
	int u,v,t;
	node() {
		u = v = t = 0;
	}
}E[maxm];
int n,m,Q,a[maxn],val[maxn << 1],pre[maxn << 1],cnt,res,b[maxn];

int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}

int f[maxn << 1][20],d[maxn << 1],lg[maxn << 1],rk[maxn << 1],L[maxn << 1],R[maxn << 1],dfn[maxn << 1],tot;

void dfs(int u) {
	if(!G[u].size()) {
		rk[dfn[u] = ++ tot] = u;
		L[u] = R[u] = dfn[u];
		return ;
	}
	L[u] = n;
	R[u] = 0;
	for(auto& v : G[u]) {
		d[v] = d[u] + 1;
		f[v][0] = u;
		for(int k = 1;(1 << k) <= d[v];++ k)
			f[v][k] = f[f[v][k - 1]][k - 1];
		dfs(v);
		L[u] = std::min(L[u] , L[v]);
		R[u] = std::max(R[u] , R[v]);
	}
	return ;
}

int rt[maxn],ls[maxn << 5],rs[maxn << 5],sum[maxn << 5],num;

int build(int l,int r) {
	int p = ++ num;
	sum[p] = 0;
	if(l == r)return p;
	int mid = l + r >> 1;
	ls[p] = build(l , mid);
	rs[p] = build(mid + 1 , r);
	return p;
}

int modify(int i,int l,int r,int val) {
	int p = ++ num;
	sum[p] = sum[i] + 1;
	if(l == r)return p;
	int mid = l + r >> 1;
	if(val <= mid)ls[p] = modify(ls[i] , l , mid , val),rs[p] = rs[i];
	else rs[p] = modify(rs[i] , mid + 1 , r , val),ls[p] = ls[i];
	return p;
}

int query(int i,int pre,int l,int r,int k) {
	if(l == r)return l;
	int mid = l + r >> 1,x = sum[ls[i]] - sum[ls[pre]];
	if(k <= x)return query(ls[i] , ls[pre] , l , mid , k);
	else return query(rs[i] , rs[pre] , mid + 1 , r , k - x);
}

int main() {
	scanf("%d %d %d",&n,&m,&Q);
	for(int i = 1;i <= n;++ i)
		scanf("%d",&a[i]),b[i] = a[i];
	std::sort(b + 1 , b + 1 + n);
	res = std::unique(b + 1 , b + 1 + n) - b - 1;
	for(int i = 1;i <= n;++ i)
		a[i] = std::lower_bound(b + 1 , b + 1 + res , a[i]) - b;
	
	for(int i = 1;i <= m;++ i)
		scanf("%d %d %d",&E[i].u,&E[i].v,&E[i].t);
	
	for(int i = 1;i <= n * 2;++ i)
		pre[i] = i;
	std::sort(E + 1 , E + 1 + m , [&](const node& p,const node& q) {
		return p.t < q.t;
	});
	cnt = n;
	for(int i = 1;i <= m;++ i) {
		int u = find(E[i].u),v = find(E[i].v);
		if(u == v)continue ;
		pre[u] = pre[v] = ++ cnt;
		val[cnt] = E[i].t;
		G[cnt].pb(u);
		G[cnt].pb(v);
		if(cnt == 2 * n - 1)break ;
	}
	
	for(int i = 2;i <= n * 2;++ i)
		lg[i] = lg[i >> 1] + 1;
	dfs(cnt);
	rt[0] = build(1 , res);
	for(int i = 1;i <= n;++ i)
		rt[i] = modify(rt[i - 1] , 1 , res , a[rk[i]]);
	
	int ans = 0;
	while(Q --) {
		int u,x,k,v;
		scanf("%d %d %d",&u,&x,&k);
		u = (u ^ ans) % n + 1;
		k = (k ^ ans) % n + 1;
		x ^= ans;
		v = u;
		for(int p = lg[d[u]];~ p;-- p)
			if(f[v][p]&&val[f[v][p]] <= x)v = f[v][p];
		if(R[v] - L[v] + 1 < k)puts("-1"),ans = 0;
		else printf("%d\n",ans = b[query(rt[R[v]] , rt[L[v] - 1] , 1 , res , R[v] - L[v] + 1 - k + 1)]);
	}
	return 0;
}

[AGC002D] Stamp Rally

给定一个连通无向图。\(q\) 次询问，每次给定两个点 \(x,y\)，求从 \(x,y\) 总共走 \(z\) 步经过的边编号最大值的最小值是多少。

\(1\le n,m,q\le 10^5\)

前面的题目都对边权做了限制，但这题没有，它只对步数做了限制。

考虑二分答案，转化为判定：\(x,y\) 只走编号 \(\le k\) 的边所能到达的点是否 \(\ge z\)。

仍然是建出 Kruskal 重构树，\(x,y\) 都倍增一下（注意判重），根据叶子结点的数量判断即可。

// Problem: AT_agc002_d [AGC002D] Stamp Rally
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_agc002_d
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back

const int maxn = 1e5 + 5;
int n,m,cnt,pre[maxn << 1],val[maxn << 1];
int sum[maxn << 1],d[maxn << 1],lg[maxn << 1],f[maxn << 1][20];
std::vector<int> G[maxn << 1];

int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}

void dfs(int u) {
	for(auto& v : G[u]) {
		d[v] = d[u] + 1;
		f[v][0] = u;
		for(int k = 1;(1 << k) <= d[v];++ k)
			f[v][k] = f[f[v][k - 1]][k - 1];
		dfs(v);
		sum[u] += sum[v];
	}
	return ;
}

int calc(int x,int y,int mid) {
	for(int k = 17;~ k;-- k) {
		if(f[x][k]&&val[f[x][k]] <= mid)x = f[x][k];
		if(f[y][k]&&val[f[y][k]] <= mid)y = f[y][k];
	}
	return (x ^ y) ? sum[x] + sum[y] : sum[x];
}

int main() {
	scanf("%d %d",&n,&m);
	cnt = n;
	for(int i = 1;i <= n;++ i)sum[i] = 1;
	for(int i = 1;i <= 2 * n;++ i)pre[i] = i;
	for(int i = 1;i <= m;++ i) {
		int u,v;
		scanf("%d %d",&u,&v);
		u = find(u);
		v = find(v);
		if(u == v)continue ;
		pre[u] = pre[v] = ++ cnt;
		val[cnt] = i;
		G[cnt].pb(u);
		G[cnt].pb(v);
	}
	
	for(int i = 2;i <= 2 * n;++ i)
		lg[i] = lg[i >> 1] + 1;
	dfs(cnt);
	
	int Q;
	for(scanf("%d",&Q);Q --;) {
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		int l = 1,r = m;
		while(l <= r) {
			int mid = l + r >> 1;
			if(calc(x , y , mid) >= z)r = mid - 1;
			else l = mid + 1;
		}
		printf("%d\n",l);
	}
	return 0;
}

[NOI2018] 归程 - 洛谷

好长的题面，不简述了。

把最大生成树的重构树建出来，水位线的限制就解除了。

预处理出 1 号节点到其它点的最短路，用倍增找出从 \(v\) 乘车出发能到达的所有点。

此时问题就是静态查询子树内叶子结点的权值最小值，构树的时候就能预处理出来。

要注意一下这题的最短路，出题人刻意卡了 SPFA。关于 SPFA，它死了。

// Problem: P4768 [NOI2018] 归程
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4768
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
typedef std::pair<int,int> pii;

const int maxn = 2e5 + 5;
const int maxm = 4e5 + 5;
int n,m,cnt,pre[maxn << 1],dis[maxn << 1],val[maxn << 1];
std::vector<int> G[maxn << 1];
struct node {
	int u,v,x;
	node() {
		u = v = x = 0;
	}
	node(int u,int v,int x):u(u),v(v),x(x){}
}E[maxm];

int find(int x) {
	return pre[x] == x ? x : pre[x] = find(pre[x]);
}

std::vector<pii> S[maxn];
std::priority_queue<pii,std::vector<pii>,std::greater<pii> > q;
bool vis[maxn];

void dijkstra(int s) {
	for(int i = 1;i <= n;++ i)
		dis[i] = 2e9,vis[i] = false;
	q.emplace(dis[s] = 0 , s);
	while(!q.empty()) {
		int u = q.top().second;
		q.pop();
		if(vis[u])continue ;
		vis[u] = true;
		for(auto& [v , w] : S[u]) {
			if(dis[v] > dis[u] + w)
				q.emplace(dis[v] = dis[u] + w , v);
		}
	}
	return ;
}

int d[maxn << 1],lg[maxn << 1],f[maxn << 1][20];

void dfs(int u) {
	for(auto& v : G[u]) {
		d[v] = d[u] + 1;
		f[v][0] = u;
		for(int k = 1;(1 << k) <= d[v];++ k)
			f[v][k] = f[f[v][k - 1]][k - 1];
		dfs(v);
	}
	return ;
}

void work() {
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;++ i)
		S[i].clear();
	for(int i = 1;i <= m;++ i) {
		int u,v,t,x;
		scanf("%d %d %d %d",&u,&v,&t,&x);
		E[i] = node(u , v , x);
		S[u].pb(v , t);
		S[v].pb(u , t);
	}
	
	dijkstra(1);
	cnt = n;
	for(int i = 1;i <= n * 2;++ i)
		G[i].clear(),pre[i] = i;
	std::sort(E + 1 , E + 1 + m , [&](const node& p,const node& q) {
		return p.x > q.x;
	});
	for(int i = 1;i <= m;++ i) {
		int u = find(E[i].u),v = find(E[i].v);
		if(u == v)continue ;
		pre[u] = pre[v] = ++ cnt;
		val[cnt] = E[i].x;
		dis[cnt] = std::min(dis[u] , dis[v]);
		G[cnt].pb(u);
		G[cnt].pb(v);
	}
	
	for(int i = 2;i <= n * 2;++ i)
		lg[i] = lg[i >> 1] + 1;
	for(int i = 1;i <= n * 2;++ i)
		for(int k = 0;k < 20;++ k)
			f[i][k] = 0;
	dfs(cnt);
	
	int Q,k,s,ans = 0;
	scanf("%d %d %d",&Q,&k,&s);
	while(Q --) {
		int u,p;
		scanf("%d %d",&u,&p);
		u = (u + k * ans - 1) % n + 1;
		p = (p + k * ans) % (s + 1);
		for(int j = lg[d[u]];~ j;-- j)
			if(f[u][j]&&val[f[u][j]] > p)u = f[u][j];
		printf("%d\n",ans = dis[u]);
	}
	return ;
}

int main() {
	int T;
	scanf("%d",&T);
	while(T --)work();
	return 0;
}

[CERC2016]机棚障碍 Hangar Hurdles

还是懒得概括题面。

不难发现，一个箱子从点 \(A\) 移动到点 \(B\) 的充要条件是箱子大小不超过 \(A,B\) 两点的限制。

用二分和二维前缀和预处理出来点 \((i,j)\) 的限制，设为 \(d(i,j)\)。

显然，若 \((i,j)\) 与 \((x,y)\) 相邻，那么它们之间可以连一条权值为 \(\min\{d(i,j),d(x,y)\}\) 的边。

每次询问要回答的其实就是从 \(A_k\) 到 \(B_k\) 的最小权值的最大值。

这个模型显然就是最大生成树重构树的模型。直接套模板即可。

我参考的学习笔记中，大佬给出了 FloodFill 缩点减少时空复杂度的方法。我这里也写了一下。当然，不这样写也可以过。

// Problem: P3684 [CERC2016]机棚障碍 Hangar Hurdles
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3684
// Memory Limit: 500 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back

const int maxn = 1005;
const int maxm = 3e6 + 5;
int n,d[maxn][maxn],dfn[maxn][maxn],cnt,pre[maxm],val[maxm],sum[maxn][maxn];
char s[maxn][maxn];
std::vector<int> tmp,G[maxm];
int fx[] = {1 , 0 , -1 , 0},fy[] = {0 , 1 , 0 , -1};
struct node {
	int u,v,t;
	node() {
		u = v = t = 0;
	}
	node(int u,int v,int t):u(u),v(v),t(t){}
}E[maxm];

int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}

void dfs(int x,int y) {
	if(dfn[x][y])return ;
	dfn[x][y] = cnt;
	for(int k = 0;k < 4;++ k) {
		int nx = x + fx[k],ny = y + fy[k];
		if(nx < 1||nx > n||ny < 1||ny > n)continue ;
		if(!dfn[nx][ny]&&d[nx][ny] == d[x][y])dfs(nx , ny);
	}
}

int f[maxm][23],lg[maxm],dep[maxm];

void DFS(int u) {
	for(auto& v : G[u]) {
		dep[v] = dep[u] + 1;
		f[v][0] = u;
		for(int k = 1;(1 << k) <= dep[v];++ k)
			f[v][k] = f[f[v][k - 1]][k - 1];
		DFS(v);
	}
	return ;
}

int LCA(int u,int v) {
	if(dep[u] < dep[v])std::swap(u , v);
	for(int k = lg[dep[u]];~ k;-- k) {
		if(dep[u] - (1 << k) >= dep[v]) {
			u = f[u][k];
		}
		if(u == v)return u;
	}
	for(int k = lg[dep[u]];~ k;-- k) {
		if(f[u][k] != f[v][k]) {
			u = f[u][k];
			v = f[v][k];
		}
	}
	return f[u][0];
}

int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n;i += 2)tmp.pb(i);
	for(int i = 1;i <= n;++ i) {
		scanf("%s",s[i] + 1);
		for(int j = 1;j <= n;++ j) {
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (s[i][j] == '#');
		}
	}
	
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= n;++ j) {
			if(s[i][j] == '#') {
				d[i][j] = 0;
				continue ;
			}
			int l = 0,r = tmp.size() - 1;
			while(l <= r) {
				int mid = l + r >> 1,k = tmp[mid] >> 1;
				if(i + k > n||i - k <= 0||j + k > n||j - k <= 0) {
					r = mid - 1;
					continue ;
				}
				if(sum[i + k][j + k] - sum[i + k][j - k - 1] - sum[i - k - 1][j + k] + sum[i - k - 1][j - k - 1] > 0)
					r = mid - 1;
				else l = mid + 1;
			}
			d[i][j] = tmp[r];
		}
	}
	
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= n;++ j) {
			if(!dfn[i][j]) {
				val[++ cnt] = d[i][j];
				dfs(i , j);
			}
		}
	}
	
	int tot = 0;
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= n;++ j) {
			for(int k = 0;k < 2;++ k) {//注意一下，这里不是 4 而是 2，减少了一些重复的边。
				int x = i + fx[k],y = j + fy[k];
				if(x < 1||x > n||y < 1||y > n)continue ;
				if(dfn[i][j] != dfn[x][y])
					E[++ tot] = node(dfn[i][j] , dfn[x][y] , std::min(d[i][j] , d[x][y]));
			}
		}
	}
	
	std::sort(E + 1 , E + 1 + tot , [&](const node& p,const node& q) {
		return p.t > q.t;
	});
	for(int i = 1;i <= cnt * 2;++ i)pre[i] = i;
	for(int i = 1;i <= tot;++ i) {
		int u = find(E[i].u),v = find(E[i].v);
		if(u == v)continue ;
		pre[u] = pre[v] = ++ cnt;
		val[cnt] = E[i].t;
		G[cnt].pb(u);
		G[cnt].pb(v);
	}
	
	for(int i = 2;i <= cnt;++ i)
		lg[i] = lg[i >> 1] + 1;
	DFS(cnt);
	
	int Q;
	scanf("%d",&Q);
	while(Q --) {
		int x,y,nx,ny;
		scanf("%d %d %d %d",&x,&y,&nx,&ny);
		printf("%d\n",val[LCA(dfn[x][y] , dfn[nx][ny])]);
	}
	return 0;
}

[CF1706E] Qpwoeirut and Vertices

这是我在学习 Kruskal 重构树之前遇到的第一道 Kruskal 重构树的题目。

题解在这里，当时我并不会标准的 Kruskal 重构树，本质上是写了一个最小生成树上倍增。

不过这题是名副其实的 Educational 题，质量很不错，可以拿来练手。

[IOI2018] werewolf 狼人

仍然懒得写题意。

首先要发现，这个问题的本质是：

令 \(A\) 为 \(S\) 经过 \(\ge L\) 的边能到达的点的集合，\(B\) 为 \(E\) 经过 \(\le R\) 的边能到达的点的集合，判断 \(A\cap B\) 是否为空集。这个问题的加强版在 [CF1093E]Intersection of Permutations，需要了解做法。

分别构建两棵重构树，一棵为最大生成树 \(tr_0\)，一棵为最小生成树 \(tr_1\)。

预处理出两棵树的 dfs 序，在询问中倍增求区间，然后用主席树求解即可。

这里有个很简单，但困扰了我很长时间的问题：边权怎么设？我不会说我是因为这个问题调了 4h 的。

因为 \(S\) 经过的所有点编号都要 \(\ge L\)，所以 \(tr_0\) 中，边 \((u,v)\) 的权值应为 \(\min\{u,v\}\)。

相应的，\(tr_1\) 中边 \((u,v)\) 的权值为 \(\max\{u,v\}\)。

因为一开始这个简单的问题我没搞明白，导致代码中建树的过程乱七八糟，见谅。

// Problem: P4899 [IOI2018] werewolf 狼人
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4899
// Memory Limit: 500 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back

const int maxn = 4e5 + 5;
int n,m,Q,pre[maxn],a[maxn],rk[maxn],from[maxn],to[maxn];
struct Edge {
	int u,v,t;
	Edge() {
		u = v = t = 0;
	}
	Edge(int u,int v,int t):u(u),v(v),t(t){}
}E[maxn];

int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}

struct Kruskal_rebuild {
	std::vector<int> G[maxn];
	int val[maxn],cnt,num,lg[maxn],f[maxn][20],d[maxn],L[maxn],R[maxn],dfn[maxn];
	
	void dfs(int u) {
		if(u <= n)
			L[u] = R[u] = ++ num,dfn[num] = u,val[u] = u;
		else L[u] = num + 1;
		for(auto& v : G[u]) {
			d[v] = d[u] + 1;
			f[v][0] = u;
			for(int k = 1;(1 << k) <= d[v];++ k)
				f[v][k] = f[f[v][k - 1]][k - 1];
			dfs(v);
		}
		R[u] = num;
		return ;
	}
	
	void build_1() {
		for(int i = 1;i <= m;++ i)
			E[i].u = from[i],E[i].v = to[i],E[i].t = std::max(E[i].u , E[i].v);
		for(int i = 1;i <= n * 2;++ i)pre[i] = i;
		cnt = n;
		std::sort(E + 1 , E + 1 + m , [&](const Edge& p,const Edge& q) {
			return p.t < q.t;
		});
		for(int i = 1;i <= m;++ i) {
			int u = find(E[i].u),v = find(E[i].v);
			if(u == v)continue ;
			pre[u] = pre[v] = ++ cnt;
			val[cnt] = E[i].t;
			G[cnt].pb(u);
			G[cnt].pb(v);
			if(cnt == 2 * n - 1)break ;
		}
		
		for(int i = 2;i <= n * 2;++ i)
			lg[i] = lg[i >> 1] + 1;
		dfs(cnt);
		return ;
	}
	
	void build_2() {
		for(int i = 1;i <= m;++ i)
			E[i].u = from[i],E[i].v = to[i],E[i].t = std::min(E[i].u , E[i].v);
		for(int i = 1;i <= n * 2;++ i)pre[i] = i;
		cnt = n;
		std::sort(E + 1 , E + 1 + m , [&](const Edge& p,const Edge& q) {
			return p.t > q.t;
		});
		for(int i = 1;i <= m;++ i) {
			int u = find(E[i].u),v = find(E[i].v);
			if(u == v)continue ;
			pre[u] = pre[v] = ++ cnt;
			val[cnt] = E[i].t;
			G[cnt].pb(u);
			G[cnt].pb(v);
			if(cnt == 2 * n - 1)break ;
		}
		
		for(int i = 2;i <= n * 2;++ i)
			lg[i] = lg[i >> 1] + 1;
		dfs(cnt);
		return ;
	}
	
	int find_1(int x,int v) {
		for(int k = lg[d[x]];~ k;-- k)
			if(f[x][k]&&val[f[x][k]] >= v)x = f[x][k];
		return x;
	}
	
	int find_2(int x,int v) {
		for(int k = lg[d[x]];~ k;-- k)
			if(f[x][k]&&val[f[x][k]] <= v)x = f[x][k];
		return x;
	}
}tr[2];

int tot,ls[maxn << 5],rs[maxn << 5],sum[maxn << 5],rt[maxn];

int build(int l,int r) {
	int p = ++ tot;
	sum[p] = 0;
	if(l == r)return p;
	int mid = l + r >> 1;
	ls[p] = build(l , mid);
	rs[p] = build(mid + 1 , r);
	return p;
}

int modify(int i,int l,int r,int pos) {
	int p = ++ tot;
	sum[p] = sum[i] + 1;
	if(l == r)return p;
	int mid = l + r >> 1;
	if(pos <= mid)ls[p] = modify(ls[i] , l , mid , pos),rs[p] = rs[i];
	else rs[p] = modify(rs[i] , mid + 1 , r , pos),ls[p] = ls[i];
	return p;
}

int query(int i,int pre,int l,int r,int val) {
	if(l == r)return l == val ? sum[i] - sum[pre] : 0;
	int mid = l + r >> 1;
	if(val <= mid)return query(ls[i] , ls[pre] , l , mid , val);
	else return query(rs[i] , rs[pre] , mid + 1 , r , val) + sum[ls[i]] - sum[ls[pre]];
}

int main() {
	int Q;
	scanf("%d %d %d",&n,&m,&Q);
	for(int i = 1;i <= m;++ i) {
		scanf("%d %d",&from[i],&to[i]);
		++ from[i];
		++ to[i];
	}
	
	tr[0].build_2();//这里 build_1 和 build_2 是反过来的，看得有点难受，还是一开始没理解的锅。
	tr[1].build_1();
	
	for(int i = 1;i <= n;++ i)rk[tr[0].dfn[i]] = i;
	rt[0] = build(1 , n);
	for(int i = 1;i <= n;++ i)
		rt[i] = modify(rt[i - 1] , 1 , n , rk[tr[1].dfn[i]]);
	
	while(Q --) {
		int s,t,l,r;
		scanf("%d %d %d %d",&s,&t,&l,&r);
		++ s;
		++ t;
		++ l;
		++ r;
		int x = tr[0].find_1(s , l),y = tr[1].find_2(t , r);
		if(query(rt[tr[1].R[y]] , rt[tr[1].L[y] - 1] , 1 , n , tr[0].R[x]) - query(rt[tr[1].R[y]] , rt[tr[1].L[y] - 1] , 1 , n , tr[0].L[x] - 1))
			puts("1");
		else
			puts("0");
	}
	return 0;
}

本来还有两道例题，是 [CF1578L] Labyrinth 和 [ARC098F] Donation ，不过我看了一下，一道 CF *2400，一道 AT *3200，感觉不好惹，先溜了，以后再补（挖坑

标签：重构,le,return,int,Kruskal,笔记,maxn
From： https://www.cnblogs.com/663B/p/16816270.html

相关文章

  • kubernetes笔记-2-基本操作
    一、kubectl的基本操作语法：  kubectl[command][type][name][flags]语法说明：  command：对资源执行相应操作的子命令，如：get、create、delete、run等；  type：要操......
  • 模拟退火学习笔记
    虽然说考前不应该碰这些随机化算法，容易影响思考，但是还是写一写吧，对于一些问题还是很好用的。概念什么是模拟退火。一句话解释，我们从一个旧状态随机出一个新状态，要从旧状......
  • SpringCloud-02 Eureka学习笔记
    ​一、Eureka简介1、什么Eureka？Netflix在涉及Eureka时，遵循的就是API原则.Eureka是Netflix的有个子模块，也是核心模块之一。Eureka是基于REST的服雾，用于定位服雾，以实现云端中......
  • 敏捷（SCRUM）学习笔记 1 —— 《SCRUM敏捷软件开发》 (美)Mike Cohn）著 清华大学出版社2
     关键词：《SCRUM敏捷软件开发》——(美)MikeCohn著，清华大学出版社2011版，读书笔记（一） 第一章  为什么敏捷转型难（但值得） 为什么转型困难一、变化来得比以往更快......
  • Vue 笔记6 模板分离
                   ......
  • 深度学习入门书籍笔记
    title:深度学习入门书籍笔记date:2022-08-0212:57:39mathjax:truetags:深度学习python第3章神经网络3.2激活函数将输入信号的总和转换为输出信号，一般称为......
  • SpringCloud-01 Rest学习环境搭建笔记
    @​​TOC​​写在前面由于刚开始创建第一个项目的时候，出现了版本冲突问题，所以最后没有启动下来，但是我大部分的图片都是用的第一次的，所以大家可以主观的把图片中父项目Spring......
  • SpringCloud-03 Netflix Ribbon学习笔记
    @​​TOC​​一、Ribbon简介1、什么是Ribbon？SpringCloudRibbon是基于NetflixRibbon实现的一套客户端负载均衡的工具,它可以很好地控制HTTP和TCP客户端的行为。简单的......
  • Jupyter笔记[1]-MNIST手写数字识别
    jupyter集成了常用python框架docker的jupyter/tensorflow-notebook镜像包含了tensorflow,scipy等主流框架我们还可以在Jupyter内打开终端，用pip或其他工具安装软件包除了......
  • 【学习笔记】Filter 过滤器
    Filter过滤器过滤器的作用：用来过滤网站的数据（处理中文乱码、登录验证....）过滤器加在服务器和servlet、jsp、静态资源中间，用来过滤服务器的请求我们以处理乱码问题为例......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99