[ONTAK2010]Peaks

题意

有n个山峰，m条有困难度的双向路径，m个询问求从x出发经过路径困难度<=y所能到达的第k高的山峰的高度。

$N \leq 10$

题解

可以想到将路径和询问按困难度从低到高排序，每次对于当前询问将能加的边加进去，然后再查找第k大，这样就变成了永无乡

基本上一样。就输出高度坑了一点

#include<bits/stdc++.h>
using namespace std;

const int maxn=500005;
int n,m,Q;
int root[maxn],belong[maxn];
int ans[maxn];
struct Splay{
  int fa,size,val,s[2];
}tr[maxn];
struct edge{
  int x,y,dis;
}e[maxn];
struct question{
  int start,dis,k,id;
}q[maxn];

template<class T>inline void read(T &x){
  x=0;char ch=getchar();
  while(!isdigit(ch)) ch=getchar();
  while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
}

bool cmp(edge a,edge b){
  return a.dis<b.dis;
}

bool cmp1(question a,question b){
  return a.dis<b.dis;
}

void update(int x){
  tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
}

void connect(int x,int y,int d){
  tr[x].fa=y;
  tr[y].s[d]=x;
}

int get(int x){
  return tr[tr[x].fa].s[1]==x;
}

void rotate(int x){
  int f=tr[x].fa,ff=tr[f].fa;
  int d1=get(x),d2=get(f);
  int cs=tr[x].s[d1^1];
  connect(x,ff,d2);
  connect(f,x,d1^1);
  connect(cs,f,d1);
  update(f);
  update(x);
}

void splay(int x,int go,int id){
  if(go==root[id]) root[id]=x;
  go=tr[go].fa;
  while(tr[x].fa!=go){
    int f=tr[x].fa;
    if(tr[f].fa==go) rotate(x);
    else if(get(x)==get(f)) {rotate(f);rotate(x);}
    else {rotate(x);rotate(x);}
  }
}

void insert(int id,int val,int x){
  int now=root[id];
  belong[x]=id;
  if(!now){
    root[id]=x;
    tr[x].size=1;
    tr[x].val=val;
    return ;
  }
  while(324){
    tr[now].size++;
    int o=val>tr[now].val;
    if(!tr[now].s[o]){
      tr[now].s[o]=x;
      tr[x]=(Splay){now,1,val,{0,0}};
      break;
    }
    now=tr[now].s[o];
  }
  splay(x,root[id],id);
}

void dfs(int x,int y){
  if(tr[y].s[0]) dfs(x,tr[y].s[0]);
  if(tr[y].s[1]) dfs(x,tr[y].s[1]);
  insert(x,tr[y].val,y);
}

void merge(int x,int y){
  int dx=root[belong[x]],dy=root[belong[y]];
  if(dx==dy) return ;
  if(tr[dx].size<tr[dy].size) swap(dx,dy);
  dfs(belong[dx],dy);
}

int query(int now,int k){
  if(tr[now].size<k) return -1;
  while(324){
    if(tr[tr[now].s[1]].size>=k) {now=tr[now].s[1];continue;}
    k-=tr[tr[now].s[1]].size;
    if(k==1) break;
    k--;
    now=tr[now].s[0];
  }
  splay(now,root[belong[now]],belong[now]);
  return tr[now].val;
}

int main(){
  read(n);read(m);read(Q);
  for(int i=1;i<=n;i++){
    int x;read(x);
    insert(i,x,i);
  }
  for(int i=1;i<=m;i++) read(e[i].x),read(e[i].y),read(e[i].dis);
  sort(e+1,e+m+1,cmp);
  for(int i=1;i<=Q;i++) read(q[i].start),read(q[i].dis),read(q[i].k),q[i].id=i;
  sort(q+1,q+Q+1,cmp1);
  int j=0;
  for(int i=1;i<=Q;i++){
    while(e[j+1].dis<=q[i].dis&&j<m) merge(e[j+1].x,e[j+1].y),j++;
    ans[q[i].id]=query(root[belong[q[i].start]],q[i].k);
  }
  for(int i=1;i<=Q;i++) printf("%d
",ans[i]);
}

View Code