機器搬遷 ISCOJ 現已搬到全新主機上，立即體驗全新的評測速度！
4660 . 雙重覆蓋問題
Description
給你一個長度為$N$的數線，以及容器$S$，請支援$Q$次以下三種操作：
1. 設這是第$x$次（1-based!）進行第1種操作，給定正整數$l, r$，在$S$中插入編號為$x$的區間$[l, r]$。
2. 給定正整數$x$，刪除$S$中編號為$x$的區間。
3. 給定正整數$x$，設$m$為$S$中覆蓋$x$的區間數量
* 如果$m=2$，輸出兩個整數$a, b$，$a, b$須滿足$a<b$，$S$中有編號為$a$的區間和編號為$b$的區間，且兩區間皆覆蓋$x$。
* 如果$m\neq2$，輸出一個整數$-1$
定義區間$[l, r]$覆蓋$k$若且唯若$l\le k\le r$
Input Format
請注意這題的所有輸入、輸出格式皆為1-based
第一行有兩個整數$N, Q$
接下來有$Q$行，第$i+1$行為一次操作$\text{query}_i$
$\text{query}_i$可能有兩個或三個數字，設最前面的是$t$，代表你要進行第$t$種操作
若$t=1$，接下來有兩個數字，分別為$l,\ r$
若$t=2$ 或 $t=3$，接下來有一個數字，為$x$
具體來說長這樣：
N Q
query_1
query_2
...
query_Q
而$\text{query}_i$的格式是以下三種之一：
1 l r
2 x
3 x
$1\le N, Q\le5\times10^ {5}$
$1\le t \le 3$
對於第1種操作，$1\le l \le r \le N$
對於第2種操作，滿足$S$中一定有剛好一個編號為$x$的區間
對於第3種操作，$1\le x \le N$
Output Format
設第3種操作總共進行$q$次，請輸出$q$行
第$i$行包含第$i$次進行第3種操作的結果，可能有以下兩種形式：
a b
-1
Sample Input 1
2 6 1 1 2 1 1 1 3 1 3 2 2 1 3 1
Sample Output 1
1 2 -1 -1
Sample Input 2
8 10 1 2 5 1 3 7 1 4 6 3 3 3 4 3 5 3 6 3 7 2 2 3 4
Sample Output 2
1 2 -1 -1 2 3 -1 1 3
Sample Input 3
10 12 1 8 10 3 9 1 4 7 1 1 8 2 2 3 1 1 7 10 3 7 1 1 10 3 7 2 4 2 5
Sample Output 3
-1 -1 3 4 -1
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 34~39 | 所有第3種操作都發生在第1, 2種操作之後 | 30 |
| 2 | 1~18 | $N, Q\le 8\times 10^ {4}$ | 60 |
| 3 | 1~39 | 無特別限制 | 10 |