bzoj3545: [ONTAK2010]Peaks

題目連結

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