题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3196
思路:典型树套树（最简单写法是线段树套BST），求第K最值用类似BZOJ 1901 Dynamic Ranking的方法二分，求前继将对应所有区间对应平衡树的前继求出，取最大值即可，后继求法类似前继求法。
代码（树状数组+SBT）：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 50001
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;
maintain(t);
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;
}
int get_prefix(int key,node *t){
if (t==bank){
return -0x7fffffff;
}
if (key>(*t).key){
return max(get_prefix(key,(*t).right),(*t).key);
} else return get_prefix(key,(*t).left);
}
int get_suffix(int key,node *t){
if (t==bank){
return 0x7fffffff;
}
if (key<(*t).key)
return min((*t).key,get_suffix(key,(*t).left));
else return get_suffix(key,(*t).right);
}
//------Binary_Search&Binary_Index_Tree---------
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_range(int l,int r){
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--;
}
}
return 0;
}
int get_ans(int l,int r,int k){
get_range(l,r);
int left=-0x7fffffff,right=0x7fffffff;
for (int 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--){
int l,r,k,ans,i;
int c;
scanf("%d",&c);
switch (c){
case 1:
scanf("%d%d%d",&l,&r,&k);
get_range(l,r);
printf("%d\n",GET_RANK(k)+1);
break;
case 2:
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",get_ans(l,r,k));
break;
case 3:
int x,y;
scanf("%d%d",&x,&y);
i=x;
while (i<=n){
DELETE(a[x],t[i]);
INSERT(y,t[i]);
i+=lowbit(i);
}
(*R[x]).key=y;
a[x]=y;
break;
case 4:
ans=-0x7fffffff;
scanf("%d%d%d",&l,&r,&k);
get_range(l,r);
for (i=0;i++<rm;){
ans=max(ans,get_prefix(k,range[i]));
}
printf("%d\n",ans);
break;
case 5:
ans=0x7fffffff;
scanf("%d%d%d",&l,&r,&k);
get_range(l,r);
for (i=0;i++<rm;){
ans=min(ans,get_suffix(k,range[i]));
}
printf("%d\n",ans);
break;
}
}
return 0;
}
网友评论