問題一覧 > 通常問題

No.776 A Simple RMQ Problem

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : りあん / テスター : rickytheta
6 ProblemId : 2588 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-10-26 07:25:08

謝罪

Python 等の言語で通る保証はないです。

問題文

要素数 N の数列 A={a1,a2,...,aN}  が与えられます。

以下の 2 種類のクエリが合計 Q 個与えられるので、それらを順番に処理してください。

  • set i x
    • ai の値を x に変更する

  • max l1 l2 r1 r2
    • range_max(l1,l2,r1,r2) =max(l1  l  l2)  (r1  r  r2)  (l  r)k=lrak  の値を出力する

入力

N Q
a1 a2  aN
query1
query2

queryQ

1 行目に数列の長さを表す整数 N とクエリの数を表す整数 Q がこの順で半角スペース区切りで与えられます。

2 行目には N 個の整数が半角スペース区切りで与えられ、その内の i 番目 (1iN) の整数は、初期の ai の値を表します。

続く Q 行のうちの i 行目 (1iQ) には、i 番目のクエリが与えられます。

各クエリは

  • set i x
  • max l1 l2 r1 r2

のいずれかの形式で与えられます。


入力は全部で Q+2 行となり、以下の制約を満たします。

  • 入力は全て整数
  • 1N,Q105
  • 109ai109  (1iN)
  • set クエリ
    • 1iN
    • 109x109
  • max クエリ
    • 1l1,l2,r1,r2N
    • (l1l2)  (r1r2)  (l1r2)
      • (l1ll2)  (r1rr2)  (lr)  を満たすような (l,r) が 1 つ以上存在する)
  • max クエリ は 1 つ以上存在する

出力

各 max クエリに対して、range_max(l1,l2,r1,r2)  の値を改行区切りで出力してください。

サンプル

サンプル1
入力
5 6
1 2 -3 -4 5
max 1 2 4 5
max 1 3 2 5
max 3 4 1 5
max 1 5 3 4
set 1 -10
max 1 5 1 1
出力
1
3
1
0
-10

サンプル2
入力
3 5
1000000000 1000000000 1000000000
max 1 3 1 3
set 1 -1000000000
set 2 -1000000000
set 3 -1000000000
max 1 1 3 3
出力
3000000000
-3000000000

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。