Bzoj3196 Tyvj 1730 二逼平衡樹

樹 樹套樹

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 3350  Solved: 1324

您需要寫一種資料結構（可參考題目标題），來維護一個有序數列，其中需要提供以下操作：

1.查詢k在區間内的排名

2.查詢區間内排名為k的值

3.修改某一位值上的數值

4.查詢k在區間内的前驅(前驅定義為小于x，且最大的數)

5.查詢k在區間内的後繼(後繼定義為大于x，且最小的數)

第一行兩個數 n,m 表示長度為n的有序序列和m個操作

第二行有n個數，表示有序序列

下面有m行，opt表示操作标号

若opt=1 則為操作1，之後有三個數l,r,k 表示查詢k在區間[l,r]的排名

若opt=2 則為操作2，之後有三個數l,r,k 表示查詢區間[l,r]内排名為k的數

若opt=3 則為操作3，之後有兩個數pos,k 表示将pos位置的數修改為k

若opt=4 則為操作4，之後有三個數l,r,k 表示查詢區間[l,r]内k的前驅

若opt=5 則為操作5，之後有三個數l,r,k 表示查詢區間[l,r]内k的後繼

對于操作1,2,4,5各輸出一行，表示查詢結果

9 6

4 2 2 1 9 4 0 1 1

2 1 4 3

3 4 10

1 2 5 9

4 3 9 5

5 2 8 5

2

4

3

9

1.n和m的資料範圍：n,m<=50000

2.序列中每個數的資料範圍：[0,1e8]

3.雖然原題沒有，但事實上5操作的k可能為負數

樹套樹

線段樹套平衡樹(treap)

外層線段樹維護區間，内層treap維護該區間内的數值

代碼超長看着就累

Bzoj過了，Tyvj上最後兩個點過不去，迷

标題仿佛在嘲笑那些光寫平衡樹的人，又仿佛在嘲諷我這種模闆題調一下午的人……

小發現：對拍的時候，要是每次錯得不一樣，基本上可以确定是旋轉錯了/結點删錯了

本文為部落客原創文章，轉載請注明出處。