Types
FunctionalGraph_with_lazy_op[ST] = ref object graph: Functional_Graph st_hld: ST st_cycle: ST cum_cyclesize: seq[int]
- ACLの遅延セグメント木を用いて、functional graph上の積と経路作用を扱う。 非サイクル頂点はst_hld、サイクル頂点はst_cycleだけに保持する。 Source Edit
Procs
proc `[]=`[ST](self: FunctionalGraph_with_lazy_op[ST]; x: int; value: ST.S)
- Source Edit
proc `[]`[ST](self: FunctionalGraph_with_lazy_op[ST]; x: int): ST.S
- Source Edit
proc apply[ST](self: FunctionalGraph_with_lazy_op[ST]; start, k: int; f: ST.F; include_start: bool = true)
- startからk回移動するまでに訪れる各頂点へfを作用させる。 同じ頂点を複数回訪れた場合は、その回数だけfを作用させる。 include_start=falseなら始点には作用させない。O(log^2 N + log k) Source Edit
proc canmove_size[ST](self: FunctionalGraph_with_lazy_op[ST]; x: int): int
- Source Edit
proc count_kth[ST](self: FunctionalGraph_with_lazy_op[ST]; x, k: int): int
- Source Edit
proc cyclesize[ST](self: FunctionalGraph_with_lazy_op[ST]; x: int): int
- Source Edit
proc depth[ST](self: FunctionalGraph_with_lazy_op[ST]; x: int): int
- Source Edit
proc dist[ST](self: FunctionalGraph_with_lazy_op[ST]; u, v: int): int
- Source Edit
proc get[ST](self: FunctionalGraph_with_lazy_op[ST]; x: int): ST.S
- 頂点xの現在値を返す。O(log N) Source Edit
proc get_cycle[ST](self: FunctionalGraph_with_lazy_op[ST]; x: int): seq[int]
- Source Edit
proc incycle[ST](self: FunctionalGraph_with_lazy_op[ST]; x: int): bool
- Source Edit
proc initFunctionalGraph_with_lazy_op[S, ST](source: Functional_Graph; values: seq[S]; st_type: typedesc[ST]): FunctionalGraph_with_lazy_op[ST]
- 明示したACL LazySegTree型STを使って構築する。O(N) 複数のfunctional graphを同じ型として保持したい場合に用いる。 Source Edit
proc initFunctionalGraph_with_lazy_op[S, ST](source: openArray[int]; values: seq[S]; st_type: typedesc[ST]): FunctionalGraph_with_lazy_op[ST]
- Source Edit
proc initFunctionalGraph_with_lazy_op[S, ST](source: UnWeightedDirectedGraph; values: seq[S]; st_type: typedesc[ST]): FunctionalGraph_with_lazy_op[ST]
- Source Edit
proc move_while[ST](self: FunctionalGraph_with_lazy_op[ST]; f: proc (x: ST.S): bool; x, L: int): int
- @[x]から始め、prefixのprodに対するfが初めてfalseになる移動距離。 L回移動してもtrueならLを返す。O(log^2 N + log L) f(e)=trueであり、一度falseになった後は頂点を追加してもfalseのまま、 というACL max_rightと同じ単調性を仮定する。 Source Edit
proc movekth[ST](self: FunctionalGraph_with_lazy_op[ST]; x, cnt: int): int
- Source Edit
proc prod[ST](self: FunctionalGraph_with_lazy_op[ST]; start, k: int; include_start: bool = true): ST.S
- startからk回移動するまでの積。include_start=falseなら始点を積に含めない。 O(log^2 N + log k) Source Edit
proc prod_range[ST](self: FunctionalGraph_with_lazy_op[ST]; start, l, r: int; include_start: bool = true): seq[ST.S]
- @[prod(start,l), ..., prod(start,r-1)]を返す。 O(log^2 N + log l + (r-l)) Source Edit
proc prod_range_fold[ST, U](self: FunctionalGraph_with_lazy_op[ST]; start, l, r: int; f: proc (x: U; y: ST.S): U; e: U; include_start: bool = true): U
- prod(start,l), ..., prod(start,r-1)を順にfで畳み込む。 O(log^2 N + log l + (r-l)) Source Edit
proc prod_reachable_idempotent_all[ST](self: FunctionalGraph_with_lazy_op[ST]): seq[ ST.S]
- 各頂点から到達可能な相異なる頂点の値の積を全頂点について返す。 opは結合的・可換・冪等でなければならない。O(N) Source Edit
proc reachable_to_size[ST](self: FunctionalGraph_with_lazy_op[ST]; x: int): int
- Source Edit
proc root[ST](self: FunctionalGraph_with_lazy_op[ST]; x: int): int
- Source Edit
proc set[ST](self: FunctionalGraph_with_lazy_op[ST]; x: int; value: ST.S)
- 頂点xの値をvalueに変更する。O(log N) Source Edit
proc walk[ST](self: FunctionalGraph_with_lazy_op[ST]; x, k: int): seq[int]
- Source Edit
Templates
template initFunctionalGraph_with_lazy_op( source, values, op, e, mapping, composition, id: untyped): untyped
- ACLのlazysegtreeと同じop/e/mapping/composition/idから構築する。O(N) Source Edit
template initFunctionalGraph_with_op(source, values, op, e, mapping, composition, id: untyped): untyped
- 遅延作用を使う場合のinitFunctionalGraph_with_opオーバーロード。 Source Edit