Interrupt Array [Maximum-Cup 2018 E]

https://beta.atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_e

解法

https://beta.atcoder.jp/contests/maximum-cup-2018/submissions/2313040

今回は問題設定が複雑である。
こういう場合は何かしらシンプルに出来ないか考えよう。
　
まず操作Aについて考察してみる。
「1→121」とすると、2は必ず1に挟まれる形になる。
ここで1,3をすると「121→12131」であり、3も必ず1に挟まれる形になる。
ここで2,3をすると「121→12321」であり、3は必ず2に挟まれる形になる。ここで重要な事があり、『3も必ず1に挟まれる形になる』
つまり、ある種の親子関係が成立している。
よって「A i j」はiの子供にjを加えるという操作であるとも言える。
　
次に操作Bについて。
「B 2 3」について「12131」なら1があるし、「12321」なら何も無い。
これは「12131」は親子関係をたどって2から3に移った時に1を通るからであり、「12321」なら親子関係をたどって2から3に移った時に何も通らないからである。
よって、『親子関係としての距離-1』がそのまま答えになるということである。
　
以上の構造と重要な制約「iは数列に存在している数のみ、jは数列に存在しない数のなかで、最も小さい正の整数が出現」を元に考えると、これは木を構築していると分かる。
そのため、木を構築し、頂点間の距離が答えられれば解答できる。
まずは操作Aを全て実行し木を構築しよう。
その後に操作Bを全て実行し、「木の頂点間の距離-1」を答えていく。
木の頂点間の距離はLCAを使う。
（下の解法ではLCAを求めるのにHL分解を使用しているが、ダブリングの方が良く聞く）

int Q;
char C[201010]; int I[201010], J[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> Q;
    rep(q, 0, Q) cin >> C[q] >> I[q] >> J[q];
    rep(q, 0, Q) {
        I[q]--;
        J[q]--;
    }
 
    HLDecomposition hld(201010);
    rep(q, 0, Q) if (C[q] == 'A') hld.add(I[q], J[q]);
    hld.build();
 
    rep(q, 0, Q) if (C[q] == 'B') {
        int ans = hld.distance(I[q], J[q]) - 1;
        printf("%d\n", ans);
    }
}