h925: 青蛙
Tags : Treap 樹堆
Accepted rate : 6人/6人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-19 19:03

Content

蛙蛙王國有很多青蛙

不只會呱呱,還會呱呱呱

平時喜歡唱歌、呱呱

各個都是游泳的小健將

出太陽時會吃西呱

呱風下雨時會大搬家

青蛙們今天要搬去哪裡呢?

還沒搬呢,還沒搬呢

要搬到最左邊的地方,還是最右邊的地方?

呱呱呱

要進行選美比賽了

每隻青蛙都蓄勢待發

最美麗的青蛙

可以獲得蛙光體

成為最耀眼的青蛙

呱呱呱

吃西呱呱呱

呱呱呱呱呱

Input

第一行有兩個正整數 $n, q$,代表有幾隻青蛙和詢問的次數。

接下來有 $n$ 個數字 $a_1\sim a_n$,代表由左到右每隻青蛙的美麗值。

接下來 $q$ 行,每行有三個整數 $ty, l, r$。如果 $ty = 1$,代表要將由左開始數第 $l$ 隻的青蛙到第 $r$ 隻的青蛙移到最左邊;如果 $ty = 2$,代表要將由左開始數第 $l$ 隻的青蛙到第 $r$ 隻的青蛙移到最右邊;如果 $ty = 3$,代表由左開始數第 $l$ 隻的青蛙到第 $r$ 隻的青蛙要進行選美比賽,請輸出它們之中最大的美麗值。

  • $1 \leq n, q \leq 10^5$
  • $1\leq a_i \leq 10^9$
  • $1 \leq ty \leq 3$
  • $1 \leq l \leq r \leq n$
Output

對於每筆 $ty = 3$ 的詢問,回答最大的美麗值。

Sample Input #1
5 5
4 8 7 6 3
1 2 3
2 2 4
3 1 3
2 4 5
3 2 4
Sample Output #1
8
7
測資資訊:
記憶體限制: 100 MB
公開 測資點#0 (7%): 2.0s , <10M
公開 測資點#1 (46%): 2.0s , <10M
公開 測資點#2 (47%): 2.0s , <10M
Hint :

在範例中,原本的序列是 $4, 8, 7, 6, 3$。

進行第一筆操作後,序列從 $4, \color{blue}{8, 7}, \color{black}{6, 3}$ 變成 $\color{blue}{8, 7}, \color{black}{4, 6, 3}$。

進行第二筆操作後,序列從 $8, \color{blue}{7, 4, 6}, \color{black}{3}$ 變成 $8, 3, \color{blue}{7, 4, 6}$。

第三筆操作詢問區間 $[1, 3]$ 的最大值,$8, 3, 7$ 中最大的數字為 $8$。

進行第四筆操作後,序列從 $8, 3, 7, \color{blue}{4, 6}$ 變成 $8, 3, 7, \color{blue}{4, 6}$。

第五筆操作詢問區間 $[2, 4]$ 的最大值,$3, 7, 4$ 中最大的數字為 $7$。

---------------------------------------------------------------------------------------------

$7\%:ty ≠ 1, 2$

$93\%:無特別限制$

Tags:
Treap 樹堆
出處:
第六屆簡單的小競賽 [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」