分析
平衡二叉树
set/map 红黑树(代码长) == splay(代码适中,支持很多操作)
treap(有局限,一些操作做不了)
AVL
多叉树
B树 B+树
操作:
左旋
右旋 (维护的是中序遍历不变)
右旋
->
z z
/ //
y x
/ \ / \\
x c A y
/ \ // \
A B B C
AxByc AxByc
左旋
->
=线代表变得关系
-代表不变的关系
可以发现由于要维护中序遍历,最左和最右的关系是不变的
插入
查询
? 每操作一个节点 均将该节点旋转到树根
splay(x,k) 将点x旋转至点k下
1
z y x
/ / \ \
y x z y
/ \
x z
先转y 转x
每转一次x往上走两格 直到某个点下面为止
2 z z x
/ / / \
y x y z
\ /
x y
先转x 转x
插入
1 找到x插入位置
把x转到根
2 将一个序列插到y的后面
---------------
y z
2.1 找y的后继z
2.2 将y转到根 splay(y,0)
2.3 将z转到y的下面 spaly(z,y)
y
\
z
/
null(因为z和y之间没有数,所以z左子树为空)
2.4 将序列插入到z的左子树
删除
-----------------
L-1 L R R+1
1 将L-1转到根节点
2 将R+1转到L-1下面
此时R+1的左子树=[L,R]
3 将R+1的左儿子置为空Null
代码
/*made in mrd*/
#include
using namespace std;
const int N=2e5+10;
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define fi first
#define se second
#define pii pair
#define pb push_back
int n,m;
struct node{
int s[2],fa,v;
int size,flag;
void init(int _v,int _fa)
{
v=_v,fa=_fa;
size=1;
}
}tr[N];
int root,dex;
void pushup(int x)
{
tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
}
void pushdown(int x)
{
// 如果当前子树需要翻转 48.34
if (tr[x].flag)
{
//要翻转整颗子树，要先把左右两个儿子翻转，然后递归翻转左右两棵子树
swap(tr[x].s[0], tr[x].s[1]);
tr[tr[x].s[0]].flag ^= 1;//翻转标记往下传
tr[tr[x].s[1]].flag ^= 1;//翻转标记往下传
tr[x].flag = 0;//当前标记清空
}
}
void rotate(int x)
{
int y=tr[x].fa, z=tr[y].fa;
int k=tr[y].s[1]==x;
tr[z].s[tr[z].s[1]==y]=x,tr[x].fa=z;
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].fa=y;
tr[x].s[k^1]=y;
tr[y].fa=x;
pushup(y),pushup(x);
}
void splay(int x, int k)
{
while (tr[x].fa != k)
{
int y = tr[x].fa, z = tr[y].fa;
if (z != k)
// 如果是折线关系 == x是y的右/左儿子 且 y是z的左/右儿子 一0一1
if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);//折线rotate两次x
else rotate(y);//直线rotate 一次y一次x
rotate(x);
}
if (!k) root = x;//如果k==0 根节点更新为x
}
void insert(int v)
{
int u=root,p=0;
while (u) p=u,u=tr[u].s[v>tr[u].v];
u=++dex;
if(p)
{
tr[p].s[v>tr[p].v]=u;
}
tr[u].init(v,p);
splay(u,0);
}
int get_k(int k)
{
int u=root;
while(1)
{
pushdown(u);
if(tr[tr[u].s[0]].size>=k) u=tr[u].s[0];
else if(tr[tr[u].s[0]].size+1==k) return u;
else k-=tr[tr[u].s[0]].size+1,u=tr[u].s[1];
}
return -1;
}
void output(int u)
{
pushdown(u);
// 如果u有左儿子 先递归输出左儿子
if (tr[u].s[0]) output(tr[u].s[0]);
// 如果u不是哨兵输出当前点
if (tr[u].v >= 1 && tr[u].v <= n) printf("%d ", tr[u].v);
// 如果u有右儿子 递归输出右儿子
if (tr[u].s[1]) output(tr[u].s[1]);
}
signed main() {
cin>>n>>m;
for (int i = 0; i <= n + 1; i ++ ) insert(i);//插入哨兵 0,n+1 防止L-1和R+1越界
while (m -- )
{
int l, r;
cin>>l>>r;
//因为哨兵要翻转的从[L,R]变为[L+1,R+1] 则要找L和R+2作为L+1的前继和R+1的后继
l = get_k(l), r = get_k(r + 2);
// 左端点l转到根,右端点r转到左端点下面
splay(l, 0), splay(r, l);
// 只要将r的左子树[L+1,R+1]翻转
tr[tr[r].s[0]].flag ^= 1;
}
output(root);
return 0;
return 0;
}