2270-The Lth Number

解法

セグメント木を永続データー構造化し，その上で二分探索する．
割と遅め．

実装(C++)

#include <vector>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
struct Persistent_Segtree{
  int n;
  struct Node{
    Node *left,*right;
    int value;
    Node(){
      left=right=0;value=0;
    }
  };
  vector<Node> roots;
  void dfs(Node *node,int left,int right){
    if(right-left==1)return;
    node->left=new Node();
    node->right=new Node();
    dfs(node->left,left,(left+right)/2);
    dfs(node->right,(left+right)/2,right);
  }
  Persistent_Segtree(int n){
    int N=1;
    while(N<=n){
      N<<=1;
    }
    this->n=N;
    Node root;
    dfs(&root,0,N);
    roots.push_back(root);
  }
  void add_term(Node *node,int l,int r,int x,int k){
    if(l<=x&&x<r){
      node->value+=k;
      if(r-l==1)return;
      if(x<(l+r)/2){
        Node tmp=*node->left;
        node->left=new Node();
        *node->left=tmp;
        add_term(node->left,l,(l+r)/2,x,k);
      }else{
        Node tmp=*node->right;
        node->right=new Node();
        *node->right=tmp;
        add_term(node->right,(l+r)/2,r,x,k);
      }
    }
  }
  int add(int x,int k,int target=-1){
    if(target==-1)target=roots.size()-1;
    Node rts;
    rts=roots[target];
    add_term(&rts,0,n,x,k);
    roots.push_back(rts);
    return roots.size()-1;
  }
  int sum(int k,int l,int r){
    return sum(&roots[k],l,r,0,n);
  }
  int sum(Node *node,int l,int r,int L,int R){
    if(l<=L&&R<=r)return node->value;
    if(r<=L||R<=l)return 0;
    return sum(node->left,l,r,L,(L+R)/2)+sum(node->right,l,r,(L+R)/2,R);
  }
};
int readint(){
  int x;
  scanf("%d",&x);
  return x;
}
int val[100000];
int v_[100000];
int N,Q;
vector<int> G[100000];
int parent[18][100000];
int depth[100000];
void dfs(int s,int b,int d=0){
  parent[0][s]=b;
  depth[s]=d;
  for(int i=0;i<(int)G[s].size();i++){
    if(G[s][i]==b)continue;
    dfs(G[s][i],s,d+1);
  }
}
 
void init(){
  for(int i=1;i<log2(N)+1;i++){
    for(int j=0;j<N;j++){
      if(parent[i-1][j]!=-1){
        parent[i][j]=parent[i-1][parent[i-1][j]];
      }
    }
  }
}
 
int getLCA(int x,int y){
  if(depth[x]<depth[y])return getLCA(y,x);
  int d=depth[x]-depth[y];
  for(int i=0;i<log2(N)+1;i++){
    if(d>>i&1)x=parent[i][x];
  }
  if(x==y)return x;
  for(int i=log2(N);i>=0;i--){
    if(parent[i][x]!=parent[i][y]){
      x=parent[i][x];
      y=parent[i][y];
    }
  }
  return parent[0][x];
}
int no[1000000];
 
void dfs_d(int n,int b,Persistent_Segtree &bit){
  no[n]=bit.add(lower_bound(v_,v_+N,val[n])-v_,1,no[b]);
  for(int i=0;i<(int)G[n].size();i++){
    if(G[n][i]==b)continue;
    dfs_d(G[n][i],n,bit);
  }
     
}
int main(){
  N=readint();
  Q=readint();
  memset(parent,-1,sizeof(parent));
  for(int i=0;i<N;i++)v_[i]=val[i]=readint();
  for(int i=0;i<N-1;i++){
    int a,b;
    a=readint()-1;
    b=readint()-1;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  Persistent_Segtree bit(N);
  dfs(0,-1);
  sort(v_,v_+N);
  dfs_d(0,0,bit);
  init();
  for(int i=0;i<Q;i++){
    int l,r,k;
    scanf("%d%d%d",&l,&r,&k);
    l--;r--;
    k--;
    int tar=getLCA(l,r);
    int tar2=getLCA(l,r);
     
    tar=parent[0][tar];
    int low=-1,high=N-1;
    while(high>low+1){
      int mid=(low+high)/2;
      int tmp=bit.sum(no[r],0,mid+1)+bit.sum(no[l],0,mid+1)-bit.sum(no[tar2],0,mid+1);
      if(tar>=0){
        tmp-=bit.sum(no[tar],0,mid+1);
      }
      if(tmp>k){
        high=mid;
      }else{
        low=mid;
      }
    }
    printf("%dn",v_[high]);
  }
}