http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp17Day2&pid=I
深さ優先探索をしたときの訪問順序によって頂点を並べると，ある頂点を根とする部分木に含まれる頂点が連続した区間に含まれる性質を使います。以下のページが詳しいです。
これを使えば，木を列として扱うことができるようになるので，列に対して以下の2つのクエリに答えられるようにすればよいです。
- count(l, r, x, y): [l, r) の中でx以上y以下の値をもつ要素の数を答える
- change(l, r, x, y): [l, r) の中で値がxである要素をすべてyに書き換える
厄介なのはchangeです。ここで注目するのは，各要素が取り得る値の範囲が0〜9の10段階と小さいことです。ここでchangeを置換として表現してみることを考えましょう。change(l, r, 0, 5) というクエリは (5 1 2 3 4 5 6 7 8 9) と表現できたり，change(l, r, 5, 8) というクエリは (0 1 2 3 4 8 6 7 8 9) と表現できたりします。また，置換は合成することができて，change(l, r, 0, 5) を適用してから change(l, r, 5, 8) を適用するようなクエリは (8 1 2 3 4 8 6 7 8 9) と表現できます。ここで重要なのは，置換という作用素はモノイド（結合法則が成り立ち，単位元が存在する）になっているので遅延セグメント木での作用として使うことができるということです。セグメント木に対して適用可能な操作については次の記事が詳しいです。
遅延セグメント木と同じ要領で範囲に対する置換を実装した平方分割を以下に示します。これを使うことで O(N+Q√N) で解けます。
typedef array<int, 10> ten; const int sqrtN = 512; ten multi(ten a, ten b) { ten ret; for (int i = 0; i < 10; i++) { ret[i] = b[a[i]]; } return ret; } struct SqrtDecomposition { int N, K; vector<int> data; // blockCount[k][z]: k番目のブロックの中で値がzである要素の数 vector<ten> blockCount; // 遅延された操作を持っているか？ vector<bool> lazyFlag; // 遅延された操作（置換） vector<ten> lazyUpdate; // 置換の単位元 ten initialValue; SqrtDecomposition(int n) : N(n) { K = (N + sqrtN - 1) / sqrtN; data.assign(K * sqrtN, 0); lazyFlag.assign(K, false); // 置換の単位元は (0 1 2 ... 7 8 9) for (int i = 0; i < 10; i++) { initialValue[i] = i; } lazyUpdate.assign(K, initialValue); ten zero; zero.fill(0); zero[0] = sqrtN; blockCount.assign(K, zero); } // k番目のブロックに対する遅延している操作を適用する void eval(int k) { if(lazyFlag[k]) { lazyFlag[k] = false; for (int i = k * sqrtN; i < (k + 1) * sqrtN; i++) { data[i] = lazyUpdate[k][data[i]]; } lazyUpdate[k] = initialValue; } } // [a, b) の範囲に対して置換を作用させる void put(int a, int b, ten perm) { for(int k = 0; k < K; ++k) { int l = k * sqrtN, r = (k + 1) * sqrtN; if(r <= a || b <= l) continue; if(a <= l && r <= b) { lazyFlag[k] = true; // 作用を合成する lazyUpdate[k] = multi(lazyUpdate[k], perm); // blockCountを更新 ten cnt; cnt.fill(0); for(int i = 0; i < 10; i++) { cnt[perm[i]] += blockCount[k][i]; } blockCount[k] = cnt; } else { eval(k); // 置換を適用 for(int i = max(a, l); i < min(b, r); ++i) { data[i] = perm[data[i]]; } // blockCountを数え直す blockCount[k].fill(0); for (int i = l; i < r; ++i) { blockCount[k][data[i]]++; } } } } // [a, b) の範囲でx以上y以下の値をもつ要素の数を返す int get(int a, int b, int x, int y) { int ret = 0; for(int k = 0; k < K; ++k) { int l = k * sqrtN, r = (k + 1) * sqrtN; if(r <= a || b <= l) continue; if(a <= l && r <= b) { for (int i = x; i <= y; i++) { ret += blockCount[k][i]; } } else { eval(k); for(int i = max(a, l); i < min(b, r); ++i) { if(x <= data[i] && data[i] <= y) { ret++; } } } } return ret; } };
