双対セグメント木をつくってみた【競技プログラミング】

はじめに

• 世の中に、双対セグメント木というモノがあるらしい。しかも、遅延セグ木のうち、区間変化クエリのみを残し、もとの区間取得クエリは削ったモノらしい。
• ならば、以前作った遅延セグ木から、簡単に作れると思ったので、作ってみた。
• とりあえず、比較表を載せておくね。

	セグ木	遅延セグ木	双対セグ木
区間変更クエリ	×	○	○
区間取得クエリ	○	○	×
点評価	○	○	○

※「点評価」は、区間取得クエリを「範囲」でなく「1要素のみ」に対して行う意味で使ってます。ノーマルのセグ木は、単なる配列の値取得だけどね。

遅延セグメント木から双対セグメント木を作る

• 評価対象となるtreeの葉部分と、遅延評価で使用するlazyのモノイドの型が一致するとは限らないけど、今回は一致すると仮定して作るね。
• 基となる遅延セグ木から、通常のセグ木部分である「区間取得クエリ(最大値クエリ)」を削り、遅延評価部分の「区間加算」を残したコード。

import Foundation

class /*LazySegTree*/DualSegTree {

    // 遅延セグ木設定場所
    // typealias Monoid = Int
    typealias ActMonoid = Int 
    // private var base: Monoid = -99 // maxクエリなので、負の大きい数
    private var lzBase: ActMonoid = 0 // 加算クエリなので、0
    // private var biOpe:(_ l:Monoid,_ r:Monoid)->Monoid = max // maxクエリなので、max
    private var lzOpe:(_ u:ActMonoid,_ d:ActMonoid)->ActMonoid = (+)
    // private var flz:(_ a:ActMonoid,_ m:Monoid,_ len:Int)->Monoid = {$0 + $1 + $2 * 0} // ActMonoidとMonoidが同型であるため、「+」が使える

    // 追加固有関数
    var add:(Int,Int,Int)->() { return {self.areaOpe($0,$1,$2)} } // 区間変更クエリが加算なので、add(a,b,x)（範囲a..<bにxを加算）で呼べるようにする。


    // 以降は変更不要なはず
    // var tree: [Monoid]
    var lazy: [ActMonoid]
    var n: Int
    // private func biOpe(_ i:Int)->Monoid{ // 引数1つのときの関数オーバーロード
    //     return biOpe(tree[2*i],tree[2*i+1])
    // }
        
    init(_ ms: [/*Monoid*/ActMonoid]) { // イニシャライザの内容は、lazyに格納
        let sz = ms.count
        n = 1
        while n < sz { n *= 2 }
        // self.tree = Array(repeating: base, count: 2*n)
        self.lazy = Array(repeating: lzBase, count: 2*n)
        buildTree(ms)
    }

    init(_ cnt: Int, v: /*Monoid*/ActMonoid? = nil) { // イニシャライザの内容は、lazyに格納
        let ms = [/*Monoid*/ActMonoid](repeating: v ?? self.lzBase/*base*/, count: cnt)
        n = 1
        while n < cnt { n *= 2 }
        // self.tree = Array(repeating: base, count: 2*n)
        self.lazy = Array(repeating: lzBase, count: 2*n)
        buildTree(ms)
    }

    private func buildTree(_ ms: [/*Monoid*/ActMonoid]) { // イニシャライザの内容は、lazyに格納
        let sz = ms.count
        for i in 0..<sz {
            /*tree*/lazy[n+i] = ms[i]
        }
        // for i in stride(from: n-1, through: 1, by: -1) {
        //     tree[i] = biOpe(i)
        // }
    }
    
    // private func eval(_ k: Int, _ l: Int, _ r: Int) {
    //     if lazy[k] != 0 {
    //         tree[k] = flz( lazy[k] ,tree[k] , r-l )
    //         if r - l > 1 {
    //             lazy[2*k] = lzOpe( lazy[k] , lazy[2*k] )
    //             lazy[2*k+1] = lzOpe( lazy[k] , lazy[2*k+1] )
    //         }
    //         lazy[k] = lzBase
    //     }
    // }

