Zju2112 Dynamic Rankings

• description
• solution
• code

description

給定一個(gè)含有n個(gè)數(shù)的序列a[1],a[2],a[3]……a[n]，程序必須回答這樣的詢(xún)問(wèn)：對(duì)于給定的i,j,k，在a[i],a[i+1

],a[i+2]……a[j]中第k小的數(shù)是多少(1≤k≤j-i+1)，并且，你可以改變一些a[i]的值，改變后，程序還能針對(duì)改

變后的a繼續(xù)回答上面的問(wèn)題。

Input

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

分別表示序列的長(zhǎng)度和指令的個(gè)數(shù)。

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

接下來(lái)的m行描述每條指令

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

Q i j k 或者 C i t

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

表示詢(xún)問(wèn)指令，詢(xún)問(wèn)a[i]，a[i+1]……a[j]中第k小的數(shù)。

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

m,n≤10000

Output

對(duì)于每一次詢(xún)問(wèn)，你都需要輸出他的答案，每一個(gè)輸出占單獨(dú)的一行。

Sample Input

5 3 3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3

Sample Output

3 6

solution

不帶修的區(qū)間第$K$大可持久化線(xiàn)段樹(shù)利用$root[r]?root[l?1]$版本的個(gè)數(shù)向前即可

本質(zhì)是一個(gè)前綴和

考慮現(xiàn)在待修，顯然就是修改后會(huì)對(duì)后面每個(gè)版本都造成影響，時(shí)間花費(fèi)巨大

需要找一個(gè)很好的工具代替，這里我們就選擇了$\mathrm{B}\mathrm{I}\mathrm{T}$樹(shù)狀數(shù)組

每一個(gè)BIT節(jié)點(diǎn)表示一棵主席樹(shù)，可持久化的是權(quán)值線(xiàn)段樹(shù)

相同區(qū)間抽離出來(lái)就相當(dāng)于一個(gè)對(duì)區(qū)間構(gòu)建的樹(shù)狀數(shù)組

就在樹(shù)狀數(shù)組上查$[l,r]$區(qū)間，里面相同區(qū)間的線(xiàn)段樹(shù)相減就是值域?qū)儆?span id="ze8trgl8bvbq" class="katex--inline">$[x,y]$的數(shù)的個(gè)數(shù)

樹(shù)狀數(shù)組是前綴和，主席樹(shù)也是前綴和，所以可以套起來(lái)

樹(shù)狀數(shù)組里套主席樹(shù)

---

具體而言：

將所有出現(xiàn)的值離散化（包括初始和修改）

對(duì)于位置$i$的修改，相當(dāng)于在樹(shù)狀數(shù)組上從$i$跳到$n$，在主席樹(shù)的$a_i$位置先減去，再在$k$位置加一

對(duì)于區(qū)間$[l,r]$的詢(xún)問(wèn)

將$l?1$跳到$1$的所有用到的樹(shù)狀數(shù)組的節(jié)點(diǎn)預(yù)處理到$L[]$數(shù)組

將$r$跳到$1$的所有用到的樹(shù)狀數(shù)組的節(jié)點(diǎn)預(yù)處理到$R[]$數(shù)組

然后在主席樹(shù)上區(qū)間跳，統(tǒng)計(jì)對(duì)于區(qū)間$[x,y]$，$L$中的個(gè)數(shù)，$R$中的個(gè)數(shù)，相減就是$[l,r]$區(qū)間中值域$[x,y]$的個(gè)數(shù)

與此時(shí)的$k$判斷，線(xiàn)段樹(shù)往左走還是往右走

這就相當(dāng)于抽離了一個(gè)區(qū)間的樹(shù)狀數(shù)組出來(lái)

code

#include <cstdio> #include <algorithm> using namespace std; #define maxn 20005 struct query { int op, i, j, k; }q[maxn]; struct node { int tot, lson, rson; }t[maxn * 200]; int n, m, cnt, cnt_l, cnt_r; int a[maxn], val[maxn], root[maxn], mp[maxn], L[maxn], R[maxn];void modify( int &now, int lst, int l, int r, int id, int k ) {t[now = ++ cnt] = t[lst];t[now].tot += k;if( l == r ) return;int mid = ( l + r ) >> 1;if( id <= mid ) modify( t[now].lson, t[now].lson, l, mid, id, k );else modify( t[now].rson, t[now].rson, mid + 1, r, id, k ); }int query( int l, int r, int k ) {if( l == r ) return l;int tot_l = 0, tot_r = 0;for( int i = 1;i <= cnt_l;i ++ ) tot_l += t[t[L[i]].lson].tot;for( int i = 1;i <= cnt_r;i ++ ) tot_r += t[t[R[i]].lson].tot;int mid = ( l + r ) >> 1;if( tot_r - tot_l >= k ) {for( int i = 1;i <= cnt_l;i ++ ) L[i] = t[L[i]].lson;for( int i = 1;i <= cnt_r;i ++ ) R[i] = t[R[i]].lson;return query( l, mid, k );}else {for( int i = 1;i <= cnt_l;i ++ ) L[i] = t[L[i]].rson;for( int i = 1;i <= cnt_r;i ++ ) R[i] = t[R[i]].rson;return query( mid + 1, r, k - ( tot_r - tot_l ) );} }int lowbit( int x ) { return x & ( -x ); }int main() {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ ) scanf( "%d", &a[i] ), val[i] = a[i];for( int i = 1;i <= m;i ++ ) {char opt[5];scanf( "%s", opt );if( opt[0] == 'Q' ) q[i].op = 0, scanf( "%d %d %d", &q[i].i, &q[i].j, &q[i].k );else q[i].op = 1, scanf( "%d %d", &q[i].i, &q[i].k ), val[++ n] = q[i].k;}sort( val + 1, val + n + 1 );n = unique( val + 1, val + n + 1 ) - val - 1;for( int i = 1;i <= n;i ++ ) {a[i] = lower_bound( val + 1, val + n + 1, a[i] ) - val;for( int j = i;j <= n;j += lowbit( j ) ) modify( root[j], root[j], 1, n, a[i], 1 );}for( int i = 1;i <= m;i ++ )if( ! q[i].op ) continue;else q[i].k = lower_bound( val + 1, val + n + 1, q[i].k ) - val;for( int i = 1;i <= n;i ++ ) mp[i] = val[i];for( int i = 1;i <= m;i ++ ) {if( q[i].op ) {for( int j = q[i].i;j <= n;j += lowbit( j ) )modify( root[j], root[j], 1, n, a[q[i].i], -1 );a[q[i].i] = q[i].k;for( int j = q[i].i;j <= n;j += lowbit( j ) )modify( root[j], root[j], 1, n, a[q[i].i], 1 );}else {cnt_l = cnt_r = 0; q[i].i --;for( int j = q[i].i;j;j -= lowbit( j ) ) L[++ cnt_l] = root[j];for( int j = q[i].j;j;j -= lowbit( j ) ) R[++ cnt_r] = root[j];printf( "%d\n", mp[query( 1, n, q[i].k )] );}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Zju2112 Dynamic Rankings（树状数组套可持久化权值线段树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。