P4197 Peaks [Kruskal 重构树 + 主席树]

本文主要是介绍P4197 Peaks [Kruskal 重构树 + 主席树]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

从小到大排, kruskal重构 , 每次倍增找到值刚好小于等于要求的点 , 问题转化为子树内的第k大

静态子树k大, 不就是主席树吗

#include<bits/stdc++.h>
#define N 200050
#define M 500050
using namespace std;int first[N],next[M],to[M],tot;struct Node{int u,v,w;}E[M];
bool cmp(Node a,Node b){return a.w<b.w;}struct Tree{int ls,rs,val;}t[N*40];
int rt[N],siz,res;int n,m,q,cnt,h[N],b[N];
int father[N]; 
int find(int x){return x==father[x]?x:father[x]=find(father[x]);}
int fa[N][22],val[N],st[N],ed[N],sign;int read(){int cnt=0; char ch=0;while(!isdigit(ch))ch=getchar();while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();return cnt;
}void add(int x,int y){next[++tot]=first[x],first[x]=tot,to[tot]=y;}void Kruskal(){sort(E+1,E+m+1,cmp); cnt=n;for(int i=1;i<=m;i++){int x=E[i].u , y=E[i].v;int fx = find(x), fy = find(y);if(fx!=fy){val[++cnt] = E[i].w;father[fx] = father[fy] = cnt;add(cnt,fx); add(cnt,fy);}} 
}/*----------------------------------主席树-------------------------------------*/
void Build(int &x,int l,int r){x=++res;if(l==r){ t[x].val = 0; return;}int mid = (l+r) >> 1;Build(t[x].ls, l, mid);Build(t[x].rs, mid+1, r);
} 
void Insert(int &x,int last,int l,int r,int pos){x = ++res;t[x].ls = t[last].ls, t[x].rs = t[last].rs;t[x].val = t[last].val + 1; if(l==r) return;int mid = (l+r) >> 1;if(pos<=mid) Insert(t[x].ls, t[last].ls, l, mid, pos);else Insert(t[x].rs, t[last].rs, mid+1, r, pos);
}
int Quary(int x,int y,int l,int r,int k){if(l==r) return l;int mid = (l+r) >> 1;int tmp = t[t[y].rs].val - t[t[x].rs].val;if(tmp >= k) return Quary(t[x].rs,t[y].rs,mid+1,r,k);else return Quary(t[x].ls,t[y].ls,l,mid,k-tmp); 
}
void dfs(int u,int f){fa[u][0] = f;for(int i=1;i<=20;i++)fa[u][i] = fa[fa[u][i-1]][i-1];st[u] = ++sign;if(u<=n) Insert(rt[sign],rt[sign-1],1,siz,h[u]);else rt[sign] = rt[sign-1];for(int i=first[u];i;i=next[i]){int t=to[i]; dfs(t,u);} ed[u] = sign;
}
int main(){n=read(),m=read(),q=read();for(int i=1;i<=n*2;i++) father[i]=i;for(int i=1;i<=n;i++) h[i] = b[i] = read();sort(b+1,b+n+1); siz = unique(b+1,b+n+1) - (b+1);for(int i=1;i<=n;i++) h[i] = lower_bound(b+1,b+siz+1,h[i]) - b;for(int i=1;i<=m;i++){E[i].u=read(),E[i].v=read(),E[i].w=read();} Kruskal();  Build(rt[0],1,siz);dfs(cnt,0);while(q--){int v=read(),x=read(),k=read();for(int i=20;i>=0;i--)if(fa[v][i] && val[fa[v][i]]<=x) v = fa[v][i];int tmp1 = rt[st[v]-1], tmp2 = rt[ed[v]];if(t[tmp2].val - t[tmp1].val < k){ printf("-1\n"); continue;} int ans = Quary(tmp1, tmp2, 1, siz, k);printf("%d\n",b[ans]);} return 0;
}

 

这篇关于P4197 Peaks [Kruskal 重构树 + 主席树]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---