[BZOJ1901]Zju2112 Dynamic Rankings

Description

給定一個含有n個數的序列a[1],a[2],a[3]……a[n]，程式必須回答這樣的詢問：對于給定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的數是多少(1≤k≤j-i+1)，并且，你可以改變一些a[i]的值，改變後，程式還能針對改

變後的a繼續回答上面的問題。

Input

第一行有兩個正整數n(1≤n≤10000)，m(1≤m≤10000)。

分别表示序列的長度和指令的個數。

第二行有n個數，表示a[1],a[2]……a[n]，這些數都小于10^9。

接下來的m行描述每條指令

每行的格式是下面兩種格式中的一種。

Q i j k 或者 C i t

Q i j k （i,j,k是數字，1≤i≤j≤n, 1≤k≤j-i+1）

表示詢問指令，詢問a[i]，a[i+1]……a[j]中第k小的數。

C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改變成為t

m,n≤10000

Output

對于每一次詢問，你都需要輸出他的答案，每一個輸出占單獨的一行。

Sample Input

5 3

3 2 1 4 7

Q 1 4 3

C 2 6

Q 2 5 3

Sample Output

3

6

思路

一道經典的樹套樹（樹狀數組套主席樹）。

首先，如果不做修改，這是道标準的主席樹模闆題。

因為在這道題中主席樹是用字首和的方式存儲的。是以當我們修改點\(i\)時，我們還需要修改\([i+1,n]\)。這樣就使得複雜度變得無法接受。

于是我們考慮使用套一層樹狀數組的方式來解決。假設在一般的樹狀數組中\(c[i]=\sum _{i=l}^{r} a[i]\)，那麼在樹套樹中\(c[i]\)這個點就是一棵包含\([l,r]\)這個區間的權值線段樹（主席樹）。這樣在修改時，隻需要修改lowbit上的\(\log _2n\)棵線段樹。

在求和時我們隻需要按照樹狀數組的求和方式來求出總和即可。

注意，每個樹狀數組節點上的主席樹都是獨立的。

轉載于:https://www.cnblogs.com/GavinZheng/p/10833025.html