h936: 磚牆改
Tags : 時間線段樹 線段樹
Accepted rate : 1人/2人 ( 50% ) [非即時]
評分方式:
Tolerant

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

Content

有一個城牆,城門被打破了,然後被修好了,然後就跑走了。

簡單來說,這是一個由 $n$ 塊磚頭組成的城牆,每塊磚頭初始的高度皆為 $0$,每次可以對區間 $[l, r]$ 進行補牆操作,也就是讓區間 $[l, r]$ 高度未滿 $h$ 的磚頭高度都變成 $h$,但是補牆的工人有時記憶會被竄改,他會發現他其實並沒有做第 $id$ 個操作,於是第 $id$ 筆操作會被取消。

這個國家的女王西斯特莉亞會問你一些問題,比如說區間 $[l, r]$ 的磚頭裡,最高的高度是多少,或是最矮的高度是多少。

如果你回答錯了,女王會揍你一拳;如果你回答最矮的東西並不是磚牆,那就請你保護好你的後頸。

Input

第一行有兩個正整數 $n, q$,代表有 $n$ 塊磚頭和 $q$ 筆詢問。

接下來 $q$ 行,每行第一個數字為 $ty$。

若 $ty = 1$,後面會接著輸入 $l, r, h$,代表要將區間 $[l, r]$ 高度未滿 $h$ 的磚頭高度變成 $h$。

若 $ty = 2$,後面會接著輸入 $id$,代表要將第 $id$ 筆操作取消,保證第 $id$ 筆操作的 $ty$ 只會是 $1$,且 $id$ 一定小於當前的操作。

若 $ty = 3$,後面會接著輸入 $l, r$,代表要詢問區間 $[l, r]$ 磚頭的最高高度。
若 $ty = 4$,後面會接著輸入 $l, r$,代表要詢問區間 $[l, r]$ 磚頭的最矮高度。

  • $1 \leq n, q \leq 10^5$
  • $1 \leq ty \leq 4$
  • $1 \leq l \leq r \leq n$
  • $0 \leq h \leq 10^9$
Output

對於每筆 $ty = 3$ 或是 $ty = 4$ 的詢問,輸出一個整數代表答案。

Sample Input #1
10 11
1 1 5 17
4 2 3
1 1 3 65
1 7 10 51
4 4 9
2 4
3 1 9
3 7 9
3 5 5
2 3
3 1 2
Sample Output #1
17
0
65
0
17
17
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 3.0s , <1M
公開 測資點#1 (45%): 3.0s , <10M
公開 測資點#2 (45%): 3.0s , <10M
Hint :

以下為範例的操作過程:

$1 : \{17, 17, 17, 17, 17, 0, 0, 0, 0, 0\}$
$2 : \{17, 17, 17, 17, 17, 0, 0, 0, 0, 0\}$
$3 : \{65, 65, 65, 17, 17, 0, 0, 0, 0, 0\}$
$4 : \{65, 65, 65, 17, 17, 0, 51, 51, 51, 51\}$
$5 : \{65, 65, 65, 17, 17, 0, 51, 51, 51, 51\}$
$6 : \{65, 65, 65, 17, 17, 0, 0, 0, 0, 0\}$
$7 : \{65, 65, 65, 17, 17, 0, 0, 0, 0, 0\}$
$8 : \{65, 65, 65, 17, 17, 0, 0, 0, 0, 0\}$
$9 : \{65, 65, 65, 17, 17, 0, 0, 0, 0, 0\}$
$10 : \{17, 17, 17, 17, 17, 0, 0, 0, 0, 0\}$
$11 : \{17, 17, 17, 17, 17, 0, 0, 0, 0, 0\}$

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

$10\%:n, q \leq 1000$

$90\%:無特別限制$

Tags:
時間線段樹 線段樹
出處:
第六屆簡單的小競賽 [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
30890 becaido(Caido) h936
題解
34 2022-06-19 19:28