The L-th Number
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270
解説にあったみたいに永続を使いました。永続書くのは初めてです
二分探索木はこわいし建て方よくわかったなかったので、せぐつりー風にしました。
ノードごとにlogN個のノードを持って、左・右へのリンクは、
このノードで更新したか、それとも最後に更新されたもっとも近い親のノードはどこかを表します
木をたぐりながら二分探索できるってすごいなぁと思いました。
ソース載せようと思ったのですが、ごちゃごちゃ過ぎて訳分からない疑惑
ですがまあとりあえず載せます。解説書くと日がくれるので、見たい人はみてやってください
#include<cstring> #include<algorithm> #include<cstdio> #define REP(num,num2) for(int num=0;num<(int)(num2);++num) #define SZ(t) ((int)t.size()) #define pb push_back #define mp make_pair #define fr first #define sc second using namespace std; typedef pair<int,int> pi; int val[400005]; struct segtree{ int n; void init(int n_){ n=1; while(n<n_) n<<=1; REP(i,n*2) val[i]=0; } void add(int k,int a){ k+=n-1; val[k]+=a; while(k>0){ k=(k-1)/2; val[k]+=a; } } int query(int node){ return val[node]; } }; segtree sum; pair<int,pi> seg[100005][20];//inclusible int whorenew[400005]; int logn,n2; int n,q; int head[100005],nxt[200005],es[200005]; int num[100005],zip[100005]; int par[100005]; int par2[20][100005],depth[100005]; int prev[100005][20]; int zn; void dfs(int v,int p,int dep){ par2[0][v]=par[v]=p; depth[v]=dep; int l=0,r=n2; sum.add(num[v],1); int node=0; REP(i,logn){ seg[v][i].fr=sum.query(node); int md=(l+r)>>1; prev[dep][i]=whorenew[node]; whorenew[node]=v; if(num[v]<md){ seg[v][i].sc=mp(v,whorenew[node*2+2]); node=node*2+1; r=md; }else{ seg[v][i].sc=mp(whorenew[node*2+1],v); node=node*2+2; l=md; } } seg[v][logn].fr=sum.query(node); prev[dep][logn]=whorenew[node]; whorenew[node]=v; for(int i=head[v];i!=-1;i=nxt[i]){ int to=es[i]; if(to==p) continue; dfs(to,v,dep+1); } sum.add(num[v],-1); l=0;r=n2; node=0; REP(i,logn){ int md=(l+r)>>1; whorenew[node]=prev[dep][i]; if(num[v]<md){ node=node*2+1; r=md; }else{ node=node*2+2; l=md; } } whorenew[node]=prev[dep][logn]; } int get2(int rank,int a){ if(a==-1) return 0; int nxt=seg[a][rank].sc.fr; if(nxt==-1) return 0; int val=seg[nxt][rank+1].fr; return val; } void renewL(int rank,int& a){ if(a==-1) return; int nxt=seg[a][rank].sc.fr; a=nxt; } void renewR(int rank,int& a){ if(a==-1) return; int nxt=seg[a][rank].sc.sc; a=nxt; } int get(int a,int b,int c,int d,int L){ int l=0,r=n2; REP(i,logn){ int all=get2(i,a)+get2(i,b)-get2(i,c)-get2(i,d),md=(l+r)>>1; if(all>=L){ renewL(i,a); renewL(i,b); renewL(i,c); renewL(i,d); r=md; }else{ L-=all; renewR(i,a); renewR(i,b); renewR(i,c); renewR(i,d); l=md; } } return l; } int lca(int a,int b){ if(depth[a]>depth[b]) swap(a,b); int dif=depth[b]-depth[a]; REP(i,20) if(dif>>i&1) b=par2[i][b]; if(a==b) return a; for(int i=19;i>=0;--i) if(par2[i][a]!=par2[i][b]){ a=par2[i][a]; b=par2[i][b]; } return par2[0][a]; } int main(){ scanf("%d%d",&n,&q); memset(head,-1,sizeof(head)); REP(i,n){ int a;scanf("%d",&a); num[i]=zip[i]=a; } sort(zip,zip+n); zn=unique(zip,zip+n)-zip; REP(i,n){ num[i]=lower_bound(zip,zip+zn,num[i])-zip; } logn=0; while((1<<logn)<zn) ++logn; n2=(1<<logn); sum.init(zn); int cnt=0; REP(i,n-1){ int a,b;scanf("%d%d",&a,&b);--a;--b; nxt[cnt]=head[a];es[cnt]=b;head[a]=cnt++; nxt[cnt]=head[b];es[cnt]=a;head[b]=cnt++; } memset(whorenew,-1,sizeof(whorenew)); dfs(0,-1,0); REP(i,19) REP(j,n){ if(par2[i][j]==-1) par2[i+1][j]=-1; else par2[i+1][j]=par2[i][par2[i][j]]; } REP(i,q){ int a,b,L;scanf("%d%d%d",&a,&b,&L);--a;--b; printf("%d\n",zip[get(a,b,lca(a,b),par[lca(a,b)],L)]); } return 0; }