IOI 2009 Day2 Regions

問題

従属関係が根付き木な、N(1<=N<=200,000)人の所属する組織がある。各人は、R(1<=R<=50,000)個の地域のうちのいずれかに所属している。
Q(1<=Q<=200,000)個の、「2つの異なる地域r1,r2であって、Aがr1に所属し、Bがr2に所属し、AがBの根付き木の祖先であるようなものがいくつある？」というクエリが与えられる。クエリにオンラインで解答せよ。

解法

まず、R<=500のときは、最初にR*R通り全部を調べればよい。これにかかる計算量はO(RN)。適切に実装すれば余裕。これで30点。

次に、各地域から来る人が500人以下の場合。
根付き木に、BFSを用いて範囲を対応付ける。次のような手順。
range(i) :
　　left[i] = id++;
　　for(iの各子孫) range(子孫);
　　right[i] = id;

そして、頂点iに対して、[ left[i] , right[i] ) を対応する範囲として扱う。

これを行うと、どの頂点に対応する範囲も異なり、ある頂点に対応する範囲は、その子孫らに対応する範囲をすべて包含するようになる。
また、「left[i] <= left[j] < right[i] ⇔ jはiの子孫である」がわかる。

これを用いて、left[v1], right[v1], left[v2]を左から走査してやると、前処理O(N log N)、各クエリがO(p1+p2) (但し、p1,p2はクエリで与えられた両地域から来た人数)で解けるようになる。これと最初の解法をあわせて、70点。

そして、500人よりも多く人が来る地域がある場合。
この場合は、そんな地域を「特定地域」として特別視する。
この「特定地域」は大して存在しないことがわかる。
「特定地域」に対しては、特定地域->すべての地域、すべての地域->特定地域、というクエリーを予めすべて処理しておく。
これらは、先程と同様に、走査を行うことで、各特定地域に対してO(N)で計算できる。
その後、各クエリの処理は、特定地域を含まない場合は先程と同様に計算し、含む場合は事前に計算したデータを用いる。
これで100点が取れる。

コードは汚すぎるので晒せません。