当前位置：科技动态 > ZOJ 2112 Dynamic Rankings（树状数组套主席树可修改区间第k小）题解

ZOJ 2112 Dynamic Rankings（树状数组套主席树可修改区间第k小）题解

发布：2023-09-25 11:35

-->

题意：求区间第k小，节点可修改

思路：如果直接用静态第k小去做，显然我更改一个节点后，后面的树都要改，这个复杂度太高。那么我们想到树状数组思路，树状数组是求前缀和，那么我们可以用树状数组套主席树，求出权值线段树前缀和，相减就是区间前缀和。而且我维护也只要改logn棵树就好了。具体看JQ博客。

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5e4 + ;
const int M = maxn * ;
const ull seed = ;
const int INF = 0x3f3f3f3f;
const int MOD = ;
int a[maxn], root[maxn], tot;
int sroot[maxn]; //树状数组的头
int use[maxn]; //保存树状数组的头
int n, m, L, R;
vector vv;
struct node{
int lson, rson;
int sum;
}T[maxn * ];
struct Que{
int order;
int l, r, k;
}q[maxn];
void init(){
memset(T, , sizeof(T));
memset(sroot, , sizeof(root));
tot = ;
vv.clear();
}
int lowbit(int x){
return x&(-x);
}
int getId(int x){
return lower_bound(vv.begin(), vv.end(),x) - vv.begin() + ;
}
void update(int l, int r, int &now, int pre, int v, int pos){
T[++tot] = T[pre], T[tot].sum += v, now = tot;
if(l == r) return;
int m = (l + r) >> ;
if(pos <= m)
update(l, m, T[now].lson, T[pre].lson, v, pos);
else
update(m + , r, T[now].rson, T[pre].rson, v, pos);
}
int add(int x, int v, int pos){
for(int i = x; i <= n; i += lowbit(i)){
update(, vv.size(), sroot[i], sroot[i], v, pos);
}
}
int SUM(int pos){
int ret = ;
for(int i = pos; i > ; i -= lowbit(i))
ret += T[T[use[i]].lson].sum;
return ret;
} int query(int l, int r, int now, int pre, int k){
if(l == r) return l;
int sum = SUM(R) - SUM(L) + T[T[now].lson].sum - T[T[pre].lson].sum;
int m = (l + r) >> ;
if(sum >= k){
for(int i = R; i > ; i -= lowbit(i)) use[i] = T[use[i]].lson;
for(int i = L; i > ; i -= lowbit(i)) use[i] = T[use[i]].lson;
return query(l, m, T[now].lson, T[pre].lson, k);
}
else{
for(int i = R; i > ; i -= lowbit(i)) use[i] = T[use[i]].rson;
for(int i = L; i > ; i -= lowbit(i)) use[i] = T[use[i]].rson;
return query(m + , r, T[now].rson, T[pre].rson, k - sum);
}
} int main(){
int T;
scanf("%d", &T);
while(T--){
init();
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++){
scanf("%d", &a[i]);
vv.push_back(a[i]);
}
for(int i = ; i <= m; i++){
char o[];
scanf("%s", o);
if(o[] == 'Q'){
q[i].order = ;
scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
}
else{
q[i].order = ;
scanf("%d%d", &q[i].l, &q[i].k);
vv.push_back(q[i].k);
}
} sort(vv.begin(), vv.end());
vv.erase(unique(vv.begin(), vv.end()), vv.end()); for(int i = ; i <= n; i++){
update(, vv.size(), root[i], root[i - ], , getId(a[i]));
}
for(int i = ; i <= m; i++){
if(q[i].order == ){
L = q[i].l - , R = q[i].r;
for(int j = R; j > ; j -= lowbit(j)) use[j] = sroot[j];
for(int j = L; j > ; j -= lowbit(j)) use[j] = sroot[j];
printf("%d\n", vv[query(, vv.size(), root[R], root[L], q[i].k) - ]);
}
else{
add(q[i].l, -, getId(a[q[i].l]));
a[q[i].l] = q[i].k;
add(q[i].l, , getId(a[q[i].l]));
}
}
}
return ;
} -->