P3369 【模板】普通平衡树
纯板子。。。。题意：
[*]插入 xx 数
[*]删除 xx 数(若有多个相同的数，因只删除一个)
[*]查询 xx 数的排名(排名定义为比当前数小的数的个数 +1+1 。若有多个相同的数，因输出最小的排名)
[*]查询排名为 xx 的数
[*]求 xx 的前驱(前驱定义为小于 xx ，且最大的数)
[*]求 xx 的后继(后继定义为大于 xx ，且最小的数)
然后。。。
然后就没有然后了。。。。
注意rotate。。。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cctype>
using namespace std;
#define olinr return
#define love_nmr 0
#define INF 0x7ffffffa
#define mod 123123
int n;
int cnt;
int root;
int siz;
int dat;
int fat;
int num;
int son;
inline int read()
{
int f=1,x=0;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
f=-f;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
olinr x*f;
}
inline void put(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
put(x/10);
putchar(x%10+'0');
}
/* ------------------------olinr love nmr--------------------------------*/
inline void update(int x)
{
siz=siz]+siz]+num;
}
inline void rotate(int x,int &o)
{
int y=fat;
int z=fat;
bool xx=son==x;
bool yy=xx^1;
if(y==o)
o=x;
else
son==y]=x;
fat=z;
fat=x;
fat]=y;
son=son;
son=y;
update(y);
update(x);
olinr;
}
inline void splay(int x,int &o)
{
while(x!=o)
{
int y=fat;
int z=fat;
if(y!=o)
{
if((son==x)^(son==y))
rotate(x,o);
else
rotate(y,o);
}
rotate(x,o);
}
}
inline int x_rank_n(int x)
{
int now=root;
int rank=0;
while(5201314+love_nmr)
{
if(x<dat)
now=son;
else
{
rank+=siz];
if(x==dat)
{
splay(now,root);
olinr rank+1;
}
rank+=num;
now=son;
}
}
}
inline int n_rank_x(int x)
{
int now=root;
while(5201314+love_nmr)
{
if(siz]>=x)
now=son;
else
{
if(num+siz]>=x)
olinr dat;
x-=(num+siz]);
now=son;
}
}
}
inline int pre(int x)
{
x_rank_n(x);
int now=son;
while(son)
now=son;
olinr now;
}
inline int nxt(int x)
{
x_rank_n(x);
int now=son;
while(son)
now=son;
olinr now;
}
inline int del(int x)
{
int l=pre(x);
int r=nxt(x);
splay(l,root);
splay(r,son);
int now=son];
siz--;
num--;
if(!num)
{
son]=0;
fat=0;
}
splay(son,root);
}
inline void insert(int x)
{
if(!root)
{
root=++cnt;
siz=1;
dat=x;
num=1;
olinr;
}
int fa=0;
int now=root;
while(5201314+love_nmr)
{
if(dat==x)
{
num++;
siz++;
splay(now,root);
olinr;
}
fa=now;
now=son];
if(!now)
{
now=++cnt;
fat=fa;
son]=now;
num++;
siz++;
dat=x;
splay(now,root);
olinr;
}
}
}
int main()
{
n=read();
int flag,x;
insert(INF);
insert(-INF);
for(int i=1;i<=n;i++)
{
flag=read();
x=read();
if(flag==1) insert(x);
if(flag==2) del(x);
if(flag==3){put(x_rank_n(x)-1);putchar('\n');}
if(flag==4){put(n_rank_x(x+1));putchar('\n');}
if(flag==5){insert(x);put(dat);putchar('\n');del(x);}
if(flag==6){insert(x);put(dat);putchar('\n');del(x);}
}
olinr love_nmr;
}注释QAQ
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cctype>
using namespace std;
#define R register
#define IL inline
#define INF 2147483640
#define mod 125125
#define II int
II root; //根的编号
II n; //n个操作
II cnt; //编号
II fa; //fa代表i的父亲
II son; //son代表i的左儿子，son代表i的右儿子
II data; //data代表树上编号为i的点的值
II size; //size表示以i为根的子树的sum的和 (大小) (包括自己)
II sum; //sum表示数字i的个数
IL II read() //快读(有负数)
{
R II x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
f=-f;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
IL void update(R II x)//更新x
{
size=size]+size]+sum;
//当前点的size == 左儿子的size + 右儿子的size + 当前点的个数
}
IL void rotate(R II x,R II &o) //旋转
{
R II y=fa; //y为x的父亲
R II z=fa; //z为y的父亲，z为x的爷爷
R bool xx=(son==x); //xx表示y的右儿子是否为x
R bool yy=xx^1; //yy表示y的左儿子是否为x
if(y==o) //x的父亲y是旋转的目标点
o=x; //目标点变为x
else //x的父亲y不是旋转的目标点
son==y]=x; //如果z的右儿子是y，那么现在z的右儿子是x；如果z的右儿子不是y，那么现在z的左儿子是x
fa=z; //x的父亲是z
fa=x; //y的父亲是x(x转了上去)
fa]=y; //如果原来y的左儿子是x，那么现在x的右儿子是y；如果原来y的右儿子是x，那么现在x的左儿子是y
son=son; //原来x的(右||左)儿子变成了先在y的(左||右)儿子
son=y; //如果原来y的(左||右)儿子是x，那么现在x的(右||左)儿子是y
update(y); //维护y
update(x); //维护x
}
IL void splay(R II x,R II &o)
{
while(x!=o) //只要为转到目标节点
{
R II y=fa; //y是x的父亲
R II z=fa; //z是y的父亲，x的爷爷
if(y!=o) //如果y不是目标节点
{
if((son==x)^(son==y)) //如果xyz不在一条直链上
rotate(x,o); //x朝o的方向转
else //在一条直链上
rotate(y,o); //转y
}
rotate(x,o); //转x
}
}
IL void insert(R II x)
{
if(!root) //是根
{ //初始化
root=++cnt;
data=x;
size=1;
sum=1;
return;
}
R II now=root; //从根开始找合适位置
R II fat=0; //now的father
while(5201314)
{
if(data==x) //树中已有该元素
{
sum++; //累计数量
splay(now,root); //转
return;
}
fat=now;
now=son<x]; //now往孩子上跳
if(!now) //跳到了叶子的孩子(还没有)
{
now=++cnt; //初始化
fa=fat;
son<x]=now;
size++;
sum++;
data=x;
splay(now,root);
return;
}
}
}
IL II x_rank_n(R II x) //找树中的数x的排名
{
R II rank=0;
R II now=root; //从根往下找
while(5201314)
{
if(x<data) //小于当前点往左跳
now=son;
else
{
rank+=size];//排名加上左子树大小(x一定比左子树所有值都大，不然就会往左跳)
if(x==data) //找到了x
{
splay(now,root); //转上去
return rank+1; //x的位置
}
rank+=sum; //往右跳说明它比前面所有数都大，所以要累计前面数的个数
now=son; //累计完后在往后跳
}
}
}
IL II rank_n_x(R II x)
{
R II rank=0;
R II now=root;
while(5201314)
{
if(size]>=x) //目标在左子树
now=son; //往左跳
else
{
if(sum+size]>=x) //now就是x的位置
return data;
x-=(sum+size]); //x减左边个数
now=son; //再向右跳
}
}
}
IL II pre(R II x)
{
x_rank_n(x);
R II now=son;
while(son)
now=son;
return now;
}
IL II nxt(R II x)
{
x_rank_n(x);
R II now=son;
while(son)
now=son;
return now;
}
IL void del(R II x)
{
R II l=pre(x);
R II r=nxt(x);
splay(l,root);
splay(r,son);
R II now=son];
sum--;
size--;
if(!sum)
{
son]=0;
fa=0;
}
splay(son,root);
}
int main()
{
ios::sync_with_stdio(false);
n=read();
insert(-INF);
insert(INF);
for(R II i=1;i<=n;i++)
{
R II x=read();
R II y=read();
if(x==1) insert(y);
if(x==2) del(y);
if(x==3) printf("%d\n",x_rank_n(y)-1);
if(x==4) printf("%d\n",rank_n_x(y+1));
if(x==5) insert(y),printf("%d\n",data),del(y);
if(x==6) insert(y),printf("%d\n",data),del(y);
}
return 0;
}
----olinr
文档来源：51CTO技术博客https://blog.51cto.com/u_15314204/3190974
页:
[1]