P4197 Peaks（主席树+Kruskal重构树+倍增）

传送门

前缀知识

Kruskal重构树

题面

思路

看到困难值小于等于x就应该想到用Kruskal重构树了；

首先我们构建一颗Kruskal重构树，然后询问是问我们从某个点 u u u出发，不超过困难值 h h h，那么这个过程我们可以用倍增来解决；

接着看到第 k k k大，那么维护第 k k k大可以用很多数据结构；

假设当前不超过困难值 h h h这个点为 r t rt rt，因为每个 r t rt rt都不同，维护的区间也不同，因此是一个动态区间第k大，因此我们考虑主席树来解决；

我们用一个数组 r a n g e ( i ) ( 2 ) range(i)(2) range(i)(2)，其中 r a n g e ( i ) ( 0 ) range(i)(0) range(i)(0)表示子树 i i i的左边界， r a n g e ( i ) ( 1 ) range(i)(1) range(i)(1)表示右边界，其中是左开右闭的，方便相减；

然后在dfs的过程中就可以就可以维护出来了；

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10,M = 5e5 + 10;

int n,m,q,a[N];

vector<int> ve;

struct Node{
	int p1,p2,val;
	bool operator<(const Node o)const{
		return val < o.val;
	}
}K[M<<1];
struct Edge{
	int to,next,val;
}e[M];
int p[N],head[N],tot,pval[N];
int find(int x){
	if(x == p[x]) return x;
	return p[x] = find(p[x]);
}
int get(int x){
	return lower_bound(ve.begin(),ve.end(),x) - ve.begin() + 1;
}
void add(int u,int v){
	e[++tot].to = v;
	e[tot].next = head[u];
	head[u] = tot;
}
struct Tree{
	int lc,rc;
	int sum;//为了找第k大
}tr[N<<5];
int cnt;//主席树索引
void push_up(int p){
	tr[p].sum = tr[tr[p].lc].sum + tr[tr[p].rc].sum;
}
int root[N];//版本数组
int build(int l,int r){
	int p = ++cnt;
	if(l == r){
		return p;
	}
	int mid = (l+r) >> 1;
	build(l,mid);
	build(mid+1,r);
	return p;
}
int update(int p,int l,int r,int tar){
	int q = ++cnt;
	tr[q] = tr[p];
	if(l == r){
		++tr[q].sum;
		return q;
	}
	int mid = (l + r) >> 1;
	if(tar <= mid) tr[q].lc = update(tr[p].lc,l,mid,tar);
	else tr[q].rc = update(tr[p].rc,mid+1,r,tar);
	push_up(q);
	return q;
}
int query(int p,int q,int l,int r,int k){//返回的是值
	if(l == r){
		return ve[l-1];
	}
	int mid = (l+r) >> 1;
	int dif = tr[tr[q].rc].sum - tr[tr[p].rc].sum;
	//第k大，先看右树
	if(k <= dif){
		return query(tr[p].rc,tr[q].rc,mid+1,r,k);
	}
	else return query(tr[p].lc,tr[q].lc,l,mid,k-dif);
}
//range是左开右闭的，方便前缀和(主席树操作)
int range[N<<1][2];//range(i)(0)表示子树i的左边界，(1)表示右边界
int fa[N][25];//倍增数组
int pos;//我们定义的位置
void dfs(int u){
	for(int i=1;i<=20;++i)
		fa[u][i] = fa[fa[u][i-1]][i-1];
	range[u][0] = pos;
	if(head[u] == 0){//是叶子结点
		//在主席树上插入
		int x = get(a[u]);
		++pos;
		range[u][1] = pos;//左开右闭
		root[pos] = update(root[pos-1],1,ve.size(),x);
		return;
	}
	for(int i=head[u];i;i=e[i].next){
		int to = e[i].to;
		dfs(to);
	}
	range[u][1] = pos;
}
void EX_Kru(){
	for(int i=1;i<=2*n-1;++i) p[i] = i;
	int now = n;
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin >> u >> v >> w;
		K[i] = {u,v,w};
	}
	sort(K+1,K+1+m);
	for(int i=1;i<=m;++i){
		int u = K[i].p1,v = K[i].p2,w = K[i].val;
		int fu = find(u),fv = find(v);
		if(fu != fv){
			//merge
			p[fu] = p[fv] = ++now;
			pval[now] = w;
			add(now,fu),add(now,fv);
			fa[fu][0] = fa[fv][0] = now;
		}
	}
	//dfs前先建树
	root[0] = build(1,ve.size());
	//当前的树根是now
	dfs(now);
}
void solve(){
	cin >> n >> m >> q;
	for(int i=1;i<=n;++i)
		cin >> a[i],ve.push_back(a[i]);
	sort(ve.begin(),ve.end());
	ve.erase(unique(ve.begin(),ve.end()),ve.end());
	EX_Kru();
	while(q--){
		int u,h,k;//从点u出发，高度不超过h，第k大
		cin >> u >> h >> k;
		//倍增
		for(int i=20;i>=0;--i){
			int anc = fa[u][i];
			if(anc && pval[anc] <= h) u = anc;
		}
		//u现在是某个子树的根
		int L = range[u][0],R = range[u][1];//左开右闭
		if(tr[root[R]].sum - tr[root[L]].sum < k){
			//不足k个数
			cout << -1 << '\n';
		}
		else{
			cout << query(root[L],root[R],1,ve.size(),k) << '\n';
		}
	}
}

signed main(){
	std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}