結果

問題 No.2223 Merged Med
コンテスト
ユーザー stoq
提出日時 2023-02-16 07:23:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,596 bytes
コンパイル時間 349 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 238,308 KB
最終ジャッジ日時 2024-07-19 11:57:49
合計ジャッジ時間 29,179 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 TLE * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

# https://qiita.com/tomato1997/items/27581f530cdf77c79ad2


class Node:
    def __init__(self, default):
        self.rch = None
        self.lch = None
        self.val = default


class PersistentSegTree:
    def __init__(self, ls, func, default, default_ver=0):
        '''
        ls (list) : 永続配列にしたい配列
        func: 関数を指定
        default: 単位元を指定
        default_ver (any): 最初のversion(デフォルト:0)
        '''
        N = len(ls)
        self.default = default
        self.func = func
        self.N = N
        self.K = (N - 1).bit_length()
        self.N2 = 1 << self.K
        self.dat = [Node(self.default) for _ in range(2**(self.K + 1))]
        for i in range(self.N):  # 葉の構築
            self.dat[self.N2 + i].val = ls[i]
        self.build()
        self.verdict = dict()
        self.verdict[default_ver] = 1  # 各versionの根のindexを格納

    def build(self):
        for node in range(self.N2 - 1, 0, -1):
            self.dat[node].rch = self.dat[node << 1 | 1]
            self.dat[node].lch = self.dat[node << 1]
            self.dat[node].val = self.func(self.dat[node << 1 | 1].val,
                                           self.dat[node << 1].val)
            self.dat.pop()
            self.dat.pop()

    def update_told_tnew_x_val(self, told, tnew, x, val):
        '''
        version:toldのindex:xをvalに変更したものをtnewとする(O(logN))
        told: 変更前のversion
        tnew: 変更後のversion
        x: 変更するindex
        val: 変更後の値
        '''
        if not (told in self.verdict):
            raise ('No such version exists')
        x += self.N2
        path = bin(x)[3:]
        self.verdict[tnew] = len(self.dat)
        new_nodes = [Node(self.default) for _ in range(len(path) + 1)]
        v_old = self.dat[self.verdict[told]]
        v_new = new_nodes[0]
        now = 1
        for i in path:  # ノードをつなげる
            if i == '0':
                v_new.rch = v_old.rch
                v_new.lch = new_nodes[now]
                v_new = new_nodes[now]
                v_old = v_old.lch
            else:
                v_new.lch = v_old.lch
                v_new.rch = new_nodes[now]
                v_new = new_nodes[now]
                v_old = v_old.rch
            now += 1
        v_new.val = val
        for node in range(len(path) - 1, -1, -1):  # 付け加えたノードの値を子から親に更新
            new_nodes[node].val = self.func(new_nodes[node].lch.val,
                                            new_nodes[node].rch.val)
        self.dat.append(new_nodes[0])

    def query_t(self, t, L, R):
        '''
        version:tにおける区間クエリ[L,R)(O(logN))
        return : int
        '''
        L += self.N2
        R += self.N2
        L0 = L
        R0 = R
        ls = set()  # 見るべきノード番号
        while L < R:
            if L & 1:
                ls.add(L)
                L += 1
            if R & 1:
                R -= 1
                ls.add(R)
            L >>= 1
            R >>= 1
        valdef = self.default
        d = [(1, 0, self.dat[self.verdict[t]])]
        while d:  # 二分木上をdfs
            num, depth, node = d.pop()
            if num in ls:
                valdef = self.func(node.val, valdef)
                continue
            if depth == self.K:
                continue
            if num >= (L0 >> (self.K - depth)):
                d.append((num << 1, depth + 1, node.lch))
            if R0 > ((num << 1 | 1) << (self.K - depth - 1)):
                d.append((num << 1 | 1, depth + 1, node.rch))
        return valdef


# (lmax, rmax, max, sum)
def op(s, t):
    return (max(s[0], s[3] + t[0]), max(t[1], s[1] + t[3]),
            max(s[2], t[2], s[1] + t[0]), s[3] + t[3])


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(n):
        a[i] -= 1
    p = [(a[i], i) for i in range(n)]
    p.sort()

    init = [(1, 1, 1, 1) for _ in range(n)]
    seg = PersistentSegTree(init, op, (0, 0, 0, 0))
    for i in range(n):
        seg.update_told_tnew_x_val(i, i + 1, p[i][1], (-1, -1, -1, -1))

    for _ in range(q):
        l, r = map(int, input().split())
        l -= 1
        lo = -1
        hi = n + 1
        while hi - lo > 1:
            mi = (lo + hi) >> 1
            s = seg.query_t(mi, l, r)
            if s[3] < 0 or s[3] - s[2] + 1 < 0:
                hi = mi
            else:
                lo = mi
        print(p[hi - 1][0] + 1)


main()
0