    func areaOpe(_ a: Int, _ b: Int, _ x: ActMonoid, _ k: Int = 1, _ l: Int = 0, _ r: Int = -1) {
        var r = r
        if r < 0 { r = n }
        // eval(k, l, r)
        if b <= l || r <= a { return }
        if a <= l && r <= b {
            lazy[k] = lzOpe( /*lzBase*/lazy[k] , x )
            // eval(k, l, r)
        } else {
            areaOpe(a, b, x, 2*k, l, (l+r)/2)
            areaOpe(a, b, x, 2*k+1, (l+r)/2, r)
            // tree[k] = biOpe(k)
        }
    }

    // func areaQuery(_ a: Int, _ b: Int, _ k: Int = 1, _ l: Int = 0, _ r: Int = -1) -> Monoid {
    //     var r = r
    //     if r < 0 { r = n }
    //     eval(k, l, r)
    //     if b <= l || r <= a { return base }
    //     if a <= l && r <= b { return tree[k] }
    //     let vl = areaQuery(a, b, 2*k, l, (l+r)/2)
    //     let vr = areaQuery(a, b, 2*k+1, (l+r)/2, r)
    //     return biOpe(vl,vr)
    // }
    
    // func pointUpdate(_ i: Int, v: Monoid) { // 一点更新
    //     var k = i + n
    //     lazy[k] = lzBase
    //     tree[k] = v
    //     while k > 1 {
    //         k /= 2
    //         tree[k] = biOpe(k)
    //     }
    // }

    func pointQuery(_ i: Int)-> /*Monoid*/ActMonoid { // 一点評価
        var k = i + n
        var ans = /*tree[k]*/lzBase
        while k > 0 {
            ans = /*flz*/lzOpe( lazy[k] ,ans /*, 1*/)        
            k /= 2
        }
        return ans
    }
    
    /// 下記は、treeやlazyがIntである前提で作ってるけど、とりあえず検証用に放置。モノイドがIntでないときはエラーの原因になるので、捨ててよし。
    /// 捨てるときは、import Foundationも不要になるよ。
    func prtIndex() {
        let nums = (1..<(2*n)).map { String(format: "%2d", $0) }.joined(separator: ",")
        print("(",nums,")")
    }    
    
    // func prtTree() {
    //     let nums = tree[1...].map { String(format: "%3d", $0) }.joined(separator: ",")
    //     print("[",nums,"]")
    //     // print(tree[1...])
    // }
    func /*prtLazyTree*/prtTree() {
        let nums = lazy[1...].map { String(format: "%2d", $0) }.joined(separator: ",")
        print("[",nums,"]")
        // print(lazy[1...])
    }

    func prtAry() {
        let nums = /*tree*/lazy[n...].map { String(format: "%2d", $0) }.joined(separator: ",")
        print("[",nums,"]")    
        // print(tree[n...])
    }

}

• 上記の解説
  • 削ったモノ
    • 通常のセグ木の成分
      • tree(モノイド)、base(単位元)、biOpe(二項演算)
    • 通常の遅延セグ木の成分や関数
      • flz(モノイドへの作用[遅延セグ木のモノイドからセグ木のモノイドへのモノイド射])、eval(遅延セグ木の要素を通常のセグ木へ遅延評価する関数)、query(通常のセグ木と遅延セグ木の要素をミックさせて区間取得クエリを行う関数)
  • 追加したモノ
    • pointQuery(lazyの葉部分の１要素に対して、lazyの上部ノード[区間変更クエリ]を適用する関数。点評価クエリと呼ぶ。)
  • その他
    • クラス名をLazySegTreeからDualSegTreeに変更。
    • initで、不要となったtreeの処理を削除。
    • buildtreeで、分析対象となる配列をtree[n...]でなくlazy[n...]に格納。
    • areaOpeで、lzOpeの引数をlzBaseからlazy[k]に変更。この変更の意味が分からない人は、遅延セグ木の投稿を読み返してね。　なーんて偉そうなこと言ってるけど、この変更については、動作確認してから僕も気付いたけどね。
