回『基礎題庫』
h936. 磚牆改
標籤 : 時間線段樹 線段樹
通過比率 : 2人/5人 ( 40% ) [非即時]
評分方式：
Tolerant

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

內容

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

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

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

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

輸入說明

第一行有兩個正整數 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≤n,q≤105
  • 1≤ty≤4
  • 1≤l≤r≤n
  • 0≤h≤109
輸出說明

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

範例輸入 #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
範例輸出 #1 
17
0
65
0
17
17
測資資訊：
記憶體限制： 512 MB
公開 測資點#0 (10%): 3.0s , <1M
公開 測資點#1 (45%): 3.0s , <10M
公開 測資點#2 (45%): 3.0s , <10M
提示 ：

以下為範例的操作過程：

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≤1000

90%：無特別限制

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
30890 becaido (Caido) h936
424 2022-06-19 19:28