Codeforces Round #223 (Div. 1) B. Sereja and Tree

問題

codeforces.com

解法

この問題では N, M が比較的小さいので, 一つのクエリにつき O(N log N) 程度で処理できれば AC します。

まず, 7000 行目で頂点がいくつぐらいあるのかを確認してみましょう。プログラムに計算させると 109315 個であるとわかりました。
type 2 のクエリに対しては, 今までの type 1 のクエリそれぞれに対して, 「level t の v 番目の頂点を根とする部分木が, 区間 [l, r] を含んでいるか」というのを判定します。
左から v 番目の頂点から, 深さ d だけ降りると, 左から何番目まで v の部分木の頂点の右端になるか(f(v, d) とする), というのは, v と d のみの関数です。これに注目すると, ダブリングのテクニックで f(v, d) は O(log d) で計算できます。parent[k][v] = (v から 2^k だけ降りた時, v の部分木の右端はいくつになるか)というのを前準備で求めまて(上で言ったことにより, v の上限は 1.1*10^5 ぐらいで OK) d に対してほげするやつです。

f(v-1, d), f(v, d) の分布がいい感じになっていたら集合に値を加えます。

const int MAX = 120000;
const int MAXQ = 7070;
int parent[15][MAX];

int level[MAXQ], L[MAXQ], R[MAXQ], X[MAXQ];

int calc(int v, int d) {
    for (int i = 15-1; i >= 0; i--) {
        if (d&(1<<i)) v = parent[i][v];
    }
    return v;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 0; i < MAX; i++) {
        int tmp = 1, next = i;
        while (tmp <= i) {
            next++;
            tmp *= 2;
        }
        parent[0][i] = next;
    }
    for (int i = 0; i < 15-1; i++) {
        for (int j = 0; j < MAX; j++) {
            if (parent[i][j] > MAX) continue;
            else parent[i+1][j] = parent[i][parent[i][j]];
        }
    }
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            cin >> level[cnt] >> L[cnt] >> R[cnt] >> X[cnt];
            cnt++;
        } else {
            int t, v;
            cin >> t >> v;
            set<int> S;
            for (int j = 0; j < cnt; j++) {
                int d = level[j]-t;
                if (d < 0) continue;
                int t1 = calc(v-1, d), t2 = calc(v, d);
                if (t1+1 <= R[j] && L[j] <= t2) S.insert(X[j]);
            }
            cout << S.size() << endl;
        }
    }
    return 0;
}