cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: test/aoj/dsl/dsl_2_a_segtree.test.py

Depends on

Code

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A

def main():
    N, Q = read()
    seg = SegTree(min, 2147483647, N)
    for _ in range(Q):
        com, x, y = read()
        if com: write(seg.prod(x,y+1))
        else: seg[x] = y

from cp_library.ds.tree.segtree_cls import SegTree
from cp_library.io.read_int_fn import read
from cp_library.io.write_fn import write

if __name__ == '__main__':
    main()
# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A

def main():
    N, Q = read()
    seg = SegTree(min, 2147483647, N)
    for _ in range(Q):
        com, x, y = read()
        if com: write(seg.prod(x,y+1))
        else: seg[x] = y

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from typing import Callable, Generic, Union
from typing import TypeVar
_T = TypeVar('T')



class SegTree(Generic[_T]):
    def __init__(seg, op: Callable[[_T, _T], _T], e: _T, v: Union[int, list[_T]]) -> None:
        if isinstance(v, int): v = [e] * v
        seg.op, seg.e, seg.n = op, e, (n := len(v))
        seg.log, seg.sz, seg.d = (log := (n-1).bit_length()+1), (sz := 1 << log), [e] * (sz << 1)
        for i in range(n): seg.d[sz + i] = v[i]
        for i in range(sz-1,0,-1): seg.d[i] = op(seg.d[i<<1], seg.d[i<<1|1])

    def set(seg, p: int, x: _T) -> None:
        seg.d[p := p + seg.sz], op = x, seg.op
        for _ in range(seg.log): seg.d[p:=p>>1] = op(seg.d[p:=p^(p&1)], seg.d[p|1])
    __setitem__ = set

    def get(seg, p: int) -> _T:
        return seg.d[p + seg.sz]
    __getitem__ = get

    def prod(seg, l: int, r: int) -> _T:
        sml = smr = seg.e
        l, r = l+seg.sz, r+seg.sz
        while l < r:
            if l&1: sml, l = seg.op(sml, seg.d[l]), l+1
            if r&1: smr = seg.op(seg.d[r:=r-1], smr)
            l, r = l >> 1, r >> 1
        return seg.op(sml, smr)

    def all_prod(seg) -> _T:
        return seg.d[1]

    def max_right(seg, l: int, f: Callable[[_T], bool]) -> int:
        assert 0 <= l <= seg.n
        assert f(seg.e)
        if l == seg.n: return seg.n
        l, op, d, sm = l+(sz := seg.sz), seg.op, seg.d, seg.e
        while True:
            while l&1 == 0: l >>= 1
            if not f(op(sm, d[l])):
                while l < sz:
                    if f(op(sm, d[l:=l<<1])): sm, l = op(sm, d[l]), l+1
                return l - sz
            sm, l = op(sm, d[l]), l+1
            if l&-l == l: return seg.n

    def min_left(seg, r: int, f: Callable[[_T], bool]) -> int:
        assert 0 <= r <= seg.n
        assert f(seg.e)
        if r == 0: return 0
        r, op, d, sm = r+(sz := seg.sz), seg.op, seg.d, seg.e
        while True:
            r -= 1
            while r > 1 and r & 1: r >>= 1
            if not f(op(d[r], sm)):
                while r < sz:
                    if f(op(d[r:=r<<1|1], sm)): sm, r = op(d[r], sm), r-1
                return r + 1 - sz
            sm = op(d[r], sm)
            if (r & -r) == r: return 0


def read(shift=0, base=10):
    return [int(s, base) + shift for s in input().split()]
import os
import sys
from io import BytesIO, IOBase


class FastIO(IOBase):
    BUFSIZE = 8192
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        BUFSIZE = self.BUFSIZE
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        BUFSIZE = self.BUFSIZE
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    stdin: 'IOWrapper' = None
    stdout: 'IOWrapper' = None
    
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable

    def write(self, s):
        return self.buffer.write(s.encode("ascii"))
    
    def read(self):
        return self.buffer.read().decode("ascii")
    
    def readline(self):
        return self.buffer.readline().decode("ascii")

sys.stdin = IOWrapper.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper.stdout = IOWrapper(sys.stdout)

def write(*args, **kwargs):
    '''Prints the values to a stream, or to stdout_fast by default.'''
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", IOWrapper.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()

if __name__ == '__main__':
    main()
Back to top page