老二哲學

發布時間: July 14, 2024, 7:50 a.m.   最後更新時間: July 16, 2024, 11:45 a.m.   時間限制: 2500ms   記憶體限制: 128M

"老二哲學"(Second-best Philosophy)是一種處世態度或人生哲學,強調在各方面不一定要爭取第一,而是接受成為第二名或次優的地位。

周總理能夠在亂世中爬上高位,卻也屢屢度過危機,有一部分就是靠著這個原因。

1971年的初夏,毛主席與周總理還有隨從們去到一個著名景點石排遊玩,石排顧名思義就是有一大排的石頭(其實你點進連結就知道了),那裡的石頭非常特別,有時候會有一顆忽然長大,有時候又會忽然縮小,一行人看到這景象頓時目瞪口呆的。

「哇喔 ! 」 「沃 !!! 」「太神奇了吧 ! 」 「真不愧咱們是偉大的主席 ! 」

「嘿嘿......周總理,我們去逛逛這神奇的地方吧。」毛主席說。

「Let's go~ 讓我們見識見識這裡還有什麼厲害的東西 ! 」周總理附和。

「呼...呼...。歐買尬~這天氣真會熱鼠人呀 ! 」毛主席氣喘吁吁地說。

「對啊對啊 ! 呼~~~ 我們休息一會兒吧 ! 大家肯定都累了。」周總理說。「既然都來到了石排,我們不妨就在這附近挑一塊石頭坐下來歇歇。」

「好啊好啊...」 「好主意 ! 」

周總理接著說「那這附近最大的那顆石頭就讓偉大的主席坐吧 ! 」

毛主席回應道「好啊 ! 那你們剩下的人就歲便坐坐唄 ! 」

周總理這時想到,要是不趕快找到這附近第二大顆的石頭,他這老二的位置豈不是拱手讓人了嗎?而且啊 ! 沿路走走停停的每次都要找好很久才找到的第二大的,有沒有什麼可以快速找到第二大的方法呢?

你要是可以想出一個快速算出區間嚴格次大值($\lt$最大值)的方法,周總理肯定會給你一輩子的排組鴨吃。

第一行給你兩個整數$n,q$代表有$n$顆石頭和$q$筆操作
第二行給你$n$個整數$s_0,s_1, ...,s_{n-1}$(我喜歡0-base的)分別代表$n$顆石頭的大小
接下來有$q$行,每行有兩種可能:
$1$ $k$ $x$,代表第$k$顆石頭變成$x$的大小
$2$ $l$ $r$,代表周總理詢問在$[l,r]$的嚴格次大值

$(1\le n,q\le 10^5)$
$(1\le s_i\le 10^9, i\in \{ 0, 1, ..., n-1\})$
$(0\le k\lt n, 1\le x\le 10^9)$
$(0\le l\le r\lt n)$

對於周總理每個詢問輸出一行答案,若無則輸出"to get a timeout!"(不含引號)

複製範例
10 8
5 2 4 4 2 7 3 4 5 4
2 5 9
1 5 5
2 5 9
1 8 4
2 7 9
2 6 9
2 1 4
2 0 7
5
4
to get a timeout!
3
2
4

之前打了一小時的題敘全部消失(╯‵□′)╯︵┻━┻,所以重打一次品質可能會降低很多

segment tree

hush