笛卡尔树及克鲁斯卡尔重构树

笛卡尔树

好东西, 可以用于最大(小)值分治, 在(O(n))的时间复杂度内建出一个节点为区间最大值的树, 每次分治时走小区间可以保证(O(nlog_n))的复杂度

建树时维护极右链, 他的中序遍历即原序列

代码

#include<bits/stdc++.h>
using namespace std; 
const int N=1e5+10;
int n,v[N],fa[N],ls[N],rs[N];
int s[N],top;
void Tree() 
{
    for(int i = 1; i <= n; i ++)
	{
        scanf("%d",&v[i]);
        while(top && v[s[top]] > v[i])
        ls[i] = s[top], top --;
        fa[i] = s[top]; 
		fa[ls[i]] = i; 
        if(fa[i]) rs[fa[i]] = i;
        s[++ top] = i;
    }
}

克鲁斯卡尔重构树

就像跑最小生成树一般, 只是每次合并时新建一个节点t, 让它与两个连通块的代表点连边, t成为整个连通块的代表节点, 这样保证底下的边权小于上面的边权

最小瓶颈生成树:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std; 
const int N = 1005000;
const int fP = 1e9+7;
vector <int> v[N];
template <typename T>
void read(T &x) {
	x = 0; bool f = 0;
	char c = getchar();
	for (;!isdigit(c);c=getchar()) if (c=='-')f=1;
	for (;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
	if (f) x=-x;
}
int n, m, p;
int val[N], f[N], cnt;
int A, B, C, P, q;
int st[N][20], fir[N];
int find(int x) {
	if (x == f[x]) return x;
	return f[x] = find(f[x]);
}
struct node{
	int x, y, w;
	bool operator < (const node &i) const {
		return w < i.w;
	}
}ed[N];
inline int rnd() {
	return A = (A * B + C) % P;
}
ll a[N], ans, tot;
void dfs(int x) {
	a[++tot] = val[x], fir[x] = tot;
	for (int i = 0;i < v[x].size(); i++) {
		int y = v[x][i];
		dfs(y); a[++tot] = val[x];
	}
}
int lg[N], s, t;
void init(void) {
	lg[0] = -1;
	for (int i = 1;i <= tot; i++) 
		st[i][0] = a[i], lg[i] = lg[i>>1] + 1;
	for (int len = 1; (1 << len) <= tot; len++) 
		for (int l = 1;l + (1 << len) - 1 <= tot; l++) 
			 st[l][len] = max(st[l][len-1], st[l + (1<<(len-1))][len-1]);
}

int ask(int l,int r) {
	if (l > r) swap(l, r);
	int t = lg[r - l + 1];
	return max(st[l][t], st[r-(1<<t)+1][t]);
}
	
		 
int main() {
	read(n), read(m); cnt = n;
	for (int i = 1;i <= n*2; i++) f[i] = i;
	for (int i = 1;i <= m; i++) 
		read(ed[i].x), read(ed[i].y), read(ed[i].w);
	sort(ed + 1,ed + m + 1);
	for (int i = 1;i <= m; i++) {
		int fx = find(ed[i].x), fy = find(ed[i].y);
		if (fx == fy) continue;
		val[++cnt] = ed[i].w;
		v[cnt].push_back(fy); v[cnt].push_back(fx);
		f[fx] = f[fy] = cnt;
	}
	dfs(cnt); init();
	read(q); read(A), read(B), read(C), read(P);
	while (q--) {
		s = rnd() % n + 1, t = rnd() % n + 1;
		ans += ask(fir[s], fir[t]);
		if (ans > fP) ans -= fP;
	}
	cout << ans % fP << endl;
	return 0;
}