• これで、遅延評価部分のみを残したと言うことが理解いただけただろうか？
• ちなみに、遅延セグ木の理解を深める投稿のところでモノイドの解説もしていたけど、本質は、外部作用ありきで考えれば、外部作用を表すflz関数を残すべきだったのかもだけど、今回は、「葉部分(評価対象配列)」と「上部ノード(遅延評価作用素)」が同じ型という前提にしたので、であれば、コード修正量が少なくなるように、flz関数の代わりにlzOpe関数を生かすことにしたよ。
• 調べてみると、双対セグメント木って言葉に対して、みんなが抱いているイメージがバラけている気がするね。モノイドというバックボーンを気にしている人と、気にしていない人に分かれている気がする。

双対セグ木の動作確認

• 前記の双対セグ木のインスタンス(dst)を作り、動かしてみた。
• やったことは、区間加算クエリを行ったときのlazyの値の動きの確認。
• 10個の10で双対セグ木を作った後、下記の処理を行った
  • 1..<5に12を加算し、全てのインデックス(0..<10)を点評価
  • 2..<10に5を加算、全てのインデックスを点評価

// 動作確認
let nums = [10,10,10,10,10,10,10,10,10,10] // 10個の10
let dst = DualSegTree(nums)

print("双対セグ木生成直後")
dst.prtIndex()
dst.prtTree()
print()

print("add(1, 5, 12)を実行")
dst.add(1, 5, 12)
dst.prtIndex()
dst.prtTree()
print("点クエリの結果(at:0..<10)")
for i in 0..<10 {print(dst.pointQuery(i),terminator:" ")}

print("\n") // これで、改行２回分

print("add(2, 10, 5)を実行")
dst.add(2, 10, 5)
dst.prtIndex()
dst.prtTree()
print("点クエリの結果(at:0..<10)")
for i in 0..<10 {print(dst.pointQuery(i),terminator:" ")}

//動作確認の出力
双対セグ木生成直後
(  1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31 )
[  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,10,10,10,10,10,10,10,10,10,10, 0, 0, 0, 0, 0, 0 ]

add(1, 5, 12)を実行
(  1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31 )
[  0, 0, 0, 0, 0, 0, 0, 0,12, 0, 0, 0, 0, 0, 0,10,22,10,10,22,10,10,10,10,10, 0, 0, 0, 0, 0, 0 ]
点クエリの結果(at:0..<10)
10 22 22 22 22 10 10 10 10 10 

add(2, 10, 5)を実行
(  1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31 )
[  0, 0, 0, 0, 5, 0, 0, 0,17, 0, 0, 5, 0, 0, 0,10,22,10,10,22,10,10,10,10,10, 0, 0, 0, 0, 0, 0 ]
点クエリの結果(at:0..<10)
10 22 27 27 27 15 15 15 15 15 

• 下図を見ながら、上記出力を検証しよう。
  
• 加算(範囲1..<5)において、上部ノード(㋐〜㋓)で完全に範囲に含まれるのは、ノード9のみ。よって、上部コードはノード9のみ値が格納されている。そして、上部ノードでカバーされない葉(㋔)17と葉20は、加算結果が直接反映している。
• 加算(範囲2..<10)において、上部ノードで完全に範囲に含まれるのは、ノード9,5,12。よって、上部コードはノード9,5,12に値が適用(lzOpe(lazy[k]),x:上記コードでは加算)されている。この加算では、葉には直接反映しない。
• 点評価(pointQuery)では、葉㋔から根㋐まで、葉の値に上部ノードの値を適用(lzOpe(rex,lazy[idx]))しながら登っていく。

世間でよく見る双対セグ木の関数との比較

• 生成AIさんが教えてくれた、世間一般的な双対セグ木の関数です。
• apply
  指定された位置に対してモノイド操作を適用する関数です。

// 生成AIの示した関数
func apply(_ node: Int, value: Int) {
    tree[node] = combine(tree[node], value)
}

// 前記コードで再現すると
func apply(_ k: Int, _ v: ActMonoid) {
    lazy[k] = lzOpe(lazy[k], v)
}

