Documentation
¶
Index ¶
- func NewBool2d(a, b int, value bool) [][]bool
- func NewFloat2d(a, b int, value float64) [][]float64
- func NewInt2d(a, b, value int) [][]int
- func NewInt3d(a, b, c, value int) [][][]int
- func Unique[V constraints.Ordered](arr []V) []V
- type DijkstraResult
- type DualSegmentTree
- type Edge
- type Graph
- func (g *Graph) AddDirectedEdge(u, v int)
- func (g *Graph) AddDirectedWeightedEdge(u, v, w int)
- func (g *Graph) AddEdge(u, v int)
- func (g *Graph) AddEdge1(u, v int)
- func (g *Graph) AddWeightedEdge(u, v, w int)
- func (g *Graph) BellmanFord(s, t int)
- func (g *Graph) CountNodes() int
- func (g *Graph) Dijkstra(s int) *DijkstraResult
- func (g *Graph) Lca(root int) *Lca
- func (g *Graph) MaxFlow(s, t int) int
- func (g *Graph) Scc() Scc
- func (g *Graph) WarshallFloyd() [][]int
- type Int2d
- type Int4d
- type IntLazySegmentTree
- type IntPriorityQueue
- type LazySegmentTree
- type Lca
- type LinkedList
- func (list *LinkedList[V]) Add(value V) *LinkedListNode[V]
- func (list *LinkedList[V]) AddBack(value V) *LinkedListNode[V]
- func (list *LinkedList[V]) AddFront(value V) *LinkedListNode[V]
- func (list *LinkedList[V]) Back() V
- func (list *LinkedList[V]) Front() V
- func (list *LinkedList[V]) Len() int
- func (list *LinkedList[V]) RemoveBack() V
- func (list *LinkedList[V]) RemoveFront() V
- func (list *LinkedList[V]) ToArray() []V
- type LinkedListNode
- type PriorityQueue
- type RedBlackTree
- func (tree *RedBlackTree[K, V]) Ceiling(key K) (*K, *V)
- func (tree *RedBlackTree[K, V]) Empty() bool
- func (tree *RedBlackTree[K, V]) Floor(key K) (*K, *V)
- func (tree *RedBlackTree[K, V]) Get(key K) *V
- func (tree *RedBlackTree[K, V]) HasEntry() bool
- func (tree *RedBlackTree[K, V]) Left() (*K, *V)
- func (tree *RedBlackTree[K, V]) Put(key K, value V)
- func (tree *RedBlackTree[K, V]) Remove(key K)
- func (tree *RedBlackTree[K, V]) Size() int
- func (tree *RedBlackTree[K, V]) String() string
- type Scc
- type SegmentTree
- type UnionFind
- type WeightedUnionFind
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func NewFloat2d ¶
Types ¶
type DijkstraResult ¶
type DualSegmentTree ¶
type DualSegmentTree[V, X, F any] struct { Init func(n int) *DualSegmentTree[V, X, F] Update func(l, r int, value F) Query func(i int) V }
Vは扱う値、Xは保持する値、Fは適用する値
func NewDualSegmentTree ¶
func NewDualSegmentTree[V, X, F any]( mapping func(x *X, v *V), composition func(f *F, x *X), e func() V, id func() X, ) *DualSegmentTree[V, X, F]
type Graph ¶
Graph はグラフを表現する構造です
func (*Graph) AddDirectedEdge ¶
AddDirectedEdgeはuからvへ重み1の有向辺を追加します。
func (*Graph) AddDirectedWeightedEdge ¶
AddDirectedWeightedEdgeはuからvへ重みwの有向辺を追加します。
func (*Graph) AddWeightedEdge ¶
AddWeightedEdge はuからvへ重みwの無向辺を追加します。
func (*Graph) Dijkstra ¶
func (g *Graph) Dijkstra(s int) *DijkstraResult
Dijkstra はsから各頂点への最短距離を返します。 重みが負の辺があるときには使用できません。 計算量: |V| + |E|log|V|
func (*Graph) WarshallFloyd ¶
WarshallFloyd は全点対の最短ルートを返します。
type IntLazySegmentTree ¶
type IntLazySegmentTree struct {
// Initは長さnの配列として初期化します
Init func(n int) *IntLazySegmentTree
// InitByArrayはarrとして初期化します。
InitByArray func(arr []int) *IntLazySegmentTree
// Updateは[l, r)をfで更新します。
Update func(l, r int, f int)
// Queryは[l, r)の値を返します。
Query func(l, r int) int
}
type IntPriorityQueue ¶
type IntPriorityQueue struct {
// contains filtered or unexported fields
}
func NewBiggerIntPriorityQueue ¶
func NewBiggerIntPriorityQueue() *IntPriorityQueue
func NewIntPriorityQueue ¶
func NewIntPriorityQueue(prior func(a, b int) bool) *IntPriorityQueue
func NewSmallerIntPriorityQueue ¶
func NewSmallerIntPriorityQueue() *IntPriorityQueue
func (IntPriorityQueue) Empty ¶
func (pq IntPriorityQueue) Empty() bool
Empty は優先度付きキューが空かどうかを判断します。
func (IntPriorityQueue) HasElements ¶
func (pq IntPriorityQueue) HasElements() bool
HasElementsはこの優先度付きキューが要素を持つかどうかを判断します。
func (IntPriorityQueue) Push ¶
func (pq IntPriorityQueue) Push(value int)
Push は優先度付きキューに要素を一つ追加します。
type LazySegmentTree ¶
type LazySegmentTree[V, F any] struct { // Initは長さnの配列として初期化します Init func(n int) *LazySegmentTree[V, F] // InitByArrayはarrとして初期化します。 InitByArray func(arr []V) *LazySegmentTree[V, F] // Updateは[l, r)をfで更新します。 Update func(l, r int, f F) // Queryは[l, r)の値を返します。 Query func(l, r int) V }
func NewLazySegmentTree ¶
func NewLazySegmentTree[V, F any]( operate func(a, b, ab *V), mapping func(f *F, x *V), composition func(f, g, fg *F), e func() V, id func() F, ) *LazySegmentTree[V, F]
NewLazySegmentTreeは遅延評価セグメントツリーの実装を返します。 Vは扱うモノイドの型、Fはモノイドに適用する写像をあらわします。
例えば range add range max queryの場合、以下のようになります。
st := NewLazySegmentTree[int, int](
max,
func(f, x int) int { return f + x },
func(f, g int) int { return f + g },
func() int { return 0 },
func() int { return 0 },
)
type LinkedList ¶
type LinkedList[V any] struct { // contains filtered or unexported fields }
func NewLinkedList ¶
func NewLinkedList[V any]() *LinkedList[V]
func (*LinkedList[V]) Add ¶
func (list *LinkedList[V]) Add(value V) *LinkedListNode[V]
func (*LinkedList[V]) AddBack ¶
func (list *LinkedList[V]) AddBack(value V) *LinkedListNode[V]
func (*LinkedList[V]) AddFront ¶
func (list *LinkedList[V]) AddFront(value V) *LinkedListNode[V]
func (*LinkedList[V]) Back ¶
func (list *LinkedList[V]) Back() V
func (*LinkedList[V]) Front ¶
func (list *LinkedList[V]) Front() V
func (*LinkedList[V]) Len ¶
func (list *LinkedList[V]) Len() int
func (*LinkedList[V]) RemoveBack ¶
func (list *LinkedList[V]) RemoveBack() V
func (*LinkedList[V]) RemoveFront ¶
func (list *LinkedList[V]) RemoveFront() V
func (*LinkedList[V]) ToArray ¶
func (list *LinkedList[V]) ToArray() []V
type LinkedListNode ¶
type LinkedListNode[V any] struct { // contains filtered or unexported fields }
func (*LinkedListNode[V]) AddAfter ¶
func (node *LinkedListNode[V]) AddAfter(value V) *LinkedListNode[V]
func (*LinkedListNode[V]) AddBefore ¶
func (node *LinkedListNode[V]) AddBefore(value V) *LinkedListNode[V]
func (*LinkedListNode[V]) Remove ¶
func (node *LinkedListNode[V]) Remove() V
type PriorityQueue ¶
type PriorityQueue struct {
// contains filtered or unexported fields
}
PriorityQueue は優先度付きキューを表す
func NewPriorityQueue ¶
func NewPriorityQueue(prior func(a, b interface{}) bool) *PriorityQueue
NewPriorityQueueはpriorで優先度が決まる空の優先度付きキューを返します。
func (PriorityQueue) HasElements ¶
func (pq PriorityQueue) HasElements() bool
HasElementsはこの優先度付きキューが要素を持つかどうかを判断します。
func (PriorityQueue) Push ¶
func (pq PriorityQueue) Push(value interface{})
Push は優先度付きキューに要素を一つ追加します。
type RedBlackTree ¶
func NewRedBlackTree ¶
func NewRedBlackTree[K any, V any](comparator func(a, b K) int) *RedBlackTree[K, V]
func (*RedBlackTree[K, V]) Ceiling ¶
func (tree *RedBlackTree[K, V]) Ceiling(key K) (*K, *V)
func (*RedBlackTree[K, V]) Empty ¶
func (tree *RedBlackTree[K, V]) Empty() bool
func (*RedBlackTree[K, V]) Floor ¶
func (tree *RedBlackTree[K, V]) Floor(key K) (*K, *V)
func (*RedBlackTree[K, V]) Get ¶
func (tree *RedBlackTree[K, V]) Get(key K) *V
func (*RedBlackTree[K, V]) HasEntry ¶
func (tree *RedBlackTree[K, V]) HasEntry() bool
func (*RedBlackTree[K, V]) Left ¶
func (tree *RedBlackTree[K, V]) Left() (*K, *V)
func (*RedBlackTree[K, V]) Put ¶
func (tree *RedBlackTree[K, V]) Put(key K, value V)
func (*RedBlackTree[K, V]) Remove ¶
func (tree *RedBlackTree[K, V]) Remove(key K)
func (*RedBlackTree[K, V]) Size ¶
func (tree *RedBlackTree[K, V]) Size() int
func (*RedBlackTree[K, V]) String ¶
func (tree *RedBlackTree[K, V]) String() string
type Scc ¶
type Scc struct {
// nは強連結成分分解後の頂点数
Size int
// Graphは強連結成分分解後のグラフ
Graph [][]int
// Componentsは強連結成分分解後の頂点(0-indexed)と、その頂点に対応する、もとのグラフの頂点(0-indexed)の配列
Components [][]int
// Nodesはもとのグラフの頂点(0-indexed)と、対応する新しい頂点(0-indexed)
Nodes map[int]int
}
Sccは強連結成分分解の結果を表します。
type SegmentTree ¶
type SegmentTree[V any] struct { // Initは[0, n)のsegment treeを初期化します。 // 各要素の値は単位元となります。 // tested: // // https://atcoder.jp/contests/abl/tasks/abl_d Init func(n int) *SegmentTree[V] // InitAsArrayはvalsで配列を初期化します。 // 区間の長さはlen(vals)になります。 // tested: // // https://judge.yosupo.jp/problem/staticrmq InitAsArray func(arr []V) *SegmentTree[V] // Updateはi(0-based)番目の値をvalueに更新します。 // tested: // // https://atcoder.jp/contests/abl/tasks/abl_d Update func(i int, value V) // Queryは[l, r) (0-based)の計算値を返します。 // tested: // // https://atcoder.jp/contests/abl/tasks/abl_d Query func(l, r int) V }
func NewSegmentTree ¶
func NewSegmentTree[V any]( e func() V, calc func(a, b, ab *V), ) *SegmentTree[V]
NewSegmentTreeは区間和を扱うSegmentTreeを返します。 tested:
https://atcoder.jp/contests/abl/tasks/abl_d
type UnionFind ¶
type UnionFind struct {
// contains filtered or unexported fields
}
UnionFind : UnionFind構造を保持する構造体
type WeightedUnionFind ¶
type WeightedUnionFind struct {
// contains filtered or unexported fields
}
重み付きUnion-Findは集合と、各ノードがルートからどれくらい距離があるかを管理します。
func NewWeightedUnionFind ¶
func NewWeightedUnionFind(n int) *WeightedUnionFind
NewWeightedUnionFindは重み付きUnion-Findの実装を返します。
func (*WeightedUnionFind) Diff ¶
func (uf *WeightedUnionFind) Diff(x, y int) int
weight[y]-weight[x]を返します。
func (*WeightedUnionFind) IsSame ¶
func (uf *WeightedUnionFind) IsSame(x, y int) bool
xとyが同じ集合にいるかを判断します。
func (*WeightedUnionFind) Merge ¶
func (uf *WeightedUnionFind) Merge(x, y, w int) bool
weight[y]-weight[x] = wとなるようにマージします
Source Files
Click to show internal directories.
Click to hide internal directories.