問題文: The L-th Number | Aizu Online Judge
想定解ではない計算量で解いたらしい。問題文は日本語なので省略。この記事、説明不足が多すぎるので注意。
解法
※僕がこの問題でやったHeavy-Light分割、適当なことしているので嘘っぽいです。信用しないでくたざい。本来きちんと最も深い頂点から優先して構築やったほうがよさそうです。(未確証) 訂正したのでたぶん大丈夫？
計算量: 多分 O（N log N + Q･(log N)^2）多分O（N log N + Q･(log N)^3）らしい。ついでにHL分割のソースも修正(02/21修正)
- 解説スライド読むべき。(no title)
- 前提: 与えられるものは明らかに木。適当な頂点を選び根付き木にする。
- 基本方針は、第一に(子,親)間を列として処理できるように構築する。
- 第二にクエリで与えられる頂点対(u,v)に関しそれらの最も近い共通祖先pを求めることで、(u,p)と(v,p)の2つの対についての列処理を行えるようにする
- 第三にどういう処理を行うかだけど、k番目の数字がxと仮定したときに、区間にx未満の値がk-1個あれば良い?(複数同じ要素があるときは誤魔化す)のでがんばって二分探索して求める。(これに慣れない人はまずPKU2104を解きましょう)
列として処理できるデータ構造の構築について
- Heavy-Light Decomposition *1と呼ばれるらしいものを使う。
- 実装の仕方だけど、
実際に再帰使って無向グラフから木を構築してる時、末端にたどり着いたら、そこから木を構築したあと、どの列にも所属してない頂点で最も深いものから親に登るように列をつくっていき、もし既に別の列に含まれるような頂点xに衝突したら、その列とxの所属する列をリンクする(という情報を持たせる)。
最も近い共通祖先(LCA)を求める方法
- ダブリングという手法を用いた二分探索。(蟻本上級編を読みましょう)
BITで列のある区間に含まれるx未満の数を求める方法
- セグメントツリーとかを使っても求めれるけど、BITの接点にソートした配列を情報として持たせておけば、さらにその配列を二分探索することで1からある位置まで連続した区間のx以下の数が求められる。任意の区間に関してこれを適用するには、[a,b]に含まれるx未満の数 = ([1,b]に含まれるx未満の数) - ([1,a-1]に含まれるx未満の数) という事実を用いればよい。
多分この解法は想定だとＴＬＥで、ＢＩＴを用いて定数倍を改善することで通せたんだと思う。
ソース
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; // グラフと深さ vector<int> graph[100000]; int parent[18][100000]; int depth[100000]; // Heavy-Light Decomposition 用 vector< vector<int> > pre; // 前処理用 vector< vector< vector<int> > > seg; // 実際にBITに使うデータが入っている int height[100000]; // height[i] = 頂点iが含まれる列でのiの位置。深さが大きいほどheight[i]も大きい。 int belong[100000]; // beling[i] = 頂点iが所属する列のインデックス int next[100000]; // next[列の番号] = 列構築してるときに衝突した頂点iが入る // ふつう int N,Q; int value[100000]; void genTree(int pos,int prev,int dep){ parent[0][pos] = prev; depth[pos] = dep; for(int i = 0 ; i < graph[pos].size() ; i++){ if(graph[pos][i] != prev) genTree(graph[pos][i],pos,dep+1); } } // Heavy-Light Decomposition している関数群 int idx[100000]; bool depth_sorting(const int &a,const int &b){ return depth[a] > depth[b]; // 降順 } int doLH(int pos,int num){ if(pos == -1 || belong[pos] != -1){ next[num] = pos; return 0; }else{ height[pos] = doLH(parent[0][pos],num) + 1; belong[pos] = num; pre[num].push_back(value[pos]); return height[pos]; } } //この関数では最も深さの大きい頂点から親に向かって列をつくっていく(そうしたら勝手に末端から列つくってくれる) int genLH(){ for(int i = 0 ; i < N ; i++) idx[i] = i; sort(idx,idx+N,depth_sorting); for(int i = 0 ; i < N ; i++){ if(belong[idx[i]] == -1){ pre.push_back(vector<int>(1,-1)); doLH(idx[i],pre.size()-1); } } } // LCAらへん // ダブリングを用いてある頂点jを2^i回巡ったときの親をparent[i][j]に格納しておく。 void genLCA(){ for(int i = 1 ; i < 18 ; i++){ for(int j = 0 ; j < N ; j++){ if(parent[i-1][j] != -1) parent[i][j] = parent[i-1][parent[i-1][j]]; } } } // genLCA()で作った情報を元にlog(N)でLCA求める。蟻本参照。深さを揃えてからそれでも頂点一致してなかったらほげっとする。 int getLCA(int x,int y){ if(depth[x] < depth[y]) swap(x,y); int d = depth[x] - depth[y]; for(int i = 0 ; i < 18 ; i++) if(d>>i&1) x = parent[i][x]; if(x==y) return x; for(int i = 17 ; i >= 0 ; i--){ if(parent[i][x] != parent[i][y]){ x = parent[i][x]; y = parent[i][y]; } } return parent[0][x]; } // BIT らへん void add(vector< vector<int> > &seg,int x,int v){ while(x < seg.size()){ seg[x].push_back(v); x += x & -x; } } int get(vector< vector<int> > &seg,int x,int k){ int ans = 0; while(x){ ans += lower_bound(seg[x].begin(),seg[x].end(),k) - seg[x].begin() - 1; x -= x & -x; } return ans; } // Heavy-Light Decompositionしたやつを使ったクエリ処理。 // 頂点from,toが同じ列に所属しているならその列での[height[to],hegith[from]]に含まれるk以下の数を計算し、 // もし違うなら、fromの所属する列で[1,height[from]]に含まれるk以下の数を計算し、衝突した列に登っていく。 int query(int from,int to,int k){ int A = belong[from] , B = belong[to]; if(A==B){ return get(seg[A],height[from],k) - get(seg[A],height[to]-1,k); }else{ return get(seg[A],height[from],k) + query(next[A],to,k); } } int uniq[100000] , U = 0; int main(){ memset(belong,-1,sizeof(belong)); memset(parent,-1,sizeof(parent)); memset(height,-1,sizeof(height)); scanf("%d%d",&N,&Q); for(int i = 0 ; i < N ; i++){ scanf("%d",&value[i]); uniq[U++] = value[i]; } for(int i = 0 ; i < N - 1 ; i++){ int a,b; scanf("%d%d",&a,&b); --a,--b; graph[a].push_back(b); graph[b].push_back(a); } sort(uniq,uniq+U); U = unique(uniq,uniq+U) - uniq; genTree(0,-1,0); genLH(); for(int i = 0 ; i < pre.size() ; i++){ seg.push_back( vector< vector<int> > (pre[i].size(),vector<int>(1,-1)) ); for(int j = 1 ; j < pre[i].size() ; j++) add(seg.back(),j,pre[i][j]); for(int j = 0 ; j < seg.back().size() ; j++) sort(seg.back()[j].begin(),seg.back()[j].end()); } genLCA(); for(int i = 0 ; i < Q ; i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); --a,--b; int l = 0 , r = U-1; int p = getLCA(a,b); while(l!=r){ int m = (l+r+1)/2; int g = query(a,p,uniq[m]) + query(b,p,uniq[m]) - (value[p] < uniq[m]); if(g < c) l = m; else r = m-1; } printf("%d\n",uniq[l]); } }
