![解説
? count(l,r,x,y)クエリ
? 分割した区間ごとに0～9のそれぞれの個数がわか
れば良い
? 各区間に要素数10の配列A[10]をもたせる
? A[i]にはその区間にあるiの個数を格納
? その区間のx～yの個数の和はA[x]+…+A[y]](https://image.slidesharecdn.com/umczjozswkmnk8uxql7z-signature-d348f6c041f3b431a8e401f4ac8c0156632525bda204eb7b3cfbdb879d4dd61d-poli-170327125740/85/RUPC2017-I-5-320.jpg)
![解説
? change(l,r,x,y)クエリ
? 各区間のAの再計算はA[y]+=A[x],A[x]=0（x!=y）
? [l,r)に入るの全ての区間についてやってたら遅い
? O(log n)くらいでやりたい
? 遅延評価する（自明）
? じゃあどうやって変更を子に伝搬させる？](https://image.slidesharecdn.com/umczjozswkmnk8uxql7z-signature-d348f6c041f3b431a8e401f4ac8c0156632525bda204eb7b3cfbdb879d4dd61d-poli-170327125740/85/RUPC2017-I-6-320.jpg)
![解説
? change(l,r,x,y)クエリ
? 遅延評価にもやっぱり要素数10の配列B[10]を使う
? B[i] := iの変更後の数字
? B[i]=xであるような全てのB[i]の中身をyにする
? Aの更新はA [B[i]]+=A[i]（A : 更新後のA）
? Bの変化した部分をうまく子に伝搬](https://image.slidesharecdn.com/umczjozswkmnk8uxql7z-signature-d348f6c041f3b431a8e401f4ac8c0156632525bda204eb7b3cfbdb879d4dd61d-poli-170327125740/85/RUPC2017-I-7-320.jpg)
![解説
? ここまで数列で考えてきたが、木の場合は？
? 木を数列に落とし込むテクニック＝ Euler-Tour
? 根からのDFSでの訪問順に頂点を並べる
? 今回は最初の訪問の順序と部分木の大きさがわかればOK
? count(r,x,y)→count(ord[r],ord[r]+subsz[r],x,y)
? change(r,x,y)も同様](https://image.slidesharecdn.com/umczjozswkmnk8uxql7z-signature-d348f6c041f3b431a8e401f4ac8c0156632525bda204eb7b3cfbdb879d4dd61d-poli-170327125740/85/RUPC2017-I-11-320.jpg)
搁鲍笔颁2017:滨解説
- 2. 問題概要 ? 頂点数nの木が与えられる ? 各頂点は0～9のいずれかの数字を一つだけもつ ? 以下の2種類のクエリを合計q個処理せよ ? count(r,x,y): T(r)にあるx～yの個数の和を求める ? change(r,x,y): T(r)にあるxを全てyにする ? T(r) … 頂点rを根とした部分木
- 4. 解説 ? 最終的にはセグ木で殴るので、数列で考える ? 数列の長さはn ? 各要素は0～9のいずれかの数字を一つだけもつ ? count(l,r,x,y): [l,r)にあるx～yの個数の和を求める ? change(l,r,x,y): [l,r)にあるxを全てyにする
- 5. 解説 ? count(l,r,x,y)クエリ ? 分割した区間ごとに0～9のそれぞれの個数がわか れば良い ? 各区間に要素数10の配列A[10]をもたせる ? A[i]にはその区間にあるiの個数を格納 ? その区間のx～yの個数の和はA[x]+…+A[y]
- 6. 解説 ? change(l,r,x,y)クエリ ? 各区間のAの再計算はA[y]+=A[x],A[x]=0（x!=y） ? [l,r)に入るの全ての区間についてやってたら遅い ? O(log n)くらいでやりたい ? 遅延評価する（自明） ? じゃあどうやって変更を子に伝搬させる？
- 7. 解説 ? change(l,r,x,y)クエリ ? 遅延評価にもやっぱり要素数10の配列B[10]を使う ? B[i] := iの変更後の数字 ? B[i]=xであるような全てのB[i]の中身をyにする ? Aの更新はA [B[i]]+=A[i]（A : 更新後のA） ? Bの変化した部分をうまく子に伝搬
- 8. 解説 ? 伝搬の例 0 2 4 3 4 6 1 7 1 0 2 5 3 5 6 7 親 子
- 9. 解説 ? 子のBの値をインデックスとして親のBを参照 0 2 4 3 4 6 1 7 1 0 2 5 3 5 6 7 親 子
- 10. 解説 ? 親のBから子へ値を伝搬 ? 伝搬後、親のBは数列0,1,...,N-1に書き換えておく 0 2 4 3 4 6 1 7 2 0 4 6 3 6 7 7 親 子
- 11. 解説 ? ここまで数列で考えてきたが、木の場合は？ ? 木を数列に落とし込むテクニック＝ Euler-Tour ? 根からのDFSでの訪問順に頂点を並べる ? 今回は最初の訪問の順序と部分木の大きさがわかればOK ? count(r,x,y)→count(ord[r],ord[r]+subsz[r],x,y) ? change(r,x,y)も同様
- 12. まとめ ? 与えられた木からDFSの訪問順序で数列をつくる ? 上で得た数列とSegment Treeを対応付ける ? 遅延評価で範囲更新をしながら答えを求める ? 時間計算量: O(n + q log n) ? 空間計算量に注意！
- 13. ジャッジ解 ? dohatsu（C++）: 148 lines ? haji（C++）: 101lines ? kawabys（C++）: 86 lines ? uku（C++）: 122 lines
- 14. 結果 ? First Submission ? Online: pekempey 41 min ? First Accepted ? Online: pekempey 41 min ? Success Rate: 25.00 % (4/16)