GoでAtCoder Library (ACL)のスニペットを作りました。
コピペするだけで使えると思います。
各コードの使い方はAtCoder Library Practice Contestの提出を見てください。
注意
動作保証はできないので、使用は自己責任でお願いします。
modintはありません。他にもところどころ実装していないものがあります。
AtCoder Library Practice Contestの全ての問題でACしましたが、ここで使用していない機能は動作確認していないものがあります。
実装に問題があったらご指摘いただけると幸いです。
目次
・DSU (Union-Find)
・Fenwick Tree (BIT)
・math (floor sumなど)
・MaxFlow
・MinCostFlow
・Convolution
・SCC
・Two SAT
・strings
・Segtree
・LazySegtree
・bits
Disjoint Set Union (DSU, Union-Find)
UnionFind.go
type UnionFind struct {
n int
par []int
}
func newUnionFind(n int) *UnionFind {
uf := new(UnionFind)
uf.n = n
uf.par = make([]int, n)
for i, _ := range uf.par {
uf.par[i] = -1
}
return uf
}
func (uf UnionFind) root(x int) int {
if uf.par[x] < 0 {
return x
}
uf.par[x] = uf.root(uf.par[x])
return uf.par[x]
}
func (uf UnionFind) unite(x, y int) {
rx, ry := uf.root(x), uf.root(y)
if rx != ry {
if uf.size(rx) > uf.size(ry) {
rx, ry = ry, rx
}
uf.par[ry] += uf.par[rx]
uf.par[rx] = ry
}
}
func (uf UnionFind) same(x, y int) bool {
return uf.root(x) == uf.root(y)
}
func (uf UnionFind) size(x int) int {
return -uf.par[uf.root(x)]
}
func (uf UnionFind) groups() [][]int {
rootBuf, groupSize := make([]int, uf.n), make([]int, uf.n)
for i := 0; i < uf.n; i++ {
rootBuf[i] = uf.root(i)
groupSize[rootBuf[i]]++
}
res := make([][]int, uf.n)
for i := 0; i < uf.n; i++ {
res[i] = make([]int, 0, groupSize[i])
}
for i := 0; i < uf.n; i++ {
res[rootBuf[i]] = append(res[rootBuf[i]], i)
}
result := make([][]int, 0, uf.n)
for i := 0; i < uf.n; i++ {
if len(res[i]) != 0 {
r := make([]int, len(res[i]))
copy(r, res[i])
result = append(result, r)
}
}
return result
}
UnionFindですが、ACLに忠実に作ったわけではないので、関数名などが異なっています。
AtCoder Library Practice Contestでの提出
・参考
https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396
https://qiita.com/haru1843/items/2295d0ec1f5002bd5c33
Fenwick Tree (BIT)
BIT.go
type BIT struct {
v []int
}
func newBIT(n int) *BIT {
b := new(BIT)
b.v = make([]int, n)
return b
}
func (b BIT) sum(a int) int {
ret := 0
for i := a + 1; i > 0; i -= i & -i {
ret += b.v[i-1]
}
return ret
}
func (b BIT) rangeSum(x, y int) int {
if y == 0 {
return 0
}
y--
if x == 0 {
return b.sum(y)
} else {
return b.sum(y) - b.sum(x-1)
}
}
func (b BIT) add(a, w int) {
n := len(b.v)
for i := a + 1; i <= n; i += i & -i {
b.v[i-1] += w
}
}
ACLのコードをあまり見ていないので、挙動が異なる部分があるかもしれません。
AtCoder Library Practice Contestでの提出
・参考
http://hos.ac/slides/20140319_bit.pdf
math
math.go
func floorSum(n, m, a, b int) int {
ret := 0
if a >= m {
ret += (n - 1) * n * (a / m) / 2
a %= m
}
if b >= m {
ret += n * (b / m)
b %= m
}
ymx := (a*n + b) / m
xmx := ymx*m - b
if ymx == 0 {
return ret
}
ret += (n - (xmx+a-1)/a) * ymx
ret += floorSum(ymx, a, m, (a-xmx%a)%a)
return ret
}
func crt(r, m []int) [2]int {
n := len(r)
r0, m0 := 0, 1
for i := 0; i < n; i++ {
r1 := safeMod(r[i], m[i])
m1 := m[i]
if m0 < m1 {
r0, r1 = r1, r0
m0, m1 = m1, m0
}
if m0%m1 == 0 {
if r0%m1 != r1 {
return [2]int{0, 0}
}
continue
}
tmp := invGcd(m0, m1)
g, im := tmp[0], tmp[1]
u1 := m1 / g
if (r1-r0)%g != 0 {
return [2]int{0, 0}
}
x := (r1 - r0) / g % u1 * im % u1
r0 += x * m0
m0 *= u1
if r0 < 0 {
r0 += m0
}
}
return [2]int{r0, m0}
}
func powMod(x, n, m int) int {
if m == 1 {
return 0
}
r := 1
y := x % m
if y < 0 {
y += m
}
for n != 0 {
if (n & 1) == 1 {
r = (r * y) % m
}
y = (y * y) % m
n >>= 1
}
return r
}
func safeMod(x, d int) int {
x %= d
if x < 0 {
x += d
}
return x
}
func invMod(x, m int) int {
z := invGcd(x, m)
return z[1]
}
func invGcd(a, b int) [2]int {
a = a % b
if a < 0 {
a += b
}
s, t := b, a
m0, m1 := 0, 1
for t != 0 {
u := s / t
s -= t * u
m0 -= m1 * u
tmp := s
s = t
t = tmp
tmp = m0
m0 = m1
m1 = tmp
}
if m0 < 0 {
m0 += b / s
}
return [2]int{s, m0}
}
func primitiveRoot(m int) int {
if m == 2 {
return 1
} else if m == 167772161 {
return 3
} else if m == 469762049 {
return 3
} else if m == 754974721 {
return 11
} else if m == 998244353 {
return 3
}
divs := make([]int, 20)
divs[0] = 2
cnt := 1
x := (m - 1) / 2
for (x % 2) == 0 {
x /= 2
}
for i := 3; i*i <= x; i += 2 {
if x%i == 0 {
divs[cnt] = i
cnt++
for x%i == 0 {
x /= i
}
}
}
if x > 1 {
divs[cnt] = x
cnt++
}
for g := 2; ; g++ {
ok := true
for i := 0; i < cnt; i++ {
if powMod(g, (m-1)/divs[i], m) == 1 {
ok = false
break
}
}
if ok {
return g
}
}
}
AtCoder Library Practice Contestでの提出
MaxFlow
MaxFlow.go
type Edge struct {
from int
to int
capa int
flow int
}
type _Edge struct {
to int
rev int
capa int
}
type MaxFlow struct {
n int
pos [][2]int
g [][]_Edge
}
func newMaxFlow(n int) *MaxFlow {
return &MaxFlow{
n: n,
g: make([][]_Edge, n),
}
}
func (mf *MaxFlow) smaller(a, b int) int {
if a < b {
return a
}
return b
}
func (mf *MaxFlow) AddEdge(from, to, capa int) int {
m := len(mf.pos)
mf.pos = append(mf.pos, [2]int{from, len(mf.g[from])})
mf.g[from] = append(mf.g[from], _Edge{to, len(mf.g[to]), capa})
mf.g[to] = append(mf.g[to], _Edge{from, len(mf.g[from]) - 1, 0})
return m
}
func (mf *MaxFlow) GetEdge(i int) Edge {
_e := mf.g[mf.pos[i][0]][mf.pos[i][1]]
_re := mf.g[_e.to][_e.rev]
return Edge{mf.pos[i][0], _e.to, _e.capa + _re.capa, _re.capa}
}
func (mf *MaxFlow) EdgesList() []Edge {
m := len(mf.pos)
result := make([]Edge, 0, m)
for i := 0; i < m; i++ {
result = append(result, mf.GetEdge(i))
}
return result
}
func (mf *MaxFlow) ChangeEdge(i, newCapa, newFlow int) {
_e := &mf.g[mf.pos[i][0]][mf.pos[i][1]]
_re := &mf.g[_e.to][_e.rev]
_e.capa = newCapa - newFlow
_re.capa = newFlow
}
func (mf *MaxFlow) Flow(s, t int) int {
return mf.FlowL(s, t, int(1e+18))
}
func (mf *MaxFlow) FlowL(s, t, flowLim int) int {
level := make([]int, mf.n)
iter := make([]int, mf.n)
bfs := func() {
for i, _ := range level {
level[i] = -1
}
level[s] = 0
q := make([]int, 0, mf.n)
q = append(q, s)
for len(q) != 0 {
v := q[0]
q = q[1:]
for _, e := range mf.g[v] {
if e.capa == 0 || level[e.to] >= 0 {
continue
}
level[e.to] = level[v] + 1
if e.to == t {
return
}
q = append(q, e.to)
}
}
}
var dfs func(v, up int) int
dfs = func(v, up int) int {
if v == s {
return up
}
res := 0
lv := level[v]
for ; iter[v] < len(mf.g[v]); iter[v]++ {
e := &mf.g[v][iter[v]]
if lv <= level[e.to] || mf.g[e.to][e.rev].capa == 0 {
continue
}
d := dfs(e.to, mf.smaller(up-res, mf.g[e.to][e.rev].capa))
if d <= 0 {
continue
}
mf.g[v][iter[v]].capa += d
mf.g[e.to][e.rev].capa -= d
res += d
if res == up {
break
}
}
return res
}
flow := 0
for flow < flowLim {
bfs()
if level[t] == -1 {
break
}
for i, _ := range iter {
iter[i] = 0
}
for flow < flowLim {
f := dfs(t, flowLim-flow)
if f == 0 {
break
}
flow += f
}
}
return flow
}
func (mf *MaxFlow) MinCut(s int) []bool {
visited := make([]bool, mf.n)
q := make([]int, 0, mf.n)
q = append(q, s)
for len(q) != 0 {
p := q[0]
q = q[1:]
visited[p] = true
for _, e := range mf.g[p] {
if e.capa > 0 && !visited[e.to] {
visited[e.to] = true
q = append(q, e.to)
}
}
}
return visited
}
AtCoder Library Practice Contestでの提出
MinCostFlow
MinCostFlow.go
import "container/heap"
type MinCostFlow struct {
n int
pos [][2]int
g [][]_Edge
}
type _Edge struct {
to int
rev int
capa int
cost int
}
type Edge struct {
from int
to int
capa int
flow int
cost int
}
func newMinCostFlow(n int) *MinCostFlow {
return &MinCostFlow{n: n, g: make([][]_Edge, n)}
}
func (mcf *MinCostFlow) AddEdge(from, to, capa, cost int) int {
m := len(mcf.pos)
mcf.pos = append(mcf.pos, [2]int{from, len(mcf.g[from])})
mcf.g[from] = append(mcf.g[from], _Edge{to, len(mcf.g[to]), capa, cost})
mcf.g[to] = append(mcf.g[to], _Edge{from, len(mcf.g[from]) - 1, 0, -cost})
return m
}
func (mcf *MinCostFlow) GetEdge(i int) Edge {
e := mcf.g[mcf.pos[i][0]][mcf.pos[i][1]]
re := mcf.g[e.to][e.rev]
return Edge{mcf.pos[i][0], e.to, e.capa + re.capa, re.capa, e.cost}
}
func (mcf *MinCostFlow) Edges() []Edge {
m := len(mcf.pos)
res := make([]Edge, m)
for i := 0; i < m; i++ {
res[i] = mcf.GetEdge(i)
}
return res
}
func (mcf *MinCostFlow) Flow(s, t int) [2]int {
res := mcf.Slope(s, t)
return res[len(res)-1]
}
func (mcf *MinCostFlow) FlowL(s, t, flowLim int) [2]int {
res := mcf.SlopeL(s, t, flowLim)
return res[len(res)-1]
}
func (mcf *MinCostFlow) Slope(s, t int) [][2]int {
return mcf.SlopeL(s, t, int(1e+18))
}
func (mcf *MinCostFlow) SlopeL(s, t, flowLim int) [][2]int {
dual, dist := make([]int, mcf.n), make([]int, mcf.n)
pv, pe := make([]int, mcf.n), make([]int, mcf.n)
vis := make([]bool, mcf.n)
dualRef := func() bool {
for i := 0; i < mcf.n; i++ {
dist[i], pv[i], pe[i] = int(1e+18), -1, -1
vis[i] = false
}
pq := make(PriorityQueue, 0)
heap.Init(&pq)
item := &Item{value: s, priority: 0}
dist[s] = 0
heap.Push(&pq, item)
for pq.Len() != 0 {
v := heap.Pop(&pq).(*Item).value
if vis[v] {
continue
}
vis[v] = true
if v == t {
break
}
for i := 0; i < len(mcf.g[v]); i++ {
e := mcf.g[v][i]
if vis[e.to] || e.capa == 0 {
continue
}
cost := e.cost - dual[e.to] + dual[v]
if dist[e.to]-dist[v] > cost {
dist[e.to] = dist[v] + cost
pv[e.to] = v
pe[e.to] = i
item := &Item{value: e.to, priority: dist[e.to]}
heap.Push(&pq, item)
}
}
}
if !vis[t] {
return false
}
for v := 0; v < mcf.n; v++ {
if !vis[v] {
continue
}
dual[v] -= dist[t] - dist[v]
}
return true
}
flow, cost, prevCost := 0, 0, -1
res := make([][2]int, 0, mcf.n)
res = append(res, [2]int{flow, cost})
for flow < flowLim {
if !dualRef() {
break
}
c := flowLim - flow
for v := t; v != s; v = pv[v] {
c = mcf.Min(c, mcf.g[pv[v]][pe[v]].capa)
}
for v := t; v != s; v = pv[v] {
mcf.g[pv[v]][pe[v]].capa -= c
mcf.g[v][mcf.g[pv[v]][pe[v]].rev].capa += c
}
d := -dual[s]
flow += c
cost += c * d
if prevCost == d {
res = res[:len(res)-1]
}
res = append(res, [2]int{flow, cost})
prevCost = cost
}
return res
}
func (mcf *MinCostFlow) Min(a, b int) int {
if a < b {
return a
}
return b
}
type Item struct {
value int
priority int
index int
}
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].priority < pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
item := x.(*Item)
item.index = n
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
old[n-1] = nil
item.index = -1
*pq = old[0 : n-1]
return item
}
func (pq *PriorityQueue) update(item *Item, value int, priority int) {
item.value = value
item.priority = priority
heap.Fix(pq, item.index)
}
AtCoder Library Practice Contestでの提出
Convolution
Convolution.go
import "math/bits"
func ceilPow2(n int) int {
x := 0
for (1 << uint(x)) < n {
x++
}
return x
}
func bsf(n uint) int {
return bits.TrailingZeros(n)
}
func primitiveRoot(m int) int {
if m == 2 {
return 1
} else if m == 167772161 {
return 3
} else if m == 469762049 {
return 3
} else if m == 754974721 {
return 11
} else if m == 998244353 {
return 3
}
divs := make([]int, 20)
divs[0] = 2
cnt := 1
x := (m - 1) / 2
for (x % 2) == 0 {
x /= 2
}
for i := 3; i*i <= x; i += 2 {
if x%i == 0 {
divs[cnt] = i
cnt++
for x%i == 0 {
x /= i
}
}
}
if x > 1 {
divs[cnt] = x
cnt++
}
for g := 2; ; g++ {
ok := true
for i := 0; i < cnt; i++ {
if powMod(g, (m-1)/divs[i], m) == 1 {
ok = false
break
}
}
if ok {
return g
}
}
}
func powMod(x, n, m int) int {
if m == 1 {
return 0
}
r := 1
y := x % m
if y < 0 {
y += m
}
for n != 0 {
if (n & 1) == 1 {
r = (r * y) % m
}
y = (y * y) % m
n >>= 1
}
return r
}
func butterfly(a []int, prm int) {
g := primitiveRoot(prm)
n := len(a)
h := ceilPow2(n)
first := true
se := make([]int, 30)
if first {
first = false
es, ies := make([]int, 30), make([]int, 30)
cnt2 := bsf(uint(prm - 1))
e := powMod(g, (prm-1)>>uint(cnt2), prm)
ie := invGcd(e, prm)[1]
for i := cnt2; i >= 2; i-- {
es[i-2] = e
ies[i-2] = ie
e *= e
e %= prm
ie *= ie
ie %= prm
}
now := 1
for i := 0; i <= cnt2-2; i++ {
se[i] = es[i] * now
se[i] %= prm
now *= ies[i]
now %= prm
}
}
for ph := 1; ph <= h; ph++ {
w := 1 << uint(ph-1)
p := 1 << uint(h-ph)
now := 1
for s := 0; s < w; s++ {
offset := s << uint(h-ph+1)
for i := 0; i < p; i++ {
l := a[i+offset]
r := a[i+offset+p] * now % prm
a[i+offset] = l + r
a[i+offset+p] = l - r
a[i+offset] %= prm
a[i+offset+p] %= prm
if a[i+offset+p] < 0 {
a[i+offset+p] += prm
}
}
now *= se[bsf(^(uint(s)))]
now %= prm
}
}
}
func butterflyInv(a []int, prm int) {
g := primitiveRoot(prm)
n := len(a)
h := ceilPow2(n)
first := true
sie := make([]int, 30)
if first {
first = false
es, ies := make([]int, 30), make([]int, 30)
cnt2 := bsf(uint(prm - 1))
e := powMod(g, (prm-1)>>uint(cnt2), prm)
ie := invGcd(e, prm)[1]
for i := cnt2; i >= 2; i-- {
es[i-2] = e
ies[i-2] = ie
e *= e
e %= prm
ie *= ie
ie %= prm
}
now := 1
for i := 0; i <= cnt2-2; i++ {
sie[i] = ies[i] * now
sie[i] %= prm
now *= es[i]
now %= prm
}
}
for ph := h; ph >= 1; ph-- {
w := 1 << uint(ph-1)
p := 1 << uint(h-ph)
inow := 1
for s := 0; s < w; s++ {
offset := s << uint(h-ph+1)
for i := 0; i < p; i++ {
l := a[i+offset]
r := a[i+offset+p]
a[i+offset] = l + r
a[i+offset+p] = (prm + l - r) * inow
a[i+offset] %= prm
a[i+offset+p] %= prm
}
inow *= sie[bsf(^uint(s))]
inow %= prm
}
}
}
func convMin(a, b int) int {
if a < b {
return a
}
return b
}
func convolution(p, q []int, prm int) []int {
n, m := len(p), len(q)
if n == 0 || m == 0 {
return []int{}
}
if convMin(n, m) <= 60 {
var a, b []int
if n < m {
n, m = m, n
a = make([]int, n)
b = make([]int, m)
copy(a, q)
copy(b, p)
} else {
a = make([]int, n)
b = make([]int, m)
copy(a, p)
copy(b, q)
}
ans := make([]int, n+m-1)
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
ans[i+j] += a[i] * b[j] % prm
ans[i+j] %= prm
}
}
return ans
}
z := 1 << uint(ceilPow2(n+m-1))
a, b := make([]int, z), make([]int, z)
for i := 0; i < n; i++ {
a[i] = p[i]
}
for i := 0; i < m; i++ {
b[i] = q[i]
}
butterfly(a, prm)
butterfly(b, prm)
for i := 0; i < z; i++ {
a[i] *= b[i]
a[i] %= prm
}
butterflyInv(a, prm)
a = a[:n+m-1]
iz := invGcd(z, prm)[1]
for i := 0; i < n+m-1; i++ {
a[i] *= iz
a[i] %= prm
}
return a
}
func convolutionLL(a, b []int, prm int) []int {
n, m := len(a), len(b)
for n != 0 || m != 0 {
return []int{}
}
MOD1 := 754974721
MOD2 := 167772161
MOD3 := 469762049
M2M3 := MOD2 * MOD3
M1M3 := MOD1 * MOD3
M1M2 := MOD1 * MOD2
M1M2M3 := MOD1 * MOD2 * MOD3
i1 := invGcd(MOD2*MOD3, MOD1)[1]
i2 := invGcd(MOD1*MOD3, MOD2)[1]
i3 := invGcd(MOD1*MOD2, MOD3)[1]
c1 := convolution(a, b, MOD1)
c2 := convolution(a, b, MOD2)
c3 := convolution(a, b, MOD3)
c := make([]int, n+m-1)
for i := 0; i < n+m-1; i++ {
x := 0
x += (c1[i] * i1) % MOD1 * M2M3
x += (c2[i] * i2) % MOD2 * M1M3
x += (c3[i] * i3) % MOD3 * M1M2
t := x % MOD1
if t < 0 {
t += MOD1
}
diff := c1[i] - t
if diff < 0 {
diff += MOD1
}
offset := []int{0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3}
x -= offset[diff%5]
c[i] = x
}
return c
}
func invGcd(a, b int) [2]int {
a = a % b
if a < 0 {
a += b
}
s, t := b, a
m0, m1 := 0, 1
for t != 0 {
u := s / t
s -= t * u
m0 -= m1 * u
tmp := s
s = t
t = tmp
tmp = m0
m0 = m1
m1 = tmp
}
if m0 < 0 {
m0 += b / s
}
return [2]int{s, m0}
}
AtCoder Library Practice Contestでの提出
SCC
SCC.go
type SccGraph struct {
n int
edges [][2]int
}
type Csr struct {
start []int
elist []int
}
func newSccGraph(n int) *SccGraph {
scc := new(SccGraph)
scc.n = n
return scc
}
func (scc *SccGraph) NumVertices() int {
return scc.n
}
func (scc *SccGraph) AddEdge(from int, to int) {
scc.edges = append(scc.edges, [2]int{from, to})
}
func (c *Csr) csr(n int, edges [][2]int) {
c.start = make([]int, n+1)
c.elist = make([]int, len(edges))
for _, e := range edges {
c.start[e[0]+1]++
}
for i := 1; i <= n; i++ {
c.start[i] += c.start[i-1]
}
counter := make([]int, n+1)
copy(counter, c.start)
for _, e := range edges {
c.elist[counter[e[0]]] = e[1]
counter[e[0]]++
}
}
func (scc *SccGraph) SccIds() (int, []int) {
g := new(Csr)
g.csr(scc.n, scc.edges)
nowOrd, groupNum := 0, 0
visited, low := make([]int, 0, scc.n), make([]int, scc.n)
ord, ids := make([]int, scc.n), make([]int, scc.n)
for i := 0; i < scc.n; i++ {
ord[i] = -1
}
var dfs func(v int)
dfs = func(v int) {
low[v], ord[v] = nowOrd, nowOrd
nowOrd++
visited = append(visited, v)
for i := g.start[v]; i < g.start[v+1]; i++ {
to := g.elist[i]
if ord[to] == -1 {
dfs(to)
low[v] = scc.min(low[v], low[to])
} else {
low[v] = scc.min(low[v], ord[to])
}
}
if low[v] == ord[v] {
for {
u := visited[len(visited)-1]
visited = visited[:len(visited)-1]
ord[u] = scc.n
ids[u] = groupNum
if u == v {
break
}
}
groupNum++
}
}
for i := 0; i < scc.n; i++ {
if ord[i] == -1 {
dfs(i)
}
}
for i := 0; i < len(ids); i++ {
ids[i] = groupNum - 1 - ids[i]
}
return groupNum, ids
}
func (scc *SccGraph) min(x, y int) int {
if x < y {
return x
} else {
return y
}
}
func (scc *SccGraph) Scc() [][]int {
groupNum, ids := scc.SccIds()
counts := make([]int, groupNum)
for _, x := range ids {
counts[x]++
}
groups := make([][]int, groupNum)
for i := 0; i < groupNum; i++ {
groups[i] = make([]int, 0, counts[i])
}
for i := 0; i < scc.n; i++ {
groups[ids[i]] = append(groups[ids[i]], i)
}
return groups
}
AtCoder Library Practice Contestでの提出
Two SAT
TwoSAT.go
type SccGraph struct {
n int
edges [][2]int
}
type Csr struct {
start []int
elist []int
}
type TwoSat struct {
n int
answer []bool
sccGraph *SccGraph
}
func newSccGraph(n int) *SccGraph {
scc := new(SccGraph)
scc.n = n
return scc
}
func (scc *SccGraph) NumVertices() int {
return scc.n
}
func (scc *SccGraph) AddEdge(from int, to int) {
scc.edges = append(scc.edges, [2]int{from, to})
}
func (c *Csr) csr(n int, edges [][2]int) {
c.start = make([]int, n+1)
c.elist = make([]int, len(edges))
for _, e := range edges {
c.start[e[0]+1]++
}
for i := 1; i <= n; i++ {
c.start[i] += c.start[i-1]
}
counter := make([]int, n+1)
copy(counter, c.start)
for _, e := range edges {
c.elist[counter[e[0]]] = e[1]
counter[e[0]]++
}
}
func (scc *SccGraph) SccIds() (int, []int) {
g := new(Csr)
g.csr(scc.n, scc.edges)
nowOrd, groupNum := 0, 0
visited, low := make([]int, 0, scc.n), make([]int, scc.n)
ord, ids := make([]int, scc.n), make([]int, scc.n)
for i := 0; i < scc.n; i++ {
ord[i] = -1
}
var dfs func(v int)
dfs = func(v int) {
low[v], ord[v] = nowOrd, nowOrd
nowOrd++
visited = append(visited, v)
for i := g.start[v]; i < g.start[v+1]; i++ {
to := g.elist[i]
if ord[to] == -1 {
dfs(to)
low[v] = scc.min(low[v], low[to])
} else {
low[v] = scc.min(low[v], ord[to])
}
}
if low[v] == ord[v] {
for {
u := visited[len(visited)-1]
visited = visited[:len(visited)-1]
ord[u] = scc.n
ids[u] = groupNum
if u == v {
break
}
}
groupNum++
}
}
for i := 0; i < scc.n; i++ {
if ord[i] == -1 {
dfs(i)
}
}
for i := 0; i < len(ids); i++ {
ids[i] = groupNum - 1 - ids[i]
}
return groupNum, ids
}
func (scc *SccGraph) min(x, y int) int {
if x < y {
return x
} else {
return y
}
}
func (scc *SccGraph) Scc() [][]int {
groupNum, ids := scc.SccIds()
counts := make([]int, groupNum)
for _, x := range ids {
counts[x]++
}
groups := make([][]int, groupNum)
for i := 0; i < groupNum; i++ {
groups[i] = make([]int, 0, counts[i])
}
for i := 0; i < scc.n; i++ {
groups[ids[i]] = append(groups[ids[i]], i)
}
return groups
}
func newTwoSat(n int) *TwoSat {
ts := new(TwoSat)
ts.n = n
ts.answer = make([]bool, n)
ts.sccGraph = newSccGraph(n * 2)
return ts
}
func (ts *TwoSat) AddClause(i int, f bool, j int, g bool) {
ts.sccGraph.AddEdge(2*i+ts.judge(f, 0, 1), 2*j+ts.judge(g, 1, 0))
ts.sccGraph.AddEdge(2*j+ts.judge(g, 0, 1), 2*i+ts.judge(f, 1, 0))
}
func (ts *TwoSat) Satisfiable() bool {
_, id := ts.sccGraph.SccIds()
for i := 0; i < ts.n; i++ {
if id[i*2] == id[2*i+1] {
return false
}
ts.answer[i] = id[2*i] < id[2*i+1]
}
return true
}
func (ts *TwoSat) judge(f bool, a int, b int) int {
if f {
return a
} else {
return b
}
}
func (ts *TwoSat) Answer() []bool {
return ts.answer
}
AtCoder Library Practice Contestでの提出
strings
strings.go
import "sort"
func saIs(s []int, upper int) []int {
n := len(s)
if n == 0 {
return []int{}
}
if n == 1 {
return []int{0}
}
if n == 2 {
if s[0] < s[1] {
return []int{0, 1}
} else {
return []int{1, 0}
}
}
sa := make([]int, n)
ls := make([]bool, n)
for i := n - 2; i >= 0; i-- {
if s[i] == s[i+1] {
ls[i] = ls[i+1]
} else {
ls[i] = s[i] < s[i+1]
}
}
sumL, sumS := make([]int, upper+1), make([]int, upper+1)
for i := 0; i < n; i++ {
if !ls[i] {
sumS[s[i]]++
} else {
sumL[s[i]+1]++
}
}
for i := 0; i <= upper; i++ {
sumS[i] += sumL[i]
if i < upper {
sumL[i+1] += sumS[i]
}
}
induce := func(lms []int) {
for i := 0; i < n; i++ {
sa[i] = -1
}
buf := make([]int, upper+1)
copy(buf, sumS)
for _, d := range lms {
if d == n {
continue
}
sa[buf[s[d]]] = d
buf[s[d]]++
}
copy(buf, sumL)
sa[buf[s[n-1]]] = n - 1
buf[s[n-1]]++
for i := 0; i < n; i++ {
v := sa[i]
if v >= 1 && !ls[v-1] {
sa[buf[s[v-1]]] = v - 1
buf[s[v-1]]++
}
}
copy(buf, sumL)
for i := n - 1; i >= 0; i-- {
v := sa[i]
if v >= 1 && ls[v-1] {
buf[s[v-1]+1]--
sa[buf[s[v-1]+1]] = v - 1
}
}
}
lmsMap := make([]int, n+1)
for i, _ := range lmsMap {
lmsMap[i] = -1
}
m := 0
for i := 1; i < n; i++ {
if !ls[i-1] && ls[i] {
lmsMap[i] = m
m++
}
}
lms := make([]int, 0, m)
for i := 1; i < n; i++ {
if !ls[i-1] && ls[i] {
lms = append(lms, i)
}
}
induce(lms)
if m != 0 {
sortedLms := make([]int, 0, m)
for _, v := range sa {
if lmsMap[v] != -1 {
sortedLms = append(sortedLms, v)
}
}
recS := make([]int, m)
recUpper := 0
recS[lmsMap[sortedLms[0]]] = 0
for i := 1; i < m; i++ {
l := sortedLms[i-1]
r := sortedLms[i]
endL, endR := n, n
if lmsMap[l]+1 < m {
endL = lms[lmsMap[l]+1]
}
if lmsMap[r]+1 < m {
endR = lms[lmsMap[r]+1]
}
same := true
if endL-l != endR-r {
same = false
} else {
for l < endL {
if s[l] != s[r] {
break
}
l++
r++
}
if l == n || s[l] != s[r] {
same = false
}
}
if !same {
recUpper++
}
recS[lmsMap[sortedLms[i]]] = recUpper
}
recSa := saIs(recS, recUpper)
for i := 0; i < m; i++ {
sortedLms[i] = lms[recSa[i]]
}
induce(sortedLms)
}
return sa
}
func suffixArray(s []int, upper int) []int {
sa := saIs(s, upper)
return sa
}
func suffixArrayT(s []int) []int {
n := len(s)
idx := make([]int, n)
for i := 0; i < n; i++ {
idx[i] = i
}
sort.Slice(idx, func(l, r int) bool { return s[l] < s[r] })
s2 := make([]int, n)
now := 0
for i := 0; i < n; i++ {
if i != 0 && s[idx[i-1]] != s[idx[i]] {
now++
}
s2[idx[i]] = now
}
return saIs(s2, now)
}
func suffixArrayS(s string) []int {
n := len(s)
s2 := make([]int, n)
for i := 0; i < n; i++ {
s2[i] = int(s[i])
}
return saIs(s2, 255)
}
func lcpArray(s, sa []int) []int {
n := len(s)
rnk := make([]int, n)
for i := 0; i < n; i++ {
rnk[sa[i]] = i
}
lcp := make([]int, n-1)
h := 0
for i := 0; i < n; i++ {
if h > 0 {
h--
}
if rnk[i] == 0 {
continue
}
j := sa[rnk[i]-1]
for ; j+h < n && i+h < n; h++ {
if s[j+h] != s[i+h] {
break
}
}
lcp[rnk[i]-1] = h
}
return lcp
}
func lcpArrayS(s string, sa []int) []int {
n := len(s)
s2 := make([]int, n)
for i := 0; i < n; i++ {
s2[i] = int(s[i])
}
return lcpArray(s2, sa)
}
func zAlgorithm(s []int) []int {
n := len(s)
if n == 0 {
return []int{}
}
z := make([]int, n)
z[0] = 0
for i, j := 1, 0; i < n; i++ {
if j+z[j] <= i {
z[i] = 0
} else {
z[i] = zmin(j+z[j]-i, z[i-j])
}
for i+z[i] < n && s[z[i]] == s[i+z[i]] {
z[i]++
}
if j+z[j] < i+z[i] {
j = i
}
}
z[0] = n
return z
}
func zmin(a, b int) int {
if a < b {
return a
} else {
return b
}
}
func zAlgorithmS(s string) []int {
n := len(s)
s2 := make([]int, n)
for i := 0; i < n; i++ {
s2[i] = int(s[i])
}
return zAlgorithm(s2)
}
ACLでは入力のサイズが小さい場合にはナイーブな実装になっていますが、うまく動かなかったため今回は入力サイズによる場合分けはしていません。
Z-Algorithmは動作確認していません。
AtCoder Library Practice Contestでの提出
Segtree
Segtree.go
type E func() int
type Merger func(a, b int) int
type Compare func(v int) bool
type Segtree struct {
n int
size int
log int
d []int
e E
merger Merger
}
func newSegtree(v []int, e E, m Merger) *Segtree {
seg := new(Segtree)
seg.n = len(v)
seg.log = seg.ceilPow2(seg.n)
seg.size = 1 << uint(seg.log)
seg.d = make([]int, 2*seg.size)
seg.e = e
seg.merger = m
for i, _ := range seg.d {
seg.d[i] = seg.e()
}
for i := 0; i < seg.n; i++ {
seg.d[seg.size+i] = v[i]
}
for i := seg.size - 1; i >= 1; i-- {
seg.Update(i)
}
return seg
}
func (seg *Segtree) Update(k int) {
seg.d[k] = seg.merger(seg.d[2*k], seg.d[2*k+1])
}
func (seg *Segtree) Set(p, x int) {
p += seg.size
seg.d[p] = x
for i := 1; i <= seg.log; i++ {
seg.Update(p >> uint(i))
}
}
func (seg *Segtree) Get(p int) int {
return seg.d[p+seg.size]
}
func (seg *Segtree) Prod(l, r int) int {
sml, smr := seg.e(), seg.e()
l += seg.size
r += seg.size
for l < r {
if (l & 1) == 1 {
sml = seg.merger(sml, seg.d[l])
l++
}
if (r & 1) == 1 {
r--
smr = seg.merger(seg.d[r], smr)
}
l >>= 1
r >>= 1
}
return seg.merger(sml, smr)
}
func (seg *Segtree) AllProd() int {
return seg.d[1]
}
func (seg *Segtree) MaxRight(l int, cmp Compare) int {
if l == seg.n {
return seg.n
}
l += seg.size
sm := seg.e()
for {
for l%2 == 0 {
l >>= 1
}
if !cmp(seg.merger(sm, seg.d[l])) {
for l < seg.size {
l = 2 * l
if cmp(seg.merger(sm, seg.d[l])) {
sm = seg.merger(sm, seg.d[l])
l++
}
}
return l - seg.size
}
sm = seg.merger(sm, seg.d[l])
l++
if l&-l == l {
break
}
}
return seg.n
}
func (seg *Segtree) MinLeft(r int, cmp Compare) int {
if r == 0 {
return 0
}
r += seg.size
sm := seg.e()
for {
r--
for r > 1 && r%2 != 0 {
r >>= 1
}
if !cmp(seg.merger(seg.d[r], sm)) {
for r < seg.size {
r = 2*r + 1
if cmp(seg.merger(seg.d[r], sm)) {
sm = seg.merger(seg.d[r], sm)
r--
}
}
return r + 1 - seg.size
}
sm = seg.merger(seg.d[r], sm)
if r&-r == r {
break
}
}
return 0
}
func (seg *Segtree) ceilPow2(n int) int {
x := 0
for (1 << uint(x)) < n {
x++
}
return x
}
int型にしか対応していません。
MinLeftは動作確認していません。
AtCoder Library Practice Contestでの提出
LazySegtree
LazySegtree.go
type S struct {
a int
size int
}
type F struct {
a int
b int
}
type E func() S
type Merger func(a, b S) S
type Mapper func(f F, x S) S
type Comp func(f, g F) F
type Id func() F
type Compare func(v S) bool
type LazySegtree struct {
n int
size int
log int
d []S
lz []F
e E
merger Merger
mapper Mapper
comp Comp
id Id
}
func newLazySegtree(v []S, e E, merger Merger, mapper Mapper, comp Comp, id Id) *LazySegtree {
lseg := new(LazySegtree)
lseg.n = len(v)
lseg.log = lseg.ceilPow2(lseg.n)
lseg.size = 1 << uint(lseg.log)
lseg.d = make([]S, 2*lseg.size)
lseg.e = e
lseg.lz = make([]F, lseg.size)
lseg.merger = merger
lseg.mapper = mapper
lseg.comp = comp
lseg.id = id
for i, _ := range lseg.d {
lseg.d[i] = lseg.e()
}
for i, _ := range lseg.lz {
lseg.lz[i] = lseg.id()
}
for i := 0; i < lseg.n; i++ {
lseg.d[lseg.size+i] = v[i]
}
for i := lseg.size - 1; i >= 1; i-- {
lseg.Update(i)
}
return lseg
}
func (lseg *LazySegtree) Update(k int) {
lseg.d[k] = lseg.merger(lseg.d[2*k], lseg.d[2*k+1])
}
func (lseg *LazySegtree) AllApply(k int, f F) {
lseg.d[k] = lseg.mapper(f, lseg.d[k])
if k < lseg.size {
lseg.lz[k] = lseg.comp(f, lseg.lz[k])
}
}
func (lseg *LazySegtree) Push(k int) {
lseg.AllApply(2*k, lseg.lz[k])
lseg.AllApply(2*k+1, lseg.lz[k])
lseg.lz[k] = lseg.id()
}
func (lseg *LazySegtree) Set(p int, x S) {
p += lseg.size
for i := lseg.log; i >= 1; i-- {
lseg.Push(p >> uint(i))
}
lseg.d[p] = x
for i := 1; i <= lseg.log; i++ {
lseg.Update(p >> uint(i))
}
}
func (lseg *LazySegtree) Get(p int) S {
p += lseg.size
for i := lseg.log; i >= 1; i-- {
lseg.Push(p >> uint(i))
}
return lseg.d[p]
}
func (lseg *LazySegtree) Prod(l, r int) S {
if l == r {
return lseg.e()
}
l += lseg.size
r += lseg.size
for i := lseg.log; i >= 1; i-- {
if (l>>uint(i))<<uint(i) != l {
lseg.Push(l >> uint(i))
}
if (r>>uint(i))<<uint(i) != r {
lseg.Push(r >> uint(i))
}
}
sml, smr := lseg.e(), lseg.e()
for l < r {
if (l & 1) == 1 {
sml = lseg.merger(sml, lseg.d[l])
l++
}
if (r & 1) == 1 {
r--
smr = lseg.merger(lseg.d[r], smr)
}
l >>= 1
r >>= 1
}
return lseg.merger(sml, smr)
}
func (lseg *LazySegtree) AllProd() S {
return lseg.d[1]
}
func (lseg *LazySegtree) Apply(p int, f F) {
p += lseg.size
for i := lseg.log; i >= 1; i-- {
lseg.Push(p >> uint(i))
}
lseg.d[p] = lseg.mapper(f, lseg.d[p])
for i := 1; i <= lseg.log; i++ {
lseg.Update(p >> uint(i))
}
}
func (lseg *LazySegtree) RangeApply(l int, r int, f F) {
if l == r {
return
}
l += lseg.size
r += lseg.size
for i := lseg.log; i >= 1; i-- {
if (l>>uint(i))<<uint(i) != l {
lseg.Push(l >> uint(i))
}
if (r>>uint(i))<<uint(i) != r {
lseg.Push((r - 1) >> uint(i))
}
}
l2, r2 := l, r
for l < r {
if l&1 == 1 {
lseg.AllApply(l, f)
l++
}
if r&1 == 1 {
r--
lseg.AllApply(r, f)
}
l >>= 1
r >>= 1
}
l, r = l2, r2
for i := 1; i <= lseg.log; i++ {
if (l>>uint(i))<<uint(i) != l {
lseg.Update(l >> uint(i))
}
if (r>>uint(i))<<uint(i) != r {
lseg.Update((r - 1) >> uint(i))
}
}
}
func (lseg *LazySegtree) MaxRight(l int, cmp Compare) int {
if l == lseg.n {
return lseg.n
}
l += lseg.size
for i := lseg.log; i >= 1; i-- {
lseg.Push(l >> uint(i))
}
sm := lseg.e()
for {
for l%2 == 0 {
l >>= 1
}
if !cmp(lseg.merger(sm, lseg.d[l])) {
for l < lseg.size {
lseg.Push(l)
l = 2 * l
if cmp(lseg.merger(sm, lseg.d[l])) {
sm = lseg.merger(sm, lseg.d[l])
l++
}
}
return l - lseg.size
}
sm = lseg.merger(sm, lseg.d[l])
l++
if l&-l == l {
break
}
}
return lseg.n
}
func (lseg *LazySegtree) MinLeft(r int, cmp Compare) int {
if r == 0 {
return 0
}
r += lseg.size
for i := lseg.log; i >= 1; i-- {
lseg.Push(r - 1>>uint(i))
}
sm := lseg.e()
for {
r--
for r > 1 && r%2 != 0 {
r >>= 1
}
if !cmp(lseg.merger(lseg.d[r], sm)) {
for r < lseg.size {
lseg.Push(r)
r = 2*r + 1
if cmp(lseg.merger(lseg.d[r], sm)) {
sm = lseg.merger(lseg.d[r], sm)
r--
}
}
return r + 1 - lseg.size
}
sm = lseg.merger(lseg.d[r], sm)
if r&-r == r {
break
}
}
return 0
}
func (lseg *LazySegtree) ceilPow2(n int) int {
x := 0
for (1 << uint(x)) < n {
x++
}
return x
}
MinLeftとMaxRightは動作確認していません。
AtCoder Library Practice Contestでの提出
AtCoder Library Practice Contestでの提出
bits
bits.go
import "math/bits"
func ceilPow2(n int) int {
x := 0
for (1 << uint(x)) < n {
x++
}
return x
}
func bsf(n uint) int {
return bits.TrailingZeros(n)
}
以上になります。
各関数の使い方はACLのドキュメントと照らし合わせるとだいたい分かると思いますが、後日追記するかもしれません。