• push
  遅延評価を行い、特定のノードの値をその子ノードに伝播させるための関数です。

// 生成AIの示した関数
func push(_ at: Int) {
    guard at > 0 else { return }

    var n = 1
    var r = 0
    while n <= at {
        n *= 2
        r += 1
    }

    for i in (1...r).reversed() {
        let parent = at >> i
        if lazy[parent] != defLazy {
            apply(parent * 2, value: lazy[parent])
            apply(parent * 2 + 1, value: lazy[parent])
            lazy[parent] = defLazy
        }
    }
}

// 前記コードで再現すると
// 〜〜省略〜〜
// pushは、updateRange、get、setで使用される関数だが、
// 前記コードで、updateRange、get、setをpushを使わずに算出するロジックを使っている

• updateRange
  指定された区間に対して一括で更新を行う関数です。

// 生成AIの作ったコード
mutating func updateRange(_ left: Int, _ right: Int, val: Int) {
    if left >= right { return }
    var l = left + size
    var r = right + size

    // 深さを計算してpush関数を呼び出す
    var tempL = l
    var depthL = 0
    while tempL > 1 {
        tempL /= 2
        depthL += 1
    }
    push(l >> depthL)

    var tempR = r - 1
    var depthR = 0
    while tempR > 1 {
        tempR /= 2
        depthR += 1
    }
    push((r - 1) >> depthR)

    // 区間の更新
    while l < r {
        if l & 1 != 0 {
            apply(l, value: val)
            l += 1
        }
        if r & 1 != 0 {
            r -= 1
            apply(r, value: val)
        }
        l >>= 1
        r >>= 1
    }
}

// 前記コードで再現すると（クラスだから、mutating不要）
var updateRange:(Int,Int,ActMonoid)->() { return {self.areaOpe($0,$1,$2)} }

• query
  指定された位置または区間に対してクエリを行い、その結果を返す関数です。

// 生成AIの作ったコード
mutating func query(index: Int) -> Int {
    var idx = index + size
    var result = monoid.identity
    while idx > 0 {
        result = combine(result, tree[idx])
        idx >>= 1
    }
    return result
}

// 前記コードで再現すると
var query:(Int) -> ActMonoid { return {self.pointQuery($0)} }

• get
  指定された位置の値を得る関数です。

// 生成AIの作ったコード
subscript(at: Int) -> Element {
    get {
        var index = at + self.size
        push(index)
        return self.lazy[index]
    }
}

// 前記コードで再現すると
var get:(Int) -> ActMonoid {return pointQuery($0)}

• set
  指定された位置に対して新しい値を設定する関数です。

// 生成AIの作ったコード
mutating func set(_ at: Int, val: Int) {
    var index = at + size
    push(index)
    tree[index] = val
}

// 前記コードで再現すると
var set:(Int,ActMonoid)-() { return {self.areaOpe($0,$0+1,$1)} }

• 総評
  • うーむ....getとqueryって同じじゃね？ただ、戻り値は同じだけど、実現するためのアルゴリズムに違いがある。
    • getのアルゴリズムでは、まず、pushを行っているけど、このプッシュはgetで求めたいインデックスiにかかる遅延評価値を全て、インデックスiの値に反映させるためのロジック。
      
      例えば、上図におけるインデックス5の対するpush(5)は、forループ内で、上部ノードにある1⇒2⇒5⇒10の順に子ノードにlzOpeをしていき、最終的に葉ノード21にかかっていた遅延評価値を反映済みにさせる、ということ。
    • queryのアルゴリズムでは、まず、葉部分の値を拾い、その後、上部ノードにある10⇒5⇒2⇒1の順に遅延評価値を反映していく。
    • また、pushでは、上部ノードの値は変更されるけど、getでは、上部ノードの値は変わらない。
• 話は変わるけど、applyとupdateRangeの手法は、有用かもしれない。
• 例えば、actMonoidが集合や配列などのCollection型の時に、範囲l..<rの集合等に一律に要素を追加するときに、高速に対応できそう。
  • applyのcombineは要素追加(insert)とする。
  • updateRangeの要修正点は、不要となったpush関数を削るくらいかな。
