题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1901
思路：
使用线段树（树状数组比较省空间，也不需要担忧爆栈）套平衡树（具体做法：在每个区间上建立一颗相应的BST），每次修改时修改该点相应区间上的平衡树，每次查询时，先将对应的全部区间找出，在每棵平衡树上二分查找排名为k的数（统计排名使用平衡树即可）。
复杂度：预处理O(n log^2 n) 修改O(log^2 n) 查询O(log^3 n)
代码（树状数组 BZOJ-1901）：
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 10001
struct node {
int key,s;
node *left,*right;
};
node* t[MAXN];
node* R[MAXN];
node *bank=new(node);
int a[MAXN];
int n,m;
int lowbit(int x){
return ((~x)+1)&x;
}
//--------------Size_Balanced_Tree------------------
int left_ratote(node* &t){
node *k=(*t).right;
(*t).right=(*k).left;
(*t).s=(*(*t).left).s+(*(*t).right).s+1;
(*k).left=t;
(*k).s=(*t).s+(*(*k).right).s+1;
t=k;
return 0;
}
int right_ratote(node* &t){
node *k=(*t).left;
(*t).left=(*k).right;
(*t).s=(*(*t).left).s+(*(*t).right).s+1;
(*k).right=t;
(*k).s=(*(*k).left).s+(*t).s+1;
t=k;
return 0;
}
int maintain(node* &t){
if ((*(*(*t).left).left).s>(*(*t).right).s){
right_ratote(t);
maintain((*t).right);
maintain(t);
return 0;
}
if ((*(*(*t).left).right).s>(*(*t).right).s){
left_ratote((*t).left);
right_ratote(t);
maintain((*t).left);
maintain((*t).right);
maintain(t);
return 0;
}
if ((*(*(*t).right).right).s>(*(*t).left).s){
left_ratote(t);
maintain((*t).left);
maintain(t);
return 0;
}
if ((*(*(*t).right).left).s>(*(*t).left).s){
right_ratote((*t).right);
left_ratote(t);
maintain((*t).left);
maintain((*t).right);
return 0;
}
return 0;
}
int INSERT(int key,node* &t){
if (t==bank){
t=new(node);
(*t).left=(*t).right=bank;
(*t).s=1;
(*t).key=key;
return 0;
}
(*t).s++;
if (key<=(*t).key){
INSERT(key,(*t).left);
} else INSERT(key,(*t).right);
maintain(t);
return 0;
}
int DELETE(int key,node* &t){
if (key==(*t).key){
if ((*t).left==bank&&(*t).right==bank){
delete(t);
t=bank;
return 0;
}
if ((*t).left==bank){
node *p=(*t).right;
delete(t);
t=p;
return 0;
}
if ((*t).right==bank){
node *p=(*t).left;
delete(t);
t=p;
return 0;
}
right_ratote(t);
DELETE(key,(*t).right);
(*t).s=(*(*t).left).s+(*(*t).right).s+1;
maintain(t);
return 0;
}
if (key<(*t).key){
DELETE(key,(*t).left);
} else DELETE(key,(*t).right);
(*t).s=(*(*t).left).s+(*(*t).right).s+1;
return 0;
}
int get_rank(int key,node *t){
int rec=0;
node *p=t;
while (p!=bank){
if ((*p).key<key){
rec+=((*(*p).left).s+1);
p=(*p).right;
} else {
p=(*p).left;
}
}
return rec;
}
//----------------Binary_Search--------------------
node *range[MAXN];
int rm;
int GET_RANK(int key){
int rec=0;
for (int i=0;i++<rm;){
rec+=get_rank(key,range[i]);
}
return rec;
}
int get_ans(int l,int r,int k){
rm=0;
int i=r;
while (i>=l){
int s=i-lowbit(i)+1;
if (s>=l){
range[++rm]=t[i];
i=s-1;
} else {
range[++rm]=R[i];
i--;
}
}
int left=-0x7fffffff,right=0x7fffffff;
for (i=0;i++<rm;){
node *p=range[i];
while (p!=bank){
if ((*p).key<left){
p=(*p).right;
continue;
}
if ((*p).key>right){
p=(*p).left;
continue;
}
int s=GET_RANK((*p).key);
if (s==k-1){
return (*p).key;
}
if (s<k-1){
left=(*p).key;
p=(*p).right;
} else {
right=(*p).key;
p=(*p).left;
}
}
}
return left;
}
//----------------------------------------------
int main(){
(*bank).s=0;
(*bank).left=(*bank).right=bank;
scanf("%d%d",&n,&m);
for (int i=0;i++<n;){
scanf("%d",&a[i]);
t[i]=R[i]=bank;
for (int j=i-lowbit(i);j++<i;){
INSERT(a[j],t[i]);
}
INSERT(a[i],R[i]);
}
while (m--){
char c[1];
scanf("%s",&c);
if (c[0]=='Q'){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",get_ans(l,r,k));
} else {
int x,y;
scanf("%d%d",&x,&y);
int i=x;
while (i<=n){
DELETE(a[x],t[i]);
INSERT(y,t[i]);
i+=lowbit(i);
}
(*R[x]).key=y;
a[x]=y;
}
}
return 0;
}
网友评论