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/library-checker/data-structure/staticrmq.test.py

Depends on

Code

# verification-helper: PROBLEM https://judge.yosupo.jp/problem/staticrmq

def main():
    N, Q = rd(), rd()
    A = rdl(N)
    st = MinSparseTable(A)
    for _ in range(Q):
        wtn(st.query(rd(),rd()))

from cp_library.ds.min_sparse_table_cls import MinSparseTable
from cp_library.io.fast.fast_io_fn import rd, rdl, wtn

if __name__ == '__main__':
    main()
# verification-helper: PROBLEM https://judge.yosupo.jp/problem/staticrmq

def main():
    N, Q = rd(), rd()
    A = rdl(N)
    st = MinSparseTable(A)
    for _ in range(Q):
        wtn(st.query(rd(),rd()))

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
# from typing import Generic
# from cp_library.misc.typing import _T


def min2(a, b):
    return a if a < b else b



class MinSparseTable:
    def __init__(st, arr: list):
        st.N = N = len(arr)
        st.log = N.bit_length()
        st.data = data = [0] * (st.log*N)
        data[:N] = arr 
        for i in range(1,st.log):
            a, b, c = i*N, (i-1)*N, (i-1)*N + (1 << (i-1))
            for j in range(N - (1 << i) + 1):
                data[a+j] = min2(data[b+j], data[c+j])

    def query(st, l: int, r: int):
        k = (r-l).bit_length() - 1
        return min2(st.data[k*st.N + l], st.data[k*st.N + r - (1<<k)])
    
from __pypy__.builders import StringBuilder
import sys
from os import read as os_read, write as os_write
from atexit import register as atexist_register

class Fastio:
    ibuf = bytes()
    pil = pir = 0
    sb = StringBuilder()
    def load(self):
        self.ibuf = self.ibuf[self.pil:]
        self.ibuf += os_read(0, 131072)
        self.pil = 0; self.pir = len(self.ibuf)
    def flush_atexit(self): os_write(1, self.sb.build().encode())
    def flush(self):
        os_write(1, self.sb.build().encode())
        self.sb = StringBuilder()
    def fastin(self):
        if self.pir - self.pil < 64: self.load()
        minus = x = 0
        while self.ibuf[self.pil] < 45: self.pil += 1
        if self.ibuf[self.pil] == 45: minus = 1; self.pil += 1
        while self.ibuf[self.pil] >= 48:
            x = x * 10 + (self.ibuf[self.pil] & 15)
            self.pil += 1
        if minus: return -x
        return x
    def fastin_string(self):
        if self.pir - self.pil < 64: self.load()
        while self.ibuf[self.pil] <= 32: self.pil += 1
        res = bytearray()
        while self.ibuf[self.pil] > 32:
            if self.pir - self.pil < 64: self.load()
            res.append(self.ibuf[self.pil])
            self.pil += 1
        return res
    def fastout(self, x): self.sb.append(str(x))
    def fastoutln(self, x): self.sb.append(str(x)); self.sb.append('\n')
fastio = Fastio()
rd = fastio.fastin; rds = fastio.fastin_string; wt = fastio.fastout; wtn = fastio.fastoutln; flush = fastio.flush
atexist_register(fastio.flush_atexit)
sys.stdin = None; sys.stdout = None
def rdl(n): return [rd() for _ in range(n)]
def wtnl(l): wtn(' '.join(map(str, l)))

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