• もちろん、前記コードでも、actMonoidが集合の場合に、要素追加を、当該要素のみを持つ集合に対するunionとして実現できるけど、集合同士の統合って、計算量を食うのよね。モノイドのみで構成したい、潔癖症の人には嫌がられるかもしれないけど、これ、競プロなのよね。
• だから、モノイドの結合則を崩しちゃうかも知れないけど、insertを導入しちゃうよ！

新たな関数追加

• 生成AIが教えてくれた、apply、updateRangeについて、違う意味を持たせて、追加するね。まず、新たな型を追加します。ActMonoidを変化させる要因だから、型名はCF(Change Factor)とでもしようか。
• でもって、新設する関数名は、
  • applyは、change(_ k:Int,_ cf:CF)
  • updateRangeは、changeArea(_ a:Int,_ b:Int,_ cf:CF)
• 名前は、changeシリーズにしたけど、このchangeでlazyのモノイドの状態を壊すわけには行かない。だから、changeシリーズで出来ることは、lzOpeをサポートする機能のみ。
• 上記の他、change関数で使う関数であり、ActMonoidにCFをどのように作用させるのか定める、subLzOpe:(_ cf:CF,_ ActMonoid)->ActMonoidを定義することも必要。
• 追加するコード

    // lzOpeをサポートする関数(範囲内のLazyを一律に変化させる)
    private var subLzOpe:(_ cf:CF,_ a:inout ActMonoid)->() = {状況に応じて}    
    
    func change(_ k:Int,_ cf:CF) {
        subLzOpe(cf,&lazy[k])
    }
    
    func changeArea(_ a:Int,_ b:Int,_ cf:CF) {
        // 葉のノードに変換
        var l = n + a
        var r = n + b
    
        // 区間の更新
        while l < r {
            if l & 1 != 0 {
                change(l, cf)
                l += 1
            }
            if r & 1 != 0 {
                r -= 1 // r自身は含まないから、先に1除く
                change(r, cf)
            }
            // 1階層上がる
            l >>= 1
            r >>= 1
        }
    }

• 上記コードを実際に使ってみよう。
  • lazyは集合
  • lzOpeは集合同士のunion
  • そして、真打ち、subLzOpeは集合への要素追加(insert)
  • subLzOpeはlzOpeを補完するものになっているよ。
• こんなコードになるよ。

class DualSegTree {

    // 双対セグ木設定場所
    typealias ActMonoid = Set<Int> 
    typealias CF = Int    
    private var lzBase: ActMonoid = Set<Int>() // 空集合
    private var lzOpe:(_ u:ActMonoid,_ d:ActMonoid)->ActMonoid = {$0.union($1)}

    // 追加固有関数

    
    // lzOpeをサポートする関数(範囲内のLazyを一律に変化させる)
    private var subLzOpe:(_ cf:CF,_ a:inout ActMonoid)->() = {cf,a in a.insert(cf)}    
    
    func change(_ k:Int,_ cf:CF) {
        subLzOpe(cf,&lazy[k])
    }
    
    func changeArea(_ a:Int,_ b:Int,_ cf:CF) {
        // 葉のノードに変換
        var l = n + a
        var r = n + b
    
        // 区間の更新
        while l < r {
            if l & 1 != 0 {
                change(l, cf)
                l += 1
            }
            if r & 1 != 0 {
                r -= 1 // r自身は含まないから、先に1除く
                change(r, cf)
            }
            // 1階層上がる
            l >>= 1
            r >>= 1
        }
    }

    // 以降は変更不要なはず
    var lazy: [ActMonoid]
    var n: Int
        
    init(_ ms: [ActMonoid]) { // イニシャライザの内容は、lazyに格納
        let sz = ms.count
        n = 1
        while n < sz { n *= 2 }
        self.lazy = Array(repeating: lzBase, count: 2*n)
        buildTree(ms)
    }

    init(_ cnt: Int, v: ActMonoid? = nil) { // イニシャライザの内容は、lazyに格納
        let ms = [ActMonoid](repeating: v ?? self.lzBase, count: cnt)
        n = 1
        while n < cnt { n *= 2 }
        self.lazy = Array(repeating: lzBase, count: 2*n)
        buildTree(ms)
    }

    private func buildTree(_ ms: [ActMonoid]) { // イニシャライザの内容は、lazyに格納
        let sz = ms.count
        for i in 0..<sz {
            lazy[n+i] = ms[i]
        }
    }
    

    func areaOpe(_ a: Int, _ b: Int, _ x: ActMonoid, _ k: Int = 1, _ l: Int = 0, _ r: Int = -1) {
        var r = r
        if r < 0 { r = n }
        if b <= l || r <= a { return }
        if a <= l && r <= b {
            lazy[k] = lzOpe(lazy[k] , x )
        } else {
            areaOpe(a, b, x, 2*k, l, (l+r)/2)
            areaOpe(a, b, x, 2*k+1, (l+r)/2, r)
        }
    }


    func pointQuery(_ i: Int)-> ActMonoid { // 一点評価
        var k = i + n
        var ans = lzBase
        while k > 0 {
            ans = lzOpe( lazy[k] ,ans)        
            k /= 2
        }
        return ans
    }
    
    func prtTrees() { // 分析用print関数
        for i in 1..<2*n {
            print(i,lazy[i])
        }
    }
}

• 利用例は

let sets:[Set<Int>] = [ // 6個の集合
[1,2,3], // 0
[10,20,30,40], // 1
[100,200], // 2
[1000,2000,3000], // 3
[10000], // 4
[1,11,111,1111,11111] // 5
]

print("生成直後")
var tree = DualSegTree(sets)
tree.prtTrees()

print("\n範囲0..<4(ノード8..<12)に集合[888,999]を追加した")
tree.areaOpe(0,4,[888,999])
tree.prtTrees()

print("\n範囲0..<6(ノード8..<14)に77を追加した(追加関数changeシリーズによる)")
tree.changeArea(0,6,77)
tree.prtTrees()

print("\n全てのインデックス(0..<6)を評価した")
for i in 0..<6 {
    print(i,tree.pointQuery(i))
}

print("\n評価後")
tree.prtTrees()

• 実行結果は

生成直後
1 []
2 []
3 []
4 []
5 []
6 []
7 []
8 [3, 1, 2]
9 [40, 10, 30, 20]
10 [200, 100]
11 [3000, 1000, 2000]
12 [10000]
13 [1111, 11, 111, 1, 11111]
14 []
15 []

範囲0..<4(ノード8..<12)に集合[888,999]を追加した
1 []
2 [999, 888]
3 []
4 []
5 []
6 []
7 []
8 [3, 1, 2]
9 [40, 10, 30, 20]
10 [200, 100]
11 [3000, 1000, 2000]
12 [10000]
13 [1111, 11, 111, 1, 11111]
14 []
15 []

範囲0..<6(ノード8..<14)に77を追加した(追加関数changeシリーズによる)
1 []
2 [77, 999, 888]
3 []
4 []
5 []
6 [77]
7 []
8 [3, 1, 2]
9 [40, 10, 30, 20]
10 [200, 100]
11 [3000, 1000, 2000]
12 [10000]
13 [1111, 11, 111, 1, 11111]
14 []
15 []

全てのインデックス(0..<6)を評価した
0 [77, 1, 999, 888, 2, 3]
1 [30, 999, 40, 77, 888, 20, 10]
2 [888, 200, 100, 999, 77]
3 [77, 1000, 999, 888, 3000, 2000]
4 [10000, 77]
5 [1111, 77, 1, 11, 11111, 111]

評価後
1 []
2 [77, 999, 888]
3 []
4 []
5 []
6 [77]
7 []
8 [3, 1, 2]
9 [40, 10, 30, 20]
10 [200, 100]
11 [3000, 1000, 2000]
12 [10000]
13 [1111, 11, 111, 1, 11111]
14 []
15 []

• うむ。良い感じに出力されている！
• 葉と上部ノードの対応図は下図を参照
  

双対セグ木を使って問題を解く

• この問題を解いてみよう。
  • 最初に配列Aがあたえられれ、以下の3種類のクエリを実行する
  • クエリ① 3つの値(l,r,x)が与えられ、配列Aの範囲l...rについて、max(元の値,x)で入れ替える。
  • クエリ② q番目に行ったクエリ①を取り消す。
  • クエリ③ A[i]を出力する。
• 入力例

6 // 配列Aの要素数N
2 7 1 8 2 8 // 配列Aの要素
15 // クエリ数Q
3 1 // クエリ③ 1-idx表示なので、A[0]を出力
3 3
3 4
1 1 5 4 // クエリ① A[0...4]をmax(4,元の値)で入れ替える。
3 1
3 3
3 4
1 3 6 9
3 1
3 3
3 4
2 4 // クエリ② 4番目のクエリを取り消す
3 1
3 3
3 4

• 解き方
  • クエリ②が鬼門です。
    • 具体的には、過去のクエリ①の内容を全て記憶しておく必要があるよね。
    • だから、クエリ番号とペアにして、集合に覚えさせておいて、後からクエリ番号で検索して、削除できるようにします。
    • ついでに、初期値もこの集合に入れてしまえば良いか。クエリ番号を1スタートとして、初期値はクエリ番号0としてしまおう。
  • クエリ③においては、集合の最大値を解答するだけだね。
  • そう言えば、Setのremoveは高速(O(1)。全ての要素がハッシュ値をもつから)だけど、max関数は低速(O(n))なのよね。大丈夫だろうか？
  • あと、Setにはタプル(Int(最大値),Int(クエリ番号))を格納するから、タプルをHashableにするために、構造体ChTplを導入する。

class DualSegTree {

    // 双対セグ木設定場所
    typealias ActMonoid = Set<ChTpl<Int>> 
    typealias CF = ChTpl<Int>
    private var lzBase: ActMonoid = Set<ChTpl<Int>>() // 空集合
    private var lzOpe:(_ u:ActMonoid,_ d:ActMonoid)->ActMonoid = {$0.union($1)}

    // 追加固有関数
    func queryMax(_ i:Int)->Int { // インデックスiの最大値を答える
        var k = i + n
        let inf = -1 // 値は全て正の値なので、基準は-1で十分
        var ans = inf
        while k > 0 {
            ans = max( (lazy[k].max() ?? ChTpl(inf,0)).fst ,ans)        
            k /= 2
        }
        return ans
    }
    
    // lzOpeをサポートする関数(範囲内のLazyを一律に変化させる)
    private var subLzOpe:(_ cf:CF,_ a:inout ActMonoid)->() = {
    cf,a in
        let (mx,index) = (cf.fst,cf.snd)
        if mx > 0 {
            a.insert(cf)          
        } else {
            a.remove(ChTpl<Int>(-mx,index))
        }
    }    

    ･･･（中略）･･･
}

struct ChTpl<T:Comparable & Hashable> : Comparable,Hashable,CustomStringConvertible {･･･}

let N = Int(readLine()!)!

//整数入力（複数、スペース区切り、配列格納）
let A = readLine()!.split(separator:" ").map{Int($0)!}
var dst = DualSegTree(A.map{ Set<ChTpl<Int>>( [ChTpl($0,0)] )})
// dst.prtTrees()

let Q = Int(readLine()!)!

//2次元配列
var qs:[[Int]] = []
for _ in 0..<Q {
    let q = readLine()!.split(separator:" ").map{Int($0)!}
    qs.append(q)
}

var i = 0
for q in qs {
    i += 1 // iは1スタート
    switch q[0] {
        case 1:
            let (l,r,x) = (q[1]-1,q[2],q[3])
            let tpl = ChTpl(x,i)
            dst.changeArea(l,r,tpl)
            // print()
            // dst.prtTrees()
        case 2:
            let rm_i = q[1]
            let rm_q = qs[rm_i - 1] // qsでは1ズレる
            let (l,r,x) = (rm_q[1]-1,rm_q[2],rm_q[3])
            let tpl = ChTpl(-x,rm_i) // 値を負数として、削除指示
            dst.changeArea(l,r,tpl)
        case 3: // case 3に相当
            print(dst.queryMax(q[1] - 1))
        default:break
    }
}

