結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー roknao
提出日時 2020-09-27 19:16:21
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,273 bytes
コンパイル時間 139 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 89,216 KB
最終ジャッジ日時 2024-06-30 12:52:43
合計ジャッジ時間 3,837 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")


def segfunc(x, y, arr):
    if -1 in [x, y]:
        return max(x, y)

    if arr[x] < arr[y]:
        return x
    else:
        return y


class SegmentTree:
    def __init__(self, arr, ini):
        size = len(arr)
        self.ini = ini
        self.arr = arr
        self.n = 2 ** (size-1).bit_length()
        self.node = [self.ini] * (2*self.n - 1)
        # print(self.n)
        # print(self.node)

        for i in range(size):
            self.node[i+self.n-1] = i
        for i in reversed(range(self.n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2], self.arr)
    

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2*x+1], self.node[2*x+2], self.arr)
    

    def add(self, x, val):
        x += (self.n - 1)
        self.node[x] += val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2*x+1], self.node[2*x+2], self.arr)
    

    def get_point(self, x):
        return self.node[x + self.n - 1]

    
    def query(self, a, b):
        res = self.ini
        l = self.n - 1 + a
        r = self.n - 1 + (b-1)
        
        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l], self.arr)
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l], self.arr)
            if r % 2 == 1:
                res = segfunc(res, self.node[r], self.arr)
            l = l // 2
            r = r // 2 - 1
        
        return res


# 処理内容
def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    seg = SegmentTree(A, -1)
    for _ in range(Q):
        com, l, r = map(int, input().split())
        l -= 1; r -= 1
        if com == 1:
            seg.arr[l], seg.arr[r] = seg.arr[r], seg.arr[l]
            seg.update(l, l)
            seg.update(r, r)
        elif com == 2:
            print(seg.query(l, r+1) + 1)


if __name__ == '__main__':
    main()
0