首页 > 代码库 > 【整合】SBT模板(全部操作)

【整合】SBT模板(全部操作)

插入,删除,前驱后继,第k大值,排名,最大值最小值8种询问外带核心左旋右旋Maintain

全套模板整合

从16:10开始写,写到了16:28

总计用时18min左右(前后误差不超过1min)

我的手速还真是快呢owo

这一次就是个小测试了。看来到现在SBT已经写熟练了0-0

可以去颓Splay和fhqTreap之类的了www

P.S.应该没写错吧。。。有什么写错了的有人看出来了马上告诉我QUQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct sbt
{
	int left,right,size,data;
}tree[100000];
int top,root;
int n;
int opt;
int key;
void left_rot(int &x)
{
	int y=tree[x].right;
	tree[x].right=tree[y].left;
	tree[y].left=x;
	tree[y].size=tree[x].size;
	tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
	x=y;
}
void right_rot(int &x)
{
	int y=tree[x].left;
	tree[x].left=tree[y].right;
	tree[y].right=x;
	tree[y].size=tree[x].size;
	tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
	x=y;
}
void Maintain(int &x,bool flag)
{
	if (!flag)
	{
		if (tree[tree[tree[x].left].left].size>tree[tree[x].right].size)
		    right_rot(x);
		else
		if (tree[tree[tree[x].left].right].size>tree[tree[x].right].size)
		    left_rot(tree[x].left),right_rot(x);
		else
		return;
	}
	else
	{
		if (tree[tree[tree[x].right].right].size>tree[tree[x].left].size)
		    left_rot(x);
		else
		if (tree[tree[tree[x].right].left].size>tree[tree[x].left].size)
		    right_rot(tree[x].right),left_rot(x);
		else
		return;
	}
	Maintain(tree[x].left,0);
	Maintain(tree[x].right,1);
	Maintain(x,1);
	Maintain(x,0);
}
void insert(int &x,int data)
{
	if (x==0)
	{
		x=++top;
		tree[x].size=1;
		tree[x].left=tree[x].right=0;
		tree[x].data=http://www.mamicode.com/data;>

【整合】SBT模板(全部操作)