$chrislaiisme$對區間十分精熟，什麼線段操作$O(N)/O(1)$，$O(NlogN)/O(1)$都輕輕鬆鬆的可以做到，今天他在寫二元樹的時候覺得單點操作太簡單了，他覺得不加點難度沒有什麼意思，他拿著題目去找$william1010121$，但是$william1010121$卻解不出來，為了維護面子，他決定把他出成題目來獲得解答。
這個三元樹有以下性質
1. 節點有兩個值$lval, rval$，然後每個節點最多可以連到三個子節點$l, mid, r$
2. 節點在插入之後位置就不會再改變了
3.接下來的操作要按照順序來判斷
4. 如果插入的$rval$大於當前節點的$rval$則他要往右子節點走
5. 如果插入的$lval$小於當前節點的$lval$則他要往左子節點有
6. 剩下的就走去$mid$
第一行有兩個數字$N$，$M$，代表接下來有$N$筆插入和$M$筆查詢。
接下來有$N$行，每一行有兩數$lval, rval$
接下來有$M$行，每一行有兩樹$lval, rval$
請對$N$行$lval, rval$照上面的規則插入
接下來的$M$行，對於$lval, rval$如果這個區間存在的話輸出他的深度(1-based)，否則輸出-1
4 3 4184 9528 2759 9262 1956 4369 2564 7529 4184 9528 1 1 0 0
1 -1 -1
$前50\% 測資 \quad N\leq100, M\leq1000$
$100\% 測資 \quad N\leq 10^4, M\leq 10^4$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||