描述
http://www.lydsy.com/JudgeOnline/problem.php?id=3196
可以处理区间问题的平衡树.
3196: Tyvj 1730 二逼平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2412 Solved: 986
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)
Input
第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继
Output
对于操作1,2,4,5各输出一行，表示查询结果
Sample Input
9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
Sample Output
2
4
3
4
9
4
3
4
9
HINT
1.n和m的数据范围：n,m<=50000
2.序列中每个数的数据范围：[0,1e8]
3.虽然原题没有，但事实上5操作的k可能为负数
Source
分析
树套树.可以用线段树套Treap.人生第一道树套树的题...
op1:如果在整区间,直接在该区间的treap上求解.否则分两个区间求解,然后相加.最后+1.
op2:这个不太好直接做,可以二分,每次假定一个值,用这个值去做op1,以此求得一个rank=k+1的数,求rank=k的数等价与求这个数的前驱pre.
op3:先删后加.
op4&op5:如果在整区间,直接在该区间的treap上求解,否则分量个区间求解,pre取最大值,suc取最小值.注意有些数在有些区间可能找不到前驱/后驱,这时pre返回-INF,suc取INF.
p.s.
1.神一样的调了一下午....上午做完普通平衡树感觉自己好不熟练啊居然搞了一上午,中午敲完这个题以为能A,结果RE,之后就没救了...发现时remove函数的问题,也没找到问题在哪,在开始怀疑人生之前换回了白书上的写法,果然A了,再看看原来的写法也没什么错啊.于是重新写了一遍原来的方法,结果A了.然后开始找不同,后来发现是结构体里定义的小于号不知咋地不好使了...C++学得太渣,最后只好舍弃,改为手动判断大小了...也不知道问题出在哪,最后还是没有解决,好遗憾...
1.白书上的remove写法
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std; const int maxn=+,oo=~0u>>;
int n,q;
int a[maxn];
struct Treap{
struct node{
node* ch[];
int v,r,s,c;
node(int v,node* t):v(v){ ch[]=ch[]=t; r=rand(); s=c=; }
bool operator < (const node &rhs) const{ return r<rhs.r; }
void push_up() { s=ch[]->s+ch[]->s+c; }
}*root,*null;
Treap(){
null=new node(,NULL);
null->c=null->s=; null->r=oo;
root=null;
}
void rotate(node* &o,bool d){
node* k=o->ch[!d]; o->ch[!d]=k->ch[d]; k->ch[d]=o;
o->push_up(); k->push_up(); o=k;
}
void insert(node* &o,int x){
if(o==null) o=new node(x,null);
else{
if(x==o->v){ o->s++; o->c++; }
else{
bool d=x>o->v;
insert(o->ch[d],x);
if(o->ch[d]<o) rotate(o,!d);
o->push_up();
}
}
}
void remove(node* &o,int x){
if(o->v==x){
if(o->c>) { o->c--; o->s--; }
else{
if(o->ch[]!=null&&o->ch[]!=null){
bool d=o->ch[]<o->ch[];
rotate(o,d); remove(o->ch[d],x); o->push_up();
}
else{
node* u=o;
if(o->ch[]==null) o=o->ch[]; else o=o->ch[];
delete u;
}
}
}
else{
bool d=x>o->v;
remove(o->ch[d],x);
o->push_up();
}
}
int rank(int x){
int ret=,s;
for(node *t=root;t!=null;){
s=t->ch[]->s+t->c;
if(x>t->v) ret+=s,t=t->ch[];
else t=t->ch[];
}
return ret;
}
int pre(int x){
int ret=-oo;
for(node* t=root;t!=null;){
if(t->v<x) ret=t->v,t=t->ch[];
else t=t->ch[];
}
return ret;
}
int suc(int x){
int ret=oo;
for(node* t=root;t!=null;){
if(t->v>x) ret=t->v,t=t->ch[];
else t=t->ch[];
}
return ret;
}
}; struct Segment_Tree{
Treap tree[maxn*];
void build_tree(int l,int r,int k){
for(int i=l;i<=r;i++) tree[k].insert(tree[k].root,a[i]);
if(l==r) return;
int mid=l+((r-l)>>);
build_tree(l,mid,k<<); build_tree(mid+,r,k<<|);
}
int get_rank(int l,int r,int k,int x,int y,int X){
if(l==x&&r==y) return tree[k].rank(X);
int mid=l+((r-l)>>);
if(y<=mid) return get_rank(l,mid,k<<,x,y,X);
else if(x>mid) return get_rank(mid+,r,k<<|,x,y,X);
else return get_rank(l,mid,k<<,x,mid,X)+get_rank(mid+,r,k<<|,mid+,y,X);
}
void change(int l,int r,int k,int id,int x){
tree[k].remove(tree[k].root,a[id]);
tree[k].insert(tree[k].root,x);
if(l==r) return;
int mid=l+((r-l)>>);
if(id<=mid) change(l,mid,k<<,id,x);
else change(mid+,r,k<<|,id,x);
}
int get_pre(int l,int r,int k,int x,int y,int X){
if(l==x&&r==y) return tree[k].pre(X);
int mid=l+((r-l)>>);
if(y<=mid) return get_pre(l,mid,k<<,x,y,X);
else if(x>mid) return get_pre(mid+,r,k<<|,x,y,X);
else return max(get_pre(l,mid,k<<,x,mid,X),get_pre(mid+,r,k<<|,mid+,y,X));
}
int get_suc(int l,int r,int k,int x,int y,int X){
if(l==x&&r==y) return tree[k].suc(X);
int mid=l+((r-l)>>);
if(y<=mid) return get_suc(l,mid,k<<,x,y,X);
else if(x>mid) return get_suc(mid+,r,k<<|,x,y,X);
else return min(get_suc(l,mid,k<<,x,mid,X),get_suc(mid+,r,k<<|,mid+,y,X));
}
int get_kth(int x,int y,int k){
int l=,r=oo;
while(l<r){
int mid=l+((r-l)>>);
int tmp=get_rank(,n,,x,y,mid)+;
if(tmp<=k) l=mid+;
else r=mid;
}
return get_pre(,n,,x,y,l);
}
}T; int main()
{
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
T.build_tree(,n,);
int qry,l,r,k,x,pos;
for(int i=;i<=q;i++){
scanf("%d",&qry);
switch(qry){
case :
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",T.get_rank(,n,,l,r,x)+);break;
case :
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",T.get_kth(l,r,k));break;
case :
scanf("%d%d",&pos,&x);
T.change(,n,,pos,x);
a[pos]=x;break;
case :
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",T.get_pre(,n,,l,r,x));break;
case :
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",T.get_suc(,n,,l,r,x));break;
}
}
return ;
}
2.另一种remove写法
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std; const int maxn=+,oo=~0u>>;
int n,q;
int a[maxn];
struct Treap{
struct node{
node* ch[];
int v,r,s,c;
node(int v,node* t):v(v){ ch[]=ch[]=t; r=rand(); s=c=; }
void push_up() { s=ch[]->s+ch[]->s+c; }
}*root,*null;
Treap(){
null=new node(,NULL);
null->c=null->s=; null->r=oo;
root=null;
}
void rotate(node* &o,bool d){
node* k=o->ch[!d]; o->ch[!d]=k->ch[d]; k->ch[d]=o;
o->push_up(); k->push_up();
if(o==root) root=k;
o=k;
}
void insert(node* &o,int x){
if(o==null) o=new node(x,null);
else{
if(x==o->v) o->s++, o->c++;
else{
bool d=x>o->v;
insert(o->ch[d],x);
if(o->ch[d]<o) rotate(o,!d);
o->push_up();
}
}
}
void remove(node* &o,int x) {
if(x==o->v) {
if(o->c>) o->c--,o->s--;
else{
bool d=o->ch[]->r<o->ch[]->r;
if(o->ch[d]==null){
delete o;
o=null;
}
else{
rotate(o,!d);
remove(o->ch[!d],x);
o->push_up();
}
}
}
else{
bool d=x>o->v;
remove(o->ch[d],x);
o->push_up();
}
}
int rank(int x){
int ret=,s;
for(node *t=root;t!=null;){
s=t->ch[]->s+t->c;
if(x>t->v) ret+=s,t=t->ch[];
else t=t->ch[];
}
return ret;
}
int pre(int x){
int ret=-oo;
for(node* t=root;t!=null;){
if(t->v<x) ret=t->v,t=t->ch[];
else t=t->ch[];
}
return ret;
}
int suc(int x){
int ret=oo;
for(node* t=root;t!=null;){
if(t->v>x) ret=t->v,t=t->ch[];
else t=t->ch[];
}
return ret;
}
}; struct Segment_Tree{
Treap tree[maxn<<];
void build_tree(int l,int r,int k){
for(int i=l;i<=r;i++) tree[k].insert(tree[k].root,a[i]);
if(l==r) return;
int mid=l+((r-l)>>);
build_tree(l,mid,k<<); build_tree(mid+,r,k<<|);
}
int get_rank(int l,int r,int k,int x,int y,int X){
if(l==x&&r==y) return tree[k].rank(X);
int mid=l+((r-l)>>);
if(y<=mid) return get_rank(l,mid,k<<,x,y,X);
else if(x>mid) return get_rank(mid+,r,k<<|,x,y,X);
else return get_rank(l,mid,k<<,x,mid,X)+get_rank(mid+,r,k<<|,mid+,y,X);
}
void change(int l,int r,int k,int id,int x){
tree[k].remove(tree[k].root,a[id]);
tree[k].insert(tree[k].root,x);
if(l==r) return;
int mid=l+((r-l)>>);
if(id<=mid) change(l,mid,k<<,id,x);
else change(mid+,r,k<<|,id,x);
}
int get_pre(int l,int r,int k,int x,int y,int X){
if(l==x&&r==y) return tree[k].pre(X);
int mid=l+((r-l)>>);
if(y<=mid) return get_pre(l,mid,k<<,x,y,X);
else if(x>mid) return get_pre(mid+,r,k<<|,x,y,X);
else return max(get_pre(l,mid,k<<,x,mid,X),get_pre(mid+,r,k<<|,mid+,y,X));
}
int get_suc(int l,int r,int k,int x,int y,int X){
if(l==x&&r==y) return tree[k].suc(X);
int mid=l+((r-l)>>);
if(y<=mid) return get_suc(l,mid,k<<,x,y,X);
else if(x>mid) return get_suc(mid+,r,k<<|,x,y,X);
else return min(get_suc(l,mid,k<<,x,mid,X),get_suc(mid+,r,k<<|,mid+,y,X));
}
int get_kth(int x,int y,int k){
int l=,r=oo;
while(l<r){
int mid=l+((r-l)>>);
int tmp=get_rank(,n,,x,y,mid)+;
if(tmp<=k) l=mid+;
else r=mid;
}
return get_pre(,n,,x,y,l);
}
}T; int main()
{
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
T.build_tree(,n,);
int qry,l,r,k,x,pos;
for(int i=;i<=q;i++){
scanf("%d",&qry);
switch(qry){
case :
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",T.get_rank(,n,,l,r,x)+);break;
case :
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",T.get_kth(l,r,k));break;
case :
scanf("%d%d",&pos,&x);
T.change(,n,,pos,x);
a[pos]=x;break;
case :
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",T.get_pre(,n,,l,r,x));break;
case :
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",T.get_suc(,n,,l,r,x));break;
}
}
return ;
}