洛谷P4197 Peaks(Kruskal重构树 主席树)

概述本文章向大家介绍洛谷P4197 Peaks(Kruskal重构树 主席树)，需要的朋友可以参考一下

题意

题目链接

往后中文题就不翻译了qwq

Sol

又是内存溢出题。。出题人这是强行把Kruskal重构树和主席树拼一块了啊。。

首先由于给出的限制条件是<=x，因此我们在最小生成树上走一定是最优的。

考虑把Kruskal重构树建出来，重构树上每个新的节点代表的是边权，同时用倍增数组维护出跳2^i步后能走到的值最大的节点

这样，该节点的整个子树内的节点都是可以走到的。

用dfs序+主席树维护出每个节点内H的值，直接查第K大即可

需要注意的是，对于不在原树内的节点，H要设的非常小，或者不插入，以免对答案产生影响

同时H需要离散化

写+调用了整两个小时，，自己的码力还是太弱了qwq

#include

#include

#include

#include

#define Pair pair

#define MP(x,y) make_pair(x,y)

#define fi first

#define se second

using namespace std;

const int MAXN = 1e6 + 10;

inline int read() {

char c = getchar(); int x = 0,f = 1;

while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();

return x * f;

}

int N,M,Q,H[MAXN],date[MAXN],tot,num = 0;

struct Edge {

int u,v,w;

bool operator < (const Edge &rhs) const {

return w < rhs.w;

}

}E[MAXN];

voID AddEdge(int x,int y,int z) {E[++num] = (Edge) {x,y,z};}

int fa[MAXN],fd[MAXN][22],dis[MAXN][22];

int find(int x) {

if(fa[x] == x) return fa[x];

else return fa[x] = find(fa[x]);

}

int unionn(int x,int y) {fa[x] = y;}

vector v[MAXN];

voID Build() {

for(int i = 1; i <= (N << 1); i++) fa[i] = i;

sort(E + 1,E + num + 1);

for(int i = 1; i <= num; i++) {

int x = E[i].u,y = E[i].v,w = E[i].w;

int fx = find(x),fy = find(y);

if(fx == fy) continue;

tot++;

fa[fx] = tot; fa[fy] = tot;

v[fx].push_back(tot); v[fy].push_back(tot);

v[tot].push_back(fx); v[tot].push_back(fy);

dis[fx][0] = w; dis[fy][0] = w;

fd[fx][0] = tot; fd[fy][0] = tot;

if(tot == 2 * N - 1) break;

}

}

int ls[MAXN * 30],rs[MAXN * 30],Tsiz[MAXN * 30],root[MAXN],cnt,siz[MAXN],dfn[MAXN],tra[MAXN];

voID dfs(int x,int fa) {

dfn[x] = ++cnt; tra[dfn[x]] = x; siz[x] = 1;

for(int i = 0; i < v[x].size(); i++) {

int to = v[x][i];

if(to == fa) continue;

dfs(to,x);

siz[x] += siz[to];

}

}

voID update(int k) {

Tsiz[k] = Tsiz[ls[k]] + Tsiz[rs[k]];

}

voID Insert(int &k,int p,int val,int l,int r) {

k = ++cnt;

ls[k] = ls[p]; rs[k] = rs[p]; Tsiz[k] = Tsiz[p];

if(val == -1) return ;

Tsiz[k]++;

if(l == r) return ;

int mID = l + r >> 1;

if(val <= mID) Insert(ls[k],ls[p],val,l,mID);

else Insert(rs[k],rs[p],mID + 1,r);

update(k);

}

voID MakeTree() {

cnt = 0;

for(int i = 1; i <= tot; i++)

Insert(root[i],root[i - 1],H[tra[i]],1,N);

}

voID Jump() {

for(int j = 1; j <= 21; j++) {

for(int i = 1; i <= tot; i++) {

fd[i][j] = fd[fd[i][j - 1]][j - 1];

dis[i][j] = max(dis[fd[i][j - 1]][j - 1],dis[i][j - 1]);

}

}

}

int Get(int x,int val) {

for(int i = 21; i >= 0; i--)

if(dis[x][i] <= val && fd[x][i] != 0)

x = fd[x][i];

return x;

}

int query(int lt,int rt,int k,int r) {

int used = Tsiz[rs[rt]] - Tsiz[rs[lt]];

if(l == r) {

if(Tsiz[rt] - Tsiz[lt] < k) return -1;

else return l;

}

int mID = l + r >> 1;

if(k <= used) return query(rs[lt],rs[rt],k,r);

else return query(ls[lt],ls[rt],k - used,mID);

}

main() {

//freopen("1.in","r",stdin);

//freopen("a.out","w",stdout);

tot = N = read(); M = read(); Q = read();

memset(H,-1,sizeof(H));

for(int i = 1; i <= N; i++) H[i] = read(),date[i] = H[i];

sort(date + 1,date + N + 1);

int tmp = unique(date + 1,date + N + 1) - date - 1;

for(int i = 1; i <= N; i++) H[i] = lower_bound(date + 1,date + N + 1,H[i]) - date;

for(int i = 1; i <= M; i++) {

int x = read(),y = read(),z = read();

// v[x].push_back(MP(y,z));

// v[y].push_back(MP(x,z));

AddEdge(x,z); AddEdge(y,x,z);

}

Build();

dfs(tot,0);

MakeTree();

Jump();

while(Q--) {

int v = read(),x = read(),k = read();

int top = Get(v,x);

int l = dfn[top],r = dfn[top] + siz[top] - 1;

int ans = query(root[l],root[r],N);

if(ans == -1) printf("%dn",-1);

else printf("%dn",date[ans]);

}

return 0;

}

总结

以上是内存溢出为你收集整理的洛谷P4197 Peaks(Kruskal重构树 主席树)全部内容，希望文章能够帮你解决洛谷P4197 Peaks(Kruskal重构树 主席树)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。