3545: [ONTAK2010]Peaks 平衡树，最小生成树

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=3545

离线询问，按照权值排个序

就是在克鲁斯卡尔时候维护个treap，到时候挨个查询一下就好了

nb的gzy说要要在线才是呢，nb

代码

/**************************************************************

    Problem: 3545

    User: gryz2016

    Language: C++

    Result: Accepted

    Time:8708 ms

    Memory:69660 kb

****************************************************************/

#include <iostream>

#include <ctime>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define ll long long

using namespace std;

const int N=1e5+7;

const int inf=0x3f3f3f3f;

int read() {

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

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

int ch[N*40][2],siz[N*40],cnt;

void build(int l,int r,int L,int &now) {

    if(!now) now=++cnt;

    siz[now]++;

    if(l==r) return;

    int mid=(l+r)>>1;

    if(L<=mid) build(l,mid,L,ch[now][0]);

    else build(mid+1,r,L,ch[now][1]);

}

int merge(int x,int y) {

    if(!x||!y) return x+y;

    siz[x]+=siz[y];

    ch[x][0]=merge(ch[x][0],ch[y][0]);

    ch[x][1]=merge(ch[x][1],ch[y][1]);

    return x;

}

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

    if(l==r) return l;

    int mid=(l+r)>>1;

    if(siz[ch[rt][0]]>=k) return query(l,mid,k,ch[rt][0]);

    else return query(mid+1,r,k-siz[ch[rt][0]],ch[rt][1]);

}

struct node {int u,v,q;}e[N*5];

bool cmp1(node a,node b) {return a.q<b.q;}

struct QQQ {int v,x,k,id;}Q[N*5];

bool cmp2(QQQ a,QQQ b) {return a.x<b.x;}

int n,m,q,a[N*5],f[N*5],ans[N*5],rt[N*5];

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

void uu(int x,int y) {

    if(x==y) return;

    rt[y]=merge(rt[x],rt[y]);

    f[y]=x;

}

int main() {

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

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

    n=read(),m=read(),q=read();

    for(int i=1;i<=n;++i) a[i]=read();

    for(int i=1;i<=m;++i) e[i].u=read(),e[i].v=read(),e[i].q=read();

    for(int i=1;i<=q;++i) Q[i].v=read(),Q[i].x=read(),Q[i].k=read(),Q[i].id=i;

    sort(e+1,e+1+m,cmp1);

    sort(Q+1,Q+1+q,cmp2);

    for(int i=1;i<=n;++i) f[i]=i,build(1,1e9,a[i],rt[i]);

    int js=1;

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

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

        int fx=find(e[i].u),fy=find(e[i].v);

        if(fx==fy) continue;

        while(Q[js].x<e[i].q&&js<=q) {

            int fa=find(Q[js].v);

            if(siz[rt[fa]]>=Q[js].k)

                ans[Q[js].id]=query(1,1e9,siz[rt[fa]]-Q[js].k+1,rt[fa]);

            js++;

        }

        uu(fx,fy);

    }

    while(Q[js].k<=e[n].q&&js<=q) {

        int fa=find(Q[js].v);

        if(siz[rt[fa]]>=Q[js].k)

            ans[Q[js].id]=query(1,1e9,siz[rt[fa]]-Q[js].k+1,rt[fa]);

        js++;

    }

    for(int i=1;i<=q;++i) printf("%d\n", ans[i]);

    return 0;

}