セグメント木上の二分探索

忘備録

はじめに

先にこっちを見て　
beet-aizu.hatenablog.com

目的：セグ木上で二分探索をするとき、適当にやると O(log2N)$O(lo{g}^{2}N)$なのを O(logN)$O(logN)$ でやりたい

これ↓をベースに一般化する
ei1333.hateblo.jp

非再帰でやるのは明らかにやばそうなので再帰で書いた
checkが判定関数　ラムダ式を渡す
accが途中経過を保存する変数

定式化すると、
min idx s.t. st <= idx && check(query(st,idx)) = false && check(query(st,idx+1)) = true
そのようなidxが存在しないなら-1を返す　さすがにcheck(単位元)=trueになるようなことはないでしょ

まず見ているノードが子のときを考える
checkの結果に関わらずaccとマージしたあと、check(acc)をみるだけ

子ではないときを考える　遅延セグ木なら最初に遅延を伝播する

もし左の子の右端がstより左にあるなら右の子だけ考えればいい

見ているノードの区間全体がstより右側にあって、accとその区間をマージしても無理なら
子を見る必要はないのでマージして-1を返す

上の二つのどちらでもないなら、再帰的に左右の子を見る
左の子だけで条件を満たすなら右の子を見る必要はない

  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){
    if(l+1==r){
      acc=f(acc,reflect(k));
      return check(acc)?k-n:-1;
    }
    eval(k);
    int m=(l+r)>>1;
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
    if(st<=l&&!check(f(acc,dat[k]))){
      acc=f(acc,dat[k]);
      return -1;
    }
    int vl=find(st,check,acc,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(st,check,acc,(k<<1)|1,m,r);
  }
  template<typename C>
  int find(int st,C &check){
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }

verify用問題集

任意始点のがほとんどないのでおしえてくだしあ
atcoder.jp
atcoder.jp
atcoder.jp
codeforces.com