题解 P3380 【【模板】二逼平衡树（树套树）】

提供指针线段树套指针Splay 查第k小二分时的初始l和r用线段树处理出区间最小最大值有效提高时效 ```cpp #include<cstdio> #include<cctype> #include<climits> #include<algorithm> using std::max; using std::min; template<class type>inline void read(type &in) { in=0;short fh=1;char ch=getchar(); while (!isdigit(ch))fh=ch=='-'?-1:fh,ch=getchar(); while (isdigit(ch))in=(in<<3)+(in<<1)+ch-48,ch=getchar(); in*=fh; } const int N=50001; int n,m,a[N]; namespace Splay { struct tree { int value,size,cnt; tree *son[2],*fa; inline tree(int key) { value=key; fa=son[0]=son[1]=NULL; cnt=size=1; } inline void pushup() { size=cnt; if (son[0])size+=son[0]->size; if (son[1])size+=son[1]->size; } }; inline bool connection(tree *p) //获取父子关系 (p是它父亲的x儿子 { if (p&&p->fa)return p->fa->son[1]==p; } inline void connect(tree *&p,tree *&fa,bool which) //建立父子关系 (p是fa的which儿子，p的父亲是fa { if (p)p->fa=fa; if (fa)fa->son[which]=p; } inline void rotate(tree *&p) //把p旋转上 { tree *fa=p->fa; bool lr=connection(p); connect(p,fa->fa,connection(fa)); connect(p->son[lr^1],fa,lr); connect(fa,p,lr^1); fa->pushup();p->pushup(); } inline void splay(tree *&p,tree *goal,tree *&root) //在根为root的Splay中把p旋作goal的儿子 (goal==NULL时旋至根 { for (tree *fa;(fa=p->fa)!=goal;rotate(p)) if (fa->fa!=goal) rotate(connection(p)==connection(fa)?fa:p); if (goal==NULL)root=p; } inline void insert(int insertion,tree *&root) //把insertion插入到根为root的Splay中 { if (root==NULL) { root=new tree(insertion); return; } tree *now=root; while (1) { if (insertion==now->value) { now->cnt++; now->pushup(); if (now->fa)now->fa->pushup(); splay(now,NULL,root); return; } tree *fa=now; bool direction=now->value<insertion; now=fa->son[direction]; if (now==NULL) { now=new tree(insertion); connect(now,fa,direction); fa->pushup(); splay(now,NULL,root); return; } } } inline void find(int key,tree *&root) //在根为root的Splay中查找值为key的点并splay至根 { if (root==NULL)return; tree *now=root; while (now->son[now->value<key]&&now->value!=key) now=now->son[now->value<key]; splay(now,NULL,root); } inline tree *precursor(int x,tree *&root) //前驱 { find(x,root); if (root->value<x)return root; tree *now=root->son[0]; while (now->son[1])now=now->son[1]; return now; } inline tree *successor(int x,tree *&root) //后继 { find(x,root); if (root->value>x)return root; tree *now=root->son[1]; while (now->son[0])now=now->son[0]; return now; } inline void Delete(int x,tree *&root) //删除 { tree *pre=precursor(x,root),*nxt=successor(x,root); splay(pre,NULL,root);splay(nxt,pre,root); tree *pop=nxt->son[0]; if (pop->cnt>1) pop->cnt--,pop->pushup(),splay(pop,NULL,root); else nxt->son[0]=NULL,delete pop; } inline int get_rank(int x,tree *&root) //在根为root的Splay中查询有多少个比x小的数 { tree *now=root;int ranking=-1; //原本ranking赋的是1，由于插入了-INF，所以要变成0，由于是比x小的数的个数，也就是x的排名减1，所以赋的是-1 while (now) if (x<now->value)now=now->son[0]; else { ranking+=now->son[0]?now->son[0]->size:0; if (now->value==x)return ranking; ranking+=now->cnt; now=now->son[1]; } return ranking; } } namespace Segment_Tree { struct tree { int l,r,maxval,minval; //存区间最大最小值 tree *lson,*rson; Splay::tree *root; inline tree(int l_,int r_) { l=l_;r=r_; root=NULL; lson=rson=NULL; maxval=minval=0; } inline void pushup() //更新 { maxval=max(lson->maxval,rson->maxval); minval=min(lson->minval,rson->minval); } }*root; inline void build(int l,int r,tree *&p) //建树 { p=new tree(l,r); Splay::insert(INT_MAX,p->root); //插入±INF使得删除操作中所有数都能找到前驱后继 Splay::insert(INT_MIN,p->root); for (int i=l;i<=r;i++) Splay::insert(a[i],p->root); if (l==r){p->maxval=p->minval=p->root->value;return;} int mid=l+r>>1; build(l,mid,p->lson); build(mid+1,r,p->rson); p->pushup(); } inline void update(int pos,int key,tree *&p) //修改操作 { Splay::Delete(a[pos],p->root); Splay::insert(key,p->root); //先删去原来的数，再把新的数插入 if (p->l==p->r){a[pos]=p->maxval=p->minval=key;return;} //同时改变最大最小值 int mid=p->l+p->r>>1; if (pos<=mid)update(pos,key,p->lson); else update(pos,key,p->rson); p->pushup(); } int query_max(int l,int r,tree *p) //查询区间最大值 { if (p->l>r||p->r<l)return INT_MIN; if (p->l>=l&&p->r<=r)return p->maxval; return max(query_max(l,r,p->lson),query_max(l,r,p->rson)); } int query_min(int l,int r,tree *p) //查询区间最小值 { if (p->l>r||p->r<l)return INT_MAX; if (p->l>=l&&p->r<=r)return p->minval; return min(query_min(l,r,p->lson),query_min(l,r,p->rson)); } inline int get_rank(int l,int r,int x,tree *p) //查询区间内有多少个比x小的数 (x的排名-1 { if (p->l>r||p->r<l)return 0; if (p->l>=l&&p->r<=r)return Splay::get_rank(x,p->root); return get_rank(l,r,x,p->lson)+get_rank(l,r,x,p->rson); } inline int find_rank(int l_,int r_,int ranking) //查询区间第k小 { int l=query_min(l_,r_,root),r=query_max(l_,r_,root)+1; //利用线段树区间最大最小值给l/r赋初值 while (l<r) { int mid=l+r>>1; if (get_rank(l_,r_,mid,root)<ranking)l=mid+1; else r=mid; } return l-1; } inline int precursor(int l,int r,int x,tree *p) //区间前驱 { if (p->l>r||p->r<l)return -INT_MAX; if (p->l>=l&&p->r<=r)return Splay::precursor(x,p->root)->value; return max(precursor(l,r,x,p->lson),precursor(l,r,x,p->rson)); } inline int successor(int l,int r,int x,tree *p) //区间后继 { if (p->l>r||p->r<l)return INT_MAX; if (p->l>=l&&p->r<=r)return Splay::successor(x,p->root)->value; return min(successor(l,r,x,p->lson),successor(l,r,x,p->rson)); } }using namespace Segment_Tree; int main() { read(n);read(m); for (int i=1;i<=n;i++)read(a[i]); build(1,n,root); while (m--) { int opt,k; read(opt); if (opt==3) { int pos; read(pos);read(k); update(pos,k,root); continue; } int l,r;read(l);read(r);read(k); switch(opt) { case 1: printf("%d\n",get_rank(l,r,k,root)+1);break; //记得加上1 case 2: printf("%d\n",find_rank(l,r,k));break; case 4: printf("%d\n",precursor(l,r,k,root));break; case 5: printf("%d\n",successor(l,r,k,root));break; } } return 0; } ```