网站建设公司电话,网站建设和维护待遇,房地产网站建设,鞍山网民Zju2112 Dynamic Rankingsdescriptionsolutioncodedescription
给定一个含有n个数的序列a[1],a[2],a[3]……a[n]#xff0c;程序必须回答这样的询问#xff1a;对于给定的i,j,k#xff0c;在a[i],a[i1
],a[i2]……a[j]中第k小的数是多少(1≤k≤j-i1)#xff0c;并且…
Zju2112 Dynamic Rankingsdescriptionsolutioncodedescription
给定一个含有n个数的序列a[1],a[2],a[3]……a[n]程序必须回答这样的询问对于给定的i,j,k在a[i],a[i1
],a[i2]……a[j]中第k小的数是多少(1≤k≤j-i1)并且你可以改变一些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-i1
表示询问指令询问a[i]a[i1]……a[j]中第k小的数。
C i t (1≤i≤n0≤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
6solution
不带修的区间第KKK大可持久化线段树利用root[r]−root[l−1]root[r]-root[l-1]root[r]−root[l−1]版本的个数向前即可
本质是一个前缀和
考虑现在待修显然就是修改后会对后面每个版本都造成影响时间花费巨大
需要找一个很好的工具代替这里我们就选择了BIT\rm BITBIT树状数组
每一个BIT节点表示一棵主席树可持久化的是权值线段树
相同区间抽离出来就相当于一个对区间构建的树状数组
就在树状数组上查[l,r][l,r][l,r]区间里面相同区间的线段树相减就是值域属于[x,y][x,y][x,y]的数的个数
树状数组是前缀和主席树也是前缀和所以可以套起来
树状数组里套主席树 具体而言
将所有出现的值离散化包括初始和修改
对于位置iii的修改相当于在树状数组上从iii跳到nnn在主席树的aia_iai位置先减去再在kkk位置加一
对于区间[l,r][l,r][l,r]的询问
将l−1l-1l−1跳到111的所有用到的树状数组的节点预处理到L[]L[]L[]数组
将rrr跳到111的所有用到的树状数组的节点预处理到R[]R[]R[]数组
然后在主席树上区间跳统计对于区间[x,y][x,y][x,y]LLL中的个数RRR中的个数相减就是[l,r][l,r][l,r]区间中值域[x,y][x,y][x,y]的个数
与此时的kkk判断线段树往左走还是往右走
这就相当于抽离了一个区间的树状数组出来
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;
}
