結果

問題 No.875 Range Mindex Query
ユーザー nephrologist
提出日時 2020-03-14 07:01:47
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,632 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 50,480 KB
最終ジャッジ日時 2024-11-23 18:15:26
合計ジャッジ時間 26,829 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 10 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, q = map(int, readline().split())
A = list(map(int, readline().split()))
m = map(int, read().split())
Q = list(zip(m, m, m))
infi = 10 ** 10

num = 2 ** ((n - 1).bit_length())
SEG = [(infi, -1)] * (2 * num - 1)


def init(A):
    for i in range(n):
        SEG[num - 1 + i] = (A[i], i)
    for i in range(num - 2, -1, -1):
        x = SEG[2 * i + 1][0]
        y = SEG[2 * i + 2][0]
        if x > y:
            SEG[i] = SEG[2 * i + 2]
        else:
            SEG[i] = SEG[2 + i + 1]


def change(p, q):
    p += num - 1
    q += num - 1
    a, b = SEG[p]
    c, d = SEG[q]
    SEG[p] = (c, b)
    SEG[q] = (a, d)
    for i in range(num - 2, -1, -1):
        x = SEG[2 * i + 1][0]
        y = SEG[2 * i + 2][0]
        if x > y:
            SEG[i] = SEG[2 * i + 2]
        else:
            SEG[i] = SEG[2 + i + 1]


def ami(pair1, pair2):
    x = pair1[0]
    y = pair2[0]
    if x > y:
        return pair2
    else:
        return pair1


def query(p, q):
    if p > q:
        return False
    p += num - 1
    q += num - 1
    ans = (infi, -1)
    while q - p > 1:
        if p & 1 == 0:
            ans = ami(SEG[p], ans)
        if q & 1 == 1:
            ans = ami(SEG[q], ans)
            q -= 1
        p //= 2
        q -= 1
        q //= 2
    if p == q:
        ans = ami(ans, SEG[p])
    else:
        ans = ami(ans, SEG[q])
        ans = ami(ans, SEG[p])
    return ans


init(A)
for a, l, r in Q:
    if a == 1:
        change(l - 1, r - 1)
    else:
        print(query(l - 1, r - 1)[1] + 1)
0