BOJ 10868最高価格

https://www.acmicpc.net/problem/10868
1秒、256 MBメモリ
input :

N M (1 ≤ N, M ≤ 100,000)

N個の整数

M行は、a、b対

を含む.
output :

M行入力の順に、a,b毎の答え

を出力する.
条件:

a 1番目の整数から2番目の整数まで、最小整数

を探す.
区間内で最大値を探すとO(N)に時間的複雑度があり,当然タイムアウトが発生する.
O(lgn)の時間複雑度であれば,一般的には1秒で十分である.
では、最近勉強したフィンウィックツリーを使用して最大値を探します.この場合、2つのツリーを使用する必要があります.

update

まず,配列入力を受信するとともに,ツリー値の更新を継続する.
そして最後に区間を入力して正解を出力します.

tree_start

この木の場合、1~区間の最大値を各位置に記憶する.
したがってidxも2の加算方式を採用している.

tree_end

このツリーでは、区間から端点までの最大値を各位置に格納します.
したがってidxも2の報酬を減算する方式を用いる.

query

queryという名前自体はちょっと怖いけど何もない質問(条件)を出して返事をもらうだけです.
input : start, end
startからendまでの最高価格を聞いて、車に戻って持って行きます.
その時一番注意すべきことです.
現在のidx値をセグメント外に意図的に格納しているノード値と比較するべきではありません.
したがってcur parentは繰り返し文の条件となる.
cur~cur parent間の最高額貯蔵区間を確認できますか?やるという意味に考えればいい.
そして、このcurに2を加えた報酬方式はtree endから値を取得する.
減算tree startから値を取得します.これに対する理由は,論文の画像を見ると分かりやすいが,endの位置ではidxごとに予想外のセグメントが完璧に除去され,必要なセグメントだけがもたらされるからである.
つまり、このようにすると、最大の2の完全平方数が問題になります.
彼には仕方がないからだ.
[1~2の完全平方数],[2]の完全平方数~end]の値を比較すると,思わぬ演算が生じる.

加算

元の配列データを比較して、そのまま車に戻ればいいです.

import sys


def update(idx, val):
    update_start(idx, val)
    update_end(idx, val)


def update_start(idx, val):
    while idx <= n:
        tree_start[idx] = min(tree_start[idx], val)
        idx += (idx & -idx)


def update_end(idx, val):
    while idx > 0:
        tree_end[idx] = min(tree_end[idx], val)
        idx -= (idx & -idx)


def query(start, end):
    ret = float('inf')

    cur = start
    cur_parent = cur + (cur & -cur)
    while cur_parent <= end:
        ret = min(ret, tree_end[cur])
        cur = cur_parent
        cur_parent += (cur_parent & -cur_parent)

    cur = end
    cur_parent = cur - (cur & -cur)
    while cur_parent >= start:
        ret = min(ret, tree_start[cur])
        cur = cur_parent
        cur_parent -= (cur_parent & -cur_parent)

    ret = min(ret, data[cur])
    return ret


n, m = map(int, sys.stdin.readline().split())
tree_start, tree_end = [float('inf')] * (n + 1), [float('inf')] * (n + 1)
data = [0] * (n + 1)

for i in range(1, n + 1):
    data[i] = int(sys.stdin.readline())
    update_start(i, data[i])
    update_end(i, data[i])

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())

    print(query(a, b))