結果

問題 No.3122 Median of Medians of Division
コンテスト
ユーザー karashi-0086A2
提出日時 2025-04-20 19:42:09
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,848 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 113,044 KB
最終ジャッジ日時 2025-04-20 19:42:18
合計ジャッジ時間 8,855 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

class SegmentTree:
    def __init__(self, A):
        self.N = len(A)
        self.size = 1
        while self.size < self.N:
            self.size <<= 1
        self.data = [[] for _ in range(2 * self.size)]
        for i in range(self.N):
            self.data[i + self.size] = [A[i]]
        for i in range(self.size - 1, 0, -1):
            self.data[i] = sorted(self.data[2 * i] + self.data[2 * i + 1])

    def update(self, i, x):
        i += self.size
        old = self.data[i][0]
        self.data[i] = [x]
        i >>= 1
        while i:
            # ノードを再構築
            self.data[i] = sorted(self.data[2 * i] + self.data[2 * i + 1])
            i >>= 1

    def count_ge(self, l, r, x):
        l += self.size
        r += self.size + 1
        count = 0
        while l < r:
            if l & 1:
                count += len(self.data[l]) - bisect.bisect_left(self.data[l], x)
                l += 1
            if r & 1:
                r -= 1
                count += len(self.data[r]) - bisect.bisect_left(self.data[r], x)
            l >>= 1
            r >>= 1
        return count

    def query_median(self, l, r):
        total = r - l + 1
        kth = (total + 1) // 2
        low, high = 1, 10**9
        while low < high:
            mid = (low + high + 1) // 2
            if self.count_ge(l, r, mid) >= kth:
                low = mid
            else:
                high = mid - 1
        return low


# 入力処理
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
A = list(map(int, input().split()))

tree = SegmentTree(A)

for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, i, x = query
        tree.update(i - 1, x)
    else:
        _, l, r = query
        ans = tree.query_median(l - 1, r - 1)
        print(ans)
0