题目链接
bzoj3545: [ONTAK2010]Peaks
题解
对于<=x的边集构成多个联通块，对于询问离线，维护单调递增的<=x的联通块，每次线段树合并，查询k大。
代码
/*
苟活者在淡红的血色中，会看见依稀的微茫
*/
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}
while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar();
return x * f;
}
const int maxn = 250007;
struct node {
int u,v,w;
bool operator < (const node & a) const {
return w < a.w;
}
} edge[(maxn << 1) + 7];
struct Query {
int u,v,k,id;
bool operator < (const Query & a) const {
return v < a.v;
}
}q[maxn * 2] ;
#define lc son[x][0]
#define rc son[x][1]
int n,m,Q,cnt;
int h[maxn],ans[maxn * 2],sz[maxn * 20],son[maxn * 20][2],tot = 0;
void insert(int &x ,int l,int r,int rk) {
sz[x = ++ tot] = 1;
if(l == r) return ;
int mid = l + r >> 1;
if(rk <= mid) insert(lc,l,mid,rk);
else insert(rc,mid + 1,r,rk);
}
int Merge(int x,int y) {
if(!x || !y) return x ^ y;
lc = Merge(lc,son[y][0]);rc = Merge(rc,son[y][1]);
sz[x] += sz[y];sz[y] = 0; return x;
}
int Query(int x,int l,int r,int k) {
if(l == r) return l;
int lz = sz[lc],mid = l + r >> 1;
if(k <= lz) return Query(lc,l,mid,k);
else return Query(rc,mid + 1,r,k - lz);
}
int fa[maxn],ref[maxn];
int find(int x ) {
if(fa[x] != x)fa[x] = find(fa[x]);
return fa[x];
}
int root[maxn * 15];
void merge(int x,int y) {
int r1 = find(x),r2 = find(y);
if(r1 == r2) return;
fa[r2] = r1,root[r1] = Merge(root[r1],root[r2]);
}
int query(int x,int k) {
int rt = find(x);
return sz[root[rt]] < k ? - 1 : ref[Query(root[rt],1,cnt,sz[root[rt]] - k + 1)];
}
int main() {
n = read(),m = read(),Q = read();
for(int i = 1;i <= n;++ i) ref[i] = h[i] = read(),fa[i] = i;
std::sort(ref + 1, ref + n + 1),cnt = 1;
for(int i = 2;i <= n;++ i) if(ref[i] != ref[i - 1]) ref[++ cnt] = ref[i];
for(int i = 1;i <= n;++ i) insert(root[i],1,cnt,lower_bound(ref + 1,ref + cnt + 1,h[i]) - ref);
for(int i = 1;i <= m;++ i) edge[i].u = read(),edge[i].v = read(), edge[i].w = read();
std::sort(edge + 1,edge + m + 1);
for(int i = 1;i <= Q;++ i)
q[i].u = read(),q[i].v = read(),q[i].k = read(),q[i].id = i;
std::sort(q + 1,q + Q + 1);
for(int i = 1,now = 1; i <= Q;++ i) {
while(now <= m && edge[now].w <= q[i].v) merge(edge[now].u,edge[now].v),++ now;
ans[q[i].id] = query(q[i].u,q[i].k);
}
for(int i = 1;i <= Q;++ i) printf("%d\n",ans[i]);
return 0;
}
转载于:https://www.cnblogs.com/sssy/p/9354919.html