• 出来たけど...TLEがちらほら発生したよ。
• やっぱり、Setで最大値を算出するのはちょっと時間がかかりすぎる。

ズルをして高速化する

• 前記の問題を解くとき、実際はlazyノード間でunion関数は使用されてないのよね。unionを使わない前提なら、ActMonoidとしてSetなんて使わず、maxヒープを使った方が高速化できるじゃない。まぁ、maxヒープにもunion関数は作れるだろうけど、使われない関数を作るほどヒマじゃない。でも、maxヒープに高速なremove(O(N)だと遅すぎだから、O(logN)にしたい)は必要だね。それくらいは追加しておこう。
  • そして... remove追加版をつくりました！、ついでに、union関数も実装しちゃいました！
  • でも、「ズルをする」と宣言したので、union関数は使いません！...このオジさん、何言ってんの？と思った人もいるかもだけど、初志貫徹します。

struct Heap<V: Comparable & Hashable>: CustomStringConvertible {･･･} // Heap導入！
struct ChTpl<T:Comparable & Hashable>: Hashable,Comparable,CustomStringConvertible {･･･}

class DualSegTree {

    // 双対セグ木設定場所
    typealias ActMonoid = Heap<ChTpl<Int>> // Heapに変更！
    typealias CF = ChTpl<Int>
    private var lzBase: ActMonoid = Heap<ChTpl<Int>>() // Heapの空集合!
    
    private var lzOpe:(_ u:ActMonoid,_ d:ActMonoid)->ActMonoid = {u,d in u} // ズル！第1引数を返すだけ!

    // 追加固有関数
    func queryMax(_ i:Int)->Int {
        var k = i + n
        let inf = -1
        var ans = inf
        while k > 0 {
            ans = max( (lazy[k].root ?? ChTpl(inf,0)).fst ,ans) // Heapのrootで高速に最大値取得！
            k /= 2
        }
        return ans
    }
    
    // lzOpeをサポートする関数(範囲内のLazyを一律に変化させる)
    private var subLzOpe:(_ cf:CF,_ a:inout ActMonoid)->() = {
    cf,a in
        let (mx,index) = (cf.fst,cf.snd)
        if mx > 0 {
            a.insert(cf)
        } else {
            a.remove(ChTpl<Int>(-mx,index)) // Heapで新たに作った高速なremove!!!
        }
    }    
    
    ･･･略･･･
}

let N = Int(readLine()!)!

//整数入力（複数、スペース区切り、配列格納）
let A = readLine()!.split(separator:" ").map{Int($0)!}
var dst = DualSegTree(A.map{ Heap<ChTpl<Int>>( [ChTpl($0,0)] )}) // SetじゃなくHeap!

    ･･･略･･･

• 上記で提出したら、2.3s(<制限5sec)でAC。
• ACにたどり着くまで､苦労したよ。めっちゃ疲れた...
• 双対セグ木って、他の人の意見を参考しようとしても、人によって説明のレベルが違い過ぎて、何を信じれば良いのかも分からず、自分の位置も見失いかけたよ。
• 結果、自分なりに、subLzOpeという考え方で、自分を納得させて、この問題を解くことが出来たよ。
• Setで解けなかったのは、想定外で、Heap強化という寄り道をするハメになった。
  • めっちゃ疲れた....

おわりに

• 双対セグ木に手を出したのって、教育的dpの最後の問題で、CHTと双対セグ木を使うって見たからなんだよね。
• 実際は、CHTだけで解けちゃったから、宝の持ち腐れになっちゃったんだけど...
• でも最後の問題を双対セグ木の１種である「li-chaoセグ木」で解く方法があるみたいだから、そのうち、li-chaoセグ木にも手を出してみるつもりです。