A 1095 Smallest Kadomatsu Subsequence
If you write it in naive, it will be * O * (* N * 2 </ sup>). At first I thought it was a seg tree, but I didn't feel like I could search for the minimum value above the specified value. Therefore, it became a balanced binary search tree. While maintaining the balanced binary search tree on the left and right sides of the central gate pine, find the minimum value for convex and the minimum value larger than the middle size for concave. All you have to do is find the minimum size of the gate pine row. * O * ( N </ i> log N </ i>).
package main
import (
"bufio"
"fmt"
"math"
"os"
"strconv"
"strings"
)
var (
y uint = 88172645463325252
)
func xorshift() uint {
y ^= y << 7
y ^= y >> 9
return y
}
type treapNode struct {
value int
priority uint
count int
left *treapNode
right *treapNode
}
func newTreapNode(v int) *treapNode {
return &treapNode{v, xorshift(), 1, nil, nil}
}
func treapRotateRight(n *treapNode) *treapNode {
l := n.left
n.left = l.right
l.right = n
return l
}
func treapRotateLeft(n *treapNode) *treapNode {
r := n.right
n.right = r.left
r.left = n
return r
}
func treapInsert(n *treapNode, v int) *treapNode {
if n == nil {
return newTreapNode(v)
}
if n.value == v {
n.count++
return n
}
if n.value > v {
n.left = treapInsert(n.left, v)
if n.priority > n.left.priority {
n = treapRotateRight(n)
}
} else {
n.right = treapInsert(n.right, v)
if n.priority > n.right.priority {
n = treapRotateLeft(n)
}
}
return n
}
func treapDelete(n *treapNode, v int) *treapNode {
if n == nil {
panic("node is not found!")
}
if n.value > v {
n.left = treapDelete(n.left, v)
return n
}
if n.value < v {
n.right = treapDelete(n.right, v)
return n
}
// n.value == v
if n.count > 1 {
n.count--
return n
}
if n.left == nil && n.right == nil {
return nil
}
if n.left == nil {
n = treapRotateLeft(n)
} else if n.right == nil {
n = treapRotateRight(n)
} else {
// n.left != nil && n.right != nil
if n.left.priority < n.right.priority {
n = treapRotateRight(n)
} else {
n = treapRotateLeft(n)
}
}
return treapDelete(n, v)
}
func treapCount(n *treapNode) int {
if n == nil {
return 0
}
return n.count + treapCount(n.left) + treapCount(n.right)
}
func treapString(n *treapNode) string {
if n == nil {
return ""
}
result := make([]string, 0)
if n.left != nil {
result = append(result, treapString(n.left))
}
result = append(result, fmt.Sprintf("%d:%d", n.value, n.count))
if n.right != nil {
result = append(result, treapString(n.right))
}
return strings.Join(result, " ")
}
func treapMin(n *treapNode) int {
if n.left != nil {
return treapMin(n.left)
}
return n.value
}
func treapGEMin(n *treapNode, v int) int {
if n.value == v {
return v
}
if n.value > v {
if n.left != nil {
return treapGEMin(n.left, v)
}
return n.value
}
// n.value < v
if n.right != nil {
return treapGEMin(n.right, v)
}
return math.MaxInt64
}
func treapMax(n *treapNode) int {
if n.right != nil {
return treapMax(n.right)
}
return n.value
}
type treap struct {
root *treapNode
size int
}
func (t *treap) Insert(v int) {
t.root = treapInsert(t.root, v)
t.size++
}
func (t *treap) Delete(v int) {
t.root = treapDelete(t.root, v)
t.size--
}
func (t *treap) String() string {
return treapString(t.root)
}
func (t *treap) Count() int {
return t.size
}
func (t *treap) Min() int {
return treapMin(t.root)
}
func (t *treap) Max() int {
return treapMax(t.root)
}
func (t *treap) GEMin(v int) int {
return treapGEMin(t.root, v)
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func main() {
defer flush()
N := readInt()
A := make([]int, N)
for i := 0; i < N; i++ {
A[i] = readInt()
}
lt := &treap{}
rt := &treap{}
lt.Insert(A[0])
for i := 2; i < N; i++ {
rt.Insert(A[i])
}
result := math.MaxInt64
for i := 1; i < N-1; i++ {
a := lt.Min()
b := rt.Min()
if a <= A[i] && b <= A[i] {
// printf("Convex%d %d %d\n", a, A[i], b)
result = min(result, a+A[i]+b)
}
c := lt.GEMin(A[i])
d := rt.GEMin(A[i])
if c != math.MaxInt64 && d != math.MaxInt64 && c >= A[i] && d >= A[i] {
// printf("Concave%d %d %d\n", c, A[i], d)
result = min(result, c+A[i]+d)
}
lt.Insert(A[i])
rt.Delete(A[i+1])
}
if result == math.MaxInt64 {
println(-1)
} else {
println(result)
}
}
const (
ioBufferSize = 1 * 1024 * 1024 // 1 MB
)
var stdinScanner = func() *bufio.Scanner {
result := bufio.NewScanner(os.Stdin)
result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
result.Split(bufio.ScanWords)
return result
}()
func readString() string {
stdinScanner.Scan()
return stdinScanner.Text()
}
func readInt() int {
result, err := strconv.Atoi(readString())
if err != nil {
panic(err)
}
return result
}
func readInts(n int) []int {
result := make([]int, n)
for i := 0; i < n; i++ {
result[i] = readInt()
}
return result
}
var stdoutWriter = bufio.NewWriter(os.Stdout)
func flush() {
stdoutWriter.Flush()
}
func printf(f string, args ...interface{}) (int, error) {
return fmt.Fprintf(stdoutWriter, f, args...)
}
func println(args ...interface{}) (int, error) {
return fmt.Fprintln(stdoutWriter, args...)
}
Addendum: It also passes below. The cumulative Min from the left and right is used. Since the minimum value above the specified value cannot be searched, the concave type kadomatsu row when A i </ sub> is B is Even if it can be created, it may be said that it cannot be created. I think that it is a lie solution, but I am thinking of a counterexample, but I can not think of it. * O * (* N *).
from itertools import accumulate
INF = float('inf')
N, *A = map(int, open(0).read().split())
l = list(accumulate(A, min))
r = list(accumulate(A[::-1], min))[::-1]
result = INF
#In the case of convex type Kadomatsu row
for i in range(1, N - 1):
a = l[i - 1]
b = A[i]
c = r[i + 1]
if a <= b and c <= b:
result = min(result, a + b + c)
#In the case of concave type Kadomatsu row
for i in range(1, N - 1):
a = l[i - 1]
b = A[i]
c = r[i + 1]
if b <= a and b <= c:
result = min(result, a + b + c)
if result == INF:
print(-1)
else:
print(result)
If you write it in naive, it will be * O * (* N * 3 </ sup>). Even if you add it up, * O * (* N * 2 </ sup>). By inputting, it became * O * ( N </ i> log N </ i>) and solved.
from operator import add
from itertools import accumulate
class SegmentTree:
_f = None
_size = None
_offset = None
_data = None
def __init__(self, size, f):
self._f = f
self._size = size
t = 1
while t < size:
t *= 2
self._offset = t - 1
self._data = [0] * (t * 2 - 1)
def build(self, iterable):
f = self._f
data = self._data
data[self._offset:self._offset + self._size] = iterable
for i in range(self._offset - 1, -1, -1):
data[i] = f(data[i * 2 + 1], data[i * 2 + 2])
def query(self, start, stop):
def iter_segments(data, l, r):
while l < r:
if l & 1 == 0:
yield data[l]
if r & 1 == 0:
yield data[r - 1]
l = l // 2
r = (r - 1) // 2
f = self._f
it = iter_segments(self._data, start + self._offset,
stop + self._offset)
result = next(it)
for e in it:
result = f(result, e)
return result
N, *A = map(int, open(0).read().split())
a = list(accumulate(A))
st = SegmentTree(N, add)
st.build(a)
result = 0
result += st.query(0, N)
for i in range(1, N):
result += st.query(i, N) - a[i - 1] * (N - i)
print(result)
Addendum: A i </ sub> is added to the answer when l = 1, .., i and r = i, ..., N, so the number of times it is added to the answer is (i). + 1) × (N --i) It was easy to think that it would be. * O * (* N *).
N, *A = map(int, open(0).read().split())
result = 0
for i in range(N):
# l = 0 .. i, r = i .. N - 1
result += A[i] * (i + 1) * (N - i)
print(result)
Addendum: Some people said that they solved it with Sparse table instead of Seg tree, but I made a mistake in Disjoint sparse table? Sparse table requires idempotency in operation, but unlike Min, Sum does not. Disjoint I didn't have an implementation of sparse table so I couldn't try it.
Addendum: Implemented Disjoint sparse table.
from itertools import accumulate
from operator import add
class DisjointSparseTable:
_f = None
_data = None
_lookup = None
def __init__(self, a, f):
self._f = f
b = 0
while (1 << b) <= len(a):
b += 1
_data = [[0] * len(a) for _ in range(b)]
_data[0] = a[:]
for i in range(1, b):
shift = 1 << i
for j in range(0, len(a), shift << 1):
t = min(j + shift, len(a))
_data[i][t - 1] = a[t - 1]
for k in range(t - 2, j - 1, -1):
_data[i][k] = f(a[k], _data[i][k + 1])
if t >= len(a):
break
_data[i][t] = a[t]
r = min(t + shift, len(a))
for k in range(t + 1, r):
_data[i][k] = f(_data[i][k - 1], a[k])
self._data = _data
_lookup = [0] * (1 << b)
for i in range(2, len(_lookup)):
_lookup[i] = _lookup[i >> 1] + 1
self._lookup = _lookup
def query(self, start, stop):
stop -= 1
if start >= stop:
return self._data[0][start]
p = self._lookup[start ^ stop]
return self._f(self._data[p][start], self._data[p][stop])
N, *A = map(int, open(0).read().split())
a = list(accumulate(A))
st = DisjointSparseTable(a, add)
result = 0
result += st.query(0, N)
for i in range(1, N):
result += st.query(i, N) - a[i - 1] * (N - i)
print(result)
I was happy to solve it 2 minutes before the end. The same remainder appears within N times and loops. If you detect the loop and find the length of one cycle and the increment in one loop, the query will be * O * (1). ), So I solved it with * O * (* N * + * Q *). I remembered ABC167D --Teleporter.
from sys import stdin
readline = stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
X = 0
b = [-1]
c = [X]
used = set()
while True:
r = X % N
X += A[r]
if r in used:
break
used.add(r)
b.append(r)
c.append(X)
b.append(r)
c.append(X)
loop_start = b.index(b[-1])
loop_len = len(b) - loop_start - 1
Q = int(readline())
for _ in range(Q):
K = int(readline())
if K < len(b):
print(c[K])
else:
K -= loop_start
a = K // loop_len
K %= loop_len
K += loop_start
print(c[K] + a * (c[-1] - c[loop_start]))
Recommended Posts