【bzoj3545】[ONTAK2010]Peaks

2015.05.23 12:53 Sat | 8次阅读 | 旧日oi | 固定链接 | 源码

题目大意:给定一些点,每个点有权值,点和点之间有带权边,有一些询问,问从某一点开始只走边权<某个数所能达到的所有点中权值第k大的点。
点数10^5,边数询问数5*10^5
题解
不强制在线。。。
对询问按边权从小到大排序,然后和2733一样了……

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#define N 500005
using namespace std;
int n,m,Q,cnt,tot;
int h[100005],ans[N],fa[100005];
int root[100005],w[N],siz[N<<2],l[N<<2],r[N<<2],rnd[N<<2],val[N<<2],d[N<<2];
struct edge
{
    int u,v,c;
}e[N];
struct Que{
    int v,x,k,id;
}q[N];
bool cmp(const Que &a,const Que &b)
{
    return a.x<b.x;
}
bool cmp2(const edge &a,const edge &b)
{
    return a.c<b.c;
}
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void update(int k)
{
    siz[k]=siz[l[k]]+siz[r[k]]+w[k];
}
void lturn(int &k)
{
    int t=r[k];r[k]=l[t];l[t]=k;
    siz[t]=siz[k];update(k);k=t;
}
void rturn(int &k)
{
    int t=l[k];l[k]=r[t];r[t]=k;
    siz[t]=siz[k];update(k);k=t;
}
void insert(int &x,int v,int num)
{
    if(!x)
    {
        if(tot) x=d[tot--];
        else x=++cnt;
        val[x]=v;
        siz[x]=w[x]=num;
        l[x]=r[x]=0;
        rnd[x]=rand();
        return;
    }
    siz[x]+=num;
    if(val[x]==v) w[x]+=num;
    else if(val[x]<v)
    {
        insert(r[x],v,num);
        if(rnd[r[x]]<rnd[x]) lturn(x);
    }
    else
    {
        insert(l[x],v,num);
        if(rnd[l[x]]<rnd[x]) rturn(x);
    }
}
void combine(int &x,int y)
{
    insert(x,val[y],w[y]);
    if(l[y]) combine(x,l[y]);
    if(r[y]) combine(x,r[y]);
    d[++tot]=y;
}
int query(int x,int t)
{
    while(x)
    {
        if(siz[r[x]]>=t) x=r[x];
        else if(siz[r[x]]+w[x]>=t) return val[x];
        else t-=siz[r[x]]+w[x],x=l[x];
    }
    return -1;
}
int main()
{
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&h[i]);
        fa[i]=i;insert(root[i],h[i],1);
    }
    for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);
    for(int i=1;i<=Q;i++) scanf("%d%d%d",&q[i].v,&q[i].x,&q[i].k),q[i].id=i;
    sort(q+1,q+Q+1,cmp);sort(e+1,e+m+1,cmp2);
    for(int j=1,i=1;i<=Q;i++)
    {
        while(j<=m&&e[j].c<=q[i].x) 
        {
            int x=find(e[j].u),y=find(e[j].v);j++;
            if(x==y) continue;
            if(siz[root[x]]<siz[root[y]]) swap(x,y);
            combine(root[x],root[y]);fa[y]=x;
        }
        ans[q[i].id]=query(root[find(q[i].v)],q[i].k);
    }
    for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
    return 0;
}```