| 记录编号 |
358321 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[SDOI 2007] 超级数组 |
最终得分 |
100 |
| 用户昵称 |
 sxysxy |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.307 s |
| 提交时间 |
2016-12-15 18:01:49 |
内存使用 |
0.37 MiB |
显示代码纯文本
#include <cstdio>
#include <cstdarg>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define BT __attribute__((optimize("O3")))
typedef struct _AVLNode
{
struct _AVLNode *left, *right;
int data; //当前节点数据
int height; //树高，用作平衡因子
int size; //以当前节点为根的子树的节点数
}AVLNode, *pNode, *AVLTree;
#define HEIGHT(x) ((x)?(x)->height:-1)
#define SIZE(x) ((x)?(x)->size:0)
BT
inline void orz_maintain(pNode k)
{ //维护单个节点的信息
if(!k)return;
k -> height = max(HEIGHT(k->left), HEIGHT(k->right))+1;
k -> size = 1 + SIZE(k -> left) + SIZE(k -> right);
}
/* LL 向左孩子的左边插入数据时执行 K1是左孩子，K2是新插入的
K0
/ K1
K1 --K0 LL-> / \
/ K2 K0
K2
*/
BT
inline pNode singleRotateLL(pNode k)
{
pNode k1 = k -> left;
k -> left = k1 -> right;
k1 -> right = k;
orz_maintain(k);
orz_maintain(k1);
return k1;
}
/*
RR 向右孩子的右边插入数据
K0 K1
\ / \
K1 --K0 RR-> k0 k2
\
K2
*/
BT
inline pNode singleRotateRR(pNode k)
{
pNode k1 = k -> right;
k -> right = k1 -> left;
k1 -> left = k;
orz_maintain(k);
orz_maintain(k1);
return k1;
}
/*
LR 向左孩子的右边插入数据
K0 K0 K1
/ / / \
K1 --K1 RR-> K1 --K0 LL-> K2 K0
\ /
K2 K2
*/
BT
inline pNode doubleRotateLR(pNode k)
{
k -> left = singleRotateRR(k -> left);
return singleRotateLL(k);
}
/*
RL 向右孩子的左边插入数据
K0 K0 K1
\ \ / \
K1 --K1 LL-> K1 --K0 RR-> K0 K2
/ \
K2 K2
*/
BT
inline pNode doubleRotateRL(pNode k)
{
k -> right = singleRotateLL(k -> right);
return singleRotateRR(k);
}
//插入
BT
pNode insert(AVLTree t, int x)
{
if(!t) //新建
{
t = new AVLNode;
t -> data = x;
t -> size = 1;
t -> left = t -> right = NULL;
}else
{
if(x < t -> data) //应插入左子树
{
t -> left = insert(t -> left, x);
//插入后不平衡
if(HEIGHT(t -> left) - HEIGHT(t -> right) == 2)
{
//插入了左边的左边
if(x < t -> left -> data)
t = singleRotateLL(t); //左单旋
else
t = doubleRotateLR(t); //左双旋
}
}else //x >= t -> data 插入右子树
{
t -> right = insert(t -> right, x);
if(HEIGHT(t -> right) - HEIGHT(t -> left) == 2)
{
//插入右边的右边
if(x >= t -> right -> data)
t = singleRotateRR(t); //右单旋
else
t = doubleRotateRL(t);
}
}
}
orz_maintain(t);
return t;
}
//查找
BT
pNode find(AVLTree t, int x)
{
if(!t)
return NULL;
else if(t -> data <= x)
return find(t -> right, x);
else if(x < t -> data)
return find(t -> left, x);
else
return t;
}
//查第k大
BT
int kth(AVLTree t, int k)
{
if(!t || k <= 0 || k > t -> size)return 0; //不存在的
int nr = SIZE(t -> right);
if(k == nr+1)
return t -> data; //刚好找到
else if(k <= nr) return kth(t -> right, k); //k <= nr，即要查找名次在右子树，在右子树查第k大（注意，右边大左边小的原则）
else return kth(t -> left, k - nr - 1); //在左子树找第k - nr - 1大
}
//查 <= x的数的个数
BT
int Smaller(pNode t, int x)
{
if(!t)return 0;
if(x < t -> data)
return Smaller(t -> left, x);
else
return 1 + SIZE(t -> left) + Smaller(t -> right, x);
}
//查x的名次
BT
int getRank(pNode t, int x)
{
return t -> size - Smaller(t, x) + 1;
}
//删除后重新平衡
BT
pNode delBalance(AVLTree t)
{
if(HEIGHT(t -> left) - HEIGHT(t -> right) == 2)
{ //删除后左边高了
if(t -> left)
{
//左孩子的左孩子比左孩子的右孩子高，左单旋
if(HEIGHT(t -> left -> left) >= HEIGHT(t -> left -> right))
t = singleRotateLL(t);
else
t = doubleRotateLR(t);
}
}
if(HEIGHT(t -> right) - HEIGHT(t -> left) == 2)
{
if(t -> right)
{
//同理
if(HEIGHT(t -> right -> right) >= HEIGHT(t -> right -> left))
t = singleRotateRR(t);
else
t = doubleRotateRL(t);
}
}
orz_maintain(t);
return t;
}
//删除
BT
pNode delNode(AVLTree t, int x)
{
if(!t)
return t;
if(x == t -> data) //找到要删除的节点
{
//没有右子树，直接让他的左孩子代替他的位置。
if(t -> right == NULL)
{
pNode tmp = t;
t = t -> left;
free(tmp);
}else
{
//存在右子树，找到右子树中最小的节点。
pNode tmp = t -> right;
while(tmp -> left)
tmp = tmp -> left;
//仅仅是替换掉t的值，不是交换tmp与t!!
t -> data = tmp -> data;
//在t的右子树种删掉tmp
t -> right = delNode(t -> right, t -> data);
}
orz_maintain(t);
return t;
}else if(x < t -> data)
{
t -> left = delNode(t -> left, x); //向左边删除
}else
{
t -> right = delNode(t -> right, x);
}
//维护平衡和维护信息。
if(t -> left)
t -> left = delBalance(t -> left);
if(t -> right)
t -> right = delBalance(t -> right);
if(t)
t = delBalance(t);
return t;
}
#include <cctype>
namespace IO
{
char buf[1<<16], *fs, *ft;
BT
inline char readc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<16,stdin), fs==ft))?0:*fs++;
}
BT
inline int fast_read()
{
char c = readc();
int r = 0;
bool sig = false;
while(c > '9' || c < '0')
{
if(c == '-')sig = true;
c = readc();
}
while(c >= '0' && c <= '9')
{
r = (r<<3)+(r<<1)+(c^0x30);
c = readc();
}
return sig?-r:r;
}
}using IO::fast_read;using IO::readc;
BT
int main()
{
freopen("arr.in", "r", stdin);
freopen("arr.out", "w", stdout);
AVLTree root = NULL;
int n = fast_read();
int q = fast_read();
while(q--)
{
char c;
while(!isalpha(c = readc()));
int v = fast_read();
if(c == 'i')
root = insert(root, v);
else if(c == 'd')
{
int r = kth(root, root->size-v+1);
printf("%d\n", r);
root = delNode(root, r);
}
}
return 0;
}