7 minutes
[BZOJ3223][TYVJ1728]普通平衡树（FANHQ_TREAP）
这道题就是裸裸的TREAP，然后TREAP的裸题好像已经写过了，于是决定试试写FANHQ TREAP，一开始我插入没写旋转，后来仔细研究了FANHQ的博客，才知道后来他加了旋转（说好的没有旋转呢），然后我去加了旋转果断快了50ms
关于FANHQ TREAP，当然是去看FANHQ在WC上讲课的材料和FANHQ的博客咯： 范浩强_wc2012谈谈各种数据结构.pdf 在线预览 挖掘Treap的潜力- fanhq666的日志- 网易博客
然后贴上我的程序，貌似不算快
//BZOJ 3224.cpp fanhq_treap
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
//#define LOCAL
//#define VISUAL_STUDIO
#define READ_FREAD
//#define READ_FILE
#ifdef VISUAL_STUDIO
#pragma warning(disable:4996)
#endif
#ifdef LOCAL
#define LOCAL_TIME
//#define DEBUG_DETAIL
//#define DEBUG_ID
//#define DEBUG_SIZE
//#define LOCAL_DEBUG
//#define STD_DEBUG
#endif
#ifdef LOCAL_TIME
#include<ctime>
#endif
#ifdef READ_FREAD
const int MAXS = 10 * 1024 * 1024;
char fread_string[MAXS];
char *fread_point = fread_string;
inline int get_int()
{
int ret = 0;
int sign = 1;
while ((*fread_point < '0') || (*fread_point > '9'))
{
sign = 1;
if (*fread_point == '-')
{
sign = -1;
}
fread_point++;
}
while ((*fread_point >= '0') && (*fread_point <= '9'))
{
ret = ret * 10 + *(fread_point++) - '0';
}
return sign * ret;
}
#endif
inline void read(int &input_num)
{
#ifdef READ_FREAD
input_num = get_int();
#else
scanf("%d", &input_num);
#endif
}
typedef long long ll;
/*---rank---*/
const int rank_base = 1753;
inline int get_rank()
{
return (rand() << 11) + rand();
}
/*---rank---*/
struct treap_node
{
int val, rank, size;
treap_node *l_child, *r_child, *parent;
inline treap_node *init(const int val_ = 0, treap_node *l_child_ = NULL, treap_node *r_child_ = NULL, treap_node *parent_ = NULL)
{
val = val_;
size = 1;
l_child = l_child_;
r_child = r_child_;
parent = parent_;
return this;
}
inline treap_node()
{
init();
}
};
#ifndef NULL
#define NULL 0
#endif
/*---recover memory---*/
const int MAXN = 100000;
treap_node node_memory[MAXN];
treap_node *memory_stack[MAXN];
int treap_top = MAXN;
inline void init_memory()
{
for (int i = 0; i < MAXN; i++)
{
memory_stack[i] = node_memory + i;
node_memory[i].rank = get_rank();
}
}
inline treap_node *new_node(const int val = 0, treap_node *l_child = NULL, treap_node *r_child = NULL, treap_node *parent = NULL)
{
return memory_stack[--treap_top]->init(val, l_child, r_child, parent);
}
inline void delete_node(treap_node *del_node)
{
memory_stack[treap_top++] = del_node;
del_node->init();
}
/*---recover memory---*/
treap_node *head;
/*---treap---*/
inline void attach_as_l_child(treap_node *parent, treap_node *child)
{
parent->l_child = child;
if (child != NULL)
{
child->parent = parent;
}
}
inline void attach_as_r_child(treap_node *parent, treap_node *child)
{
parent->r_child = child;
if (child != NULL)
{
child->parent = parent;
}
}
inline int treap_size(treap_node *size_node)
{
if (size_node == NULL)
{
return 0;
}
return size_node->size;
}
inline void treap_update_size(treap_node *update_node)
{
update_node->size = treap_size(update_node->l_child) + treap_size(update_node->r_child) + 1;
}
inline void treap_update(treap_node *update_node)
{
treap_update_size(update_node);
}
treap_node *treap_merge(treap_node *merge_left, treap_node *merge_right)
{
if ((merge_left == NULL) && (merge_right == NULL))
{
return NULL;
}
if (merge_left == NULL)
{
return merge_right;
}
if (merge_right == NULL)
{
return merge_left;
}
if (merge_left->rank < merge_right->rank)
{
attach_as_r_child(merge_left, treap_merge(merge_left->r_child, merge_right));
treap_update(merge_left);
return merge_left;
}
else
{
attach_as_l_child(merge_right, treap_merge(merge_left, merge_right->l_child));
treap_update(merge_right);
return merge_right;
}
return NULL;
}
inline treap_node *treap_search_val(const int val, const int add_size = 0, bool get_same = true)
{
treap_node *last_visit = head;
treap_node *found = NULL;
for (treap_node *tmp = head; tmp != NULL;)
{
last_visit = tmp;
if (tmp->val == val)
{
found = tmp;
tmp = tmp->l_child;
}
else if (tmp->val < val)
{
tmp = tmp->r_child;
}
else
{
tmp = tmp->l_child;
}
}
for (treap_node *tmp = ((found != NULL) && get_same ? found->parent : last_visit); tmp != NULL; tmp = tmp->parent)
{
tmp->size += add_size;
}
return ((found != NULL) && get_same ? found : last_visit);
}
inline void zig(treap_node *axis)
{
treap_node *left_child = axis->l_child;
treap_node *parent = axis->parent;
attach_as_l_child(axis, left_child->r_child);
attach_as_r_child(left_child, axis);
left_child->parent = parent;
if (parent == NULL)
{
head = left_child;
}
else if (parent->l_child == axis)
{
parent->l_child = left_child;
}
else
{
parent->r_child = left_child;
}
treap_update(axis);
treap_update(left_child);
}
inline void zag(treap_node *axis)
{
treap_node *right_child = axis->r_child;
treap_node *parent = axis->parent;
attach_as_r_child(axis, right_child->l_child);
attach_as_l_child(right_child, axis);
right_child->parent = parent;
if (parent == NULL)
{
head = right_child;
}
else if (parent->l_child == axis)
{
parent->l_child = right_child;
}
else
{
parent->r_child = right_child;
}
treap_update(axis);
treap_update(right_child);
}
inline void treap_route(treap_node *route_node)
{
while ((route_node->parent != NULL) && (route_node->rank < route_node->parent->rank))
{
if (route_node->parent->l_child == route_node)
{
zig(route_node->parent);
}
else
{
zag(route_node->parent);
}
}
}
inline void treap_insert(const int val)
{
treap_node *tmp = new_node(val);
if (head == NULL)
{
head = tmp;
}
else
{
treap_node *insert_pt = treap_search_val(val, 1, false);
if (insert_pt->val < val)
{
attach_as_r_child(insert_pt, tmp);
}
else
{
attach_as_l_child(insert_pt, tmp);
}
treap_route(insert_pt);
}
}
inline void treap_delete(const int val)
{
treap_node *del_node = treap_search_val(val, -1);
treap_node *tmp = treap_merge(del_node->l_child, del_node->r_child);
if (del_node->parent == NULL)
{
head = tmp;
tmp->parent = NULL;
}
else if (del_node->parent->l_child == del_node)
{
attach_as_l_child(del_node->parent, tmp);
}
else
{
attach_as_r_child(del_node->parent, tmp);
}
delete_node(del_node);
}
inline int treap_rank(const int val)
{
int ret = -1;
int rank = 0;
for (treap_node *tmp = head; tmp != NULL;)
{
if (tmp->val == val)
{
ret = rank + treap_size(tmp->l_child) + 1;
tmp = tmp->l_child;
}
else if (tmp->val < val)
{
rank += treap_size(tmp->l_child) + 1;
tmp = tmp->r_child;
}
else
{
tmp = tmp->l_child;
}
}
return ret;
}
inline int treap_num(const int rank)
{
int size = 0;
for (treap_node *tmp = head; tmp != NULL;)
{
if (size + treap_size(tmp->l_child) + 1 == rank)
{
return tmp->val;
}
if (size + treap_size(tmp->l_child) + 1 < rank)
{
size += treap_size(tmp->l_child) + 1;
tmp = tmp->r_child;
}
else
{
tmp = tmp->l_child;
}
}
return -1;
}
inline int treap_prev(const int val)
{
int max = -1;
for (treap_node *tmp = head; tmp != NULL;)
{
if (tmp->val < val)
{
if (tmp->val > max)
{
max = tmp->val;
}
tmp = tmp->r_child;
}
else
{
tmp = tmp->l_child;
}
}
return max;
}
inline int treap_next(const int val)
{
int min = -1;
for (treap_node *tmp = head; tmp != NULL;)
{
if (tmp->val > val)
{
if ((min == -1) || (tmp->val < min))
{
min = tmp->val;
}
tmp = tmp->l_child;
}
else
{
tmp = tmp->r_child;
}
}
return min;
}
#ifdef LOCAL_DEBUG
int checker_prev = -1;
inline void treap_checker(treap_node *root = head)
{
if (root == NULL)
{
return;
}
int size = 0;
if (root->l_child != NULL)
{
if (root->l_child->parent != root)
{
printf("ERROR ");
}
treap_checker(root->l_child);
size += root->l_child->size;
}
printf("%d ", root->val);
if (root->val < checker_prev)
{
printf("ERROR_ORDER ");
}
checker_prev = root->val;
if (root->r_child != NULL)
{
if (root->r_child->parent != root)
{
printf("ERROR ");
}
treap_checker(root->r_child);
size += root->r_child->size;
}
if (size + 1 != root->size)
{
printf("E %d ERROR_SIZE ", root->val);
}
}
#endif
/*---treap---*/
const int OP_INS = 1;
const int OP_DEL = 2;
const int OP_QRK = 3;
const int OP_QNM = 4;
const int OP_PRE = 5;
const int OP_NET = 6;
int n;
int operator_num, x;
int main()
{
#ifdef LOCAL_TIME
ll start_time_ = clock();
#endif
#ifdef READ_FILE
freopen("3224.in", "r", stdin);
#ifndef STD_DEBUG
#ifdef LOCAL_DEBUG
freopen("3224_debug.out", "w", stdout);
#else
freopen("3224.out", "w", stdout);
#endif
#endif
#endif
#ifdef READ_FREAD
fread(fread_string, 1, MAXS, stdin);
#endif
srand(rank_base);
init_memory();
read(n);
#ifdef DEBUG_SIZE
int size = 0;
#endif
for (int i = 0; i < n; i++)
{
read(operator_num);
read(x);
#ifdef LOCAL_DEBUG
printf("INPUT: %d %d %dn", i, operator_num, x);
if (i == 6)
{
printf("DEBUG:6n");
}
#endif
#ifdef DEBUG_DETAIL
if (i == 3506)
{
printf("DEBUG:3506n");
}
#endif
#ifdef DEBUG_ID
printf("%d ", i);
#endif
if (operator_num == OP_INS)
{
#ifdef DEBUG_SIZE
size++;
#endif
treap_insert(x);
}
else if (operator_num == OP_DEL)
{
#ifdef DEBUG_SIZE
size--;
#endif
treap_delete(x);
}
else if (operator_num == OP_QRK)
{
printf("%dn", treap_rank(x));
}
else if (operator_num == OP_QNM)
{
printf("%dn", treap_num(x));
}
else if (operator_num == OP_PRE)
{
printf("%dn", treap_prev(x));
}
else if (operator_num == OP_NET)
{
printf("%dn", treap_next(x));
}
#ifdef DEBUG_SIZE
if (size != head->size)
{
printf("ERROR!!n");
}
#endif
#ifdef LOCAL_DEBUG
checker_prev = -1;
printf("DEBUG: ");
treap_checker();
printf("n");
#endif
}
#ifdef LOCAL_TIME
printf("run time: %lld ms", clock() - start_time_);
#endif
#ifdef READ_FILE
fclose(stdin);
#ifndef STD_DEBUG
fclose(stdout);
#endif
#endif
return 0;
}
Read other posts