【bzoj3545】peaks

离线一下，动态开点+线段树合并，然后权值线段树上询问kth即可。

#include<bits/stdc++.h>

const int N=;

const int M=*;

using namespace std;

int n,m,q,ans[N],rt[N],a[N],fa[N],cnt=;

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

struct Edge{

    int u,v,w;

    bool operator <(const Edge &x)const{return w<x.w;}

    inline void init(){u=read();v=read();w=read();}

}G[N];

struct Query{

    int v,x,k,id;

    inline void init(int i){v=read();x=read();k=read();id=i;}

    bool operator < (const Query &a)const{return x<a.x;}

}Q[N];

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

struct Segment_Tree{

    int lc[M],rc[M],val[M];

    void ins(int &o,int l,int r,int q){

        if(!o)o=++cnt;val[o]++;

        if(l==r)return;int mid=(l+r)>>;

        if(q<=mid)ins(lc[o],l,mid,q);

        else ins(rc[o],mid+,r,q);

    }

    int merge(int x,int y,int l,int r){

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

        if(l==r){val[x]+=val[y];return x;}

        int mid=(l+r)>>;

        lc[x]=merge(lc[x],lc[y],l,mid);

        rc[x]=merge(rc[x],rc[y],mid+,r);

        val[x]=val[lc[x]]+val[rc[x]];

        return x;

    }

    int kth(int o,int l,int r,int q){

        if(l==r)return l;

        int mid=(l+r)>>;

        if(val[rc[o]]>=q)return kth(rc[o],mid+,r,q);

        return kth(lc[o],l,mid,q-val[rc[o]]);

    }

}T;

inline void uni(int u,int v){

    int x=find(u),y=find(v);

    if(x==y)return;

    rt[x]=T.merge(rt[x],rt[y],,1e9);

    fa[y]=x;

}

int main(){

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

    for(int i=;i<=n;i++){

        a[i]=read();fa[i]=i;T.ins(rt[i],,1e9,a[i]);

    }

    for(int i=;i<=m;i++)G[i].init();

    sort(G+,G+m+);

    for(int i=;i<=q;i++)Q[i].init(i);

    sort(Q+,Q+q+);

    for(int i=,j=;i<=q;i++){

        while(j<=m&&G[j].w<=Q[i].x)uni(G[j].u,G[j].v),++j;

        int t=rt[find(Q[i].v)];

        ans[Q[i].id]=T.val[t]>=Q[i].k?T.kth(t,,1e9,Q[i].k):-;

    }

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

}