6 minutes
[BZOJ3223][TYVJ1729]文艺平衡树（FANHQ_TREAP）
平衡树三件套的第三题目测要树套，我太弱了所以不会，只好接着用FANHQ_TREAP水第二题了。听说这题目只有一个操作，于是很高端地用了FANHQ_TREAP。但是莫名其妙写得好慢，比RANK1慢了1S多，一定是还有什么神奇的算法，求教。。
关于FANHQ_TREAP的问题详见我的上一篇日志[TYVJ1728]普通平衡树（FANHQ_TREAP）FANHQ_TREAP好像能实现SPLAY几乎全部的操作，而且支持持久化，常数又小，听起来就很高端。。
//BZOJ 3223.cpp fanhq_treap
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
//#define LOCAL
//#define READ_FILE
#define READ_FREAD
//#define VISUAL_STUDIO
#ifdef VISUAL_STUDIO
#pragma warning(disable:4996)
#endif
#ifdef LOCAL
#define LOCAL_TIME
//#define LOCAL_DEBUG
//#define STD_DEBUG
#endif
#ifdef LOCAL_TIME
#include<ctime>
#endif
#ifndef NULL
#define NULL 0
#endif
typedef long long ll;
#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;
char fread_point = getchar();
while ((fread_point < '0') || (fread_point > '9'))
{
fread_point = getchar();
}
while ((fread_point >= '0') && (fread_point <= '9'))
{
ret = ret * 10 + fread_point - '0';
fread_point = getchar();
}
return ret;
}
#endif
inline void read(int &input_num)
{
#ifdef READ_FREAD
input_num = get_int();
#else
scanf("%d", &input_num);
#endif
}
/*---rank---*/
const int rand_base = 79;
inline int get_rank()
{
return (rand() << 11) + rand();
}
/*---rank---*/
struct treap_node
{
int val;
treap_node *l_child, *r_child, *parent;
bool down_swap;
int size, rank;
inline treap_node *init(const int val_, treap_node *l_child_, treap_node *r_child_, treap_node *parent_)
{
val = val_;
l_child = l_child_;
r_child = r_child_;
parent = parent_;
down_swap = false;
size = 1;
return this;
}
inline treap_node(const int val_ = -1, treap_node *l_child_ = NULL, treap_node *r_child_ = NULL, treap_node *parent_ = NULL)
{
init(val_, l_child_, r_child_, parent_);
}
};
/*---recover memory---*/
const int MAXN = 100000 + 10;
treap_node node_memory[MAXN];
treap_node *memory_stack[MAXN];
int stack_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 = -1, treap_node *l_child = NULL, treap_node *r_child = NULL, treap_node *parent = NULL)
{
return memory_stack[--stack_top]->init(val, l_child, r_child, parent);
}
inline void delete_node(treap_node *del_node)
{
memory_stack[stack_top++] = del_node;
}
/*---recover memory---*/
treap_node *head = NULL;
/*---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 void treap_swap(treap_node *swap_node)
{
if (swap_node == NULL)
{
return;
}
std::swap(swap_node->l_child, swap_node->r_child);
swap_node->down_swap = !swap_node->down_swap;
}
inline int treap_size(treap_node *query_node)
{
if (query_node == NULL)
{
return 0;
}
return query_node->size;
}
inline void treap_update_size(treap_node *update_node)
{
if (update_node == NULL)
{
return;
}
update_node->size = treap_size(update_node->l_child) + treap_size(update_node->r_child) + 1;
}
inline void treap_down_swap(treap_node *down_node)
{
if (down_node == NULL)
{
return;
}
if (down_node->down_swap)
{
treap_swap(down_node->l_child);
treap_swap(down_node->r_child);
down_node->down_swap = false;
}
}
inline void treap_down(treap_node *down_node)
{
treap_down_swap(down_node);
}
inline void treap_update(treap_node *update_node)
{
treap_update_size(update_node);
}
inline void zig(treap_node *axis)
{
treap_node *left_child = axis->l_child;
treap_node *parent = axis->parent;
treap_down(axis);
treap_down(left_child);
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;
treap_down(axis);
treap_down(right_child);
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_insert_size(treap_node *v)
{
for (; v != NULL; v = v->parent)
{
v->size++;
}
}
void treap_cut(treap_node *root, treap_node *&treap_left, treap_node *&treap_right, const int cut_left)
{
if (cut_left == 0)
{
treap_left = NULL;
treap_right = root;
}
else if (cut_left == treap_size(root))
{
treap_left = root;
treap_right = NULL;
}
if (root == NULL)
{
treap_left = NULL;
treap_right = NULL;
return;
}
else
{
treap_down(root);
if (treap_size(root->l_child) + 1 <= cut_left)
{
treap_left = root;
treap_cut(root->r_child, treap_left->r_child, treap_right, cut_left - treap_size(root->l_child) - 1);
if (treap_left->r_child != NULL)
{
treap_left->r_child->parent = treap_left;
}
treap_update(treap_left);
}
else
{
treap_right = root;
treap_cut(root->l_child, treap_left, treap_right->l_child, cut_left);
if (treap_right->l_child != NULL)
{
treap_right->l_child->parent = treap_right;
}
treap_update(treap_right);
}
}
}
treap_node *treap_merge(treap_node *merge_left, treap_node *merge_right)
{
if (merge_left == NULL)
{
return merge_right;
}
else if (merge_right == NULL)
{
return merge_left;
}
treap_node *ret = NULL;
if (merge_left->rank < merge_right->rank)
{
ret = merge_left;
treap_down(ret);
attach_as_r_child(ret, treap_merge(ret->r_child, merge_right));
}
else
{
ret = merge_right;
treap_down(ret);
attach_as_l_child(ret, treap_merge(merge_left, ret->l_child));
}
treap_update(ret);
return ret;
}
inline void treap_route(treap_node *v)
{
while ((v->parent != NULL) && (v->rank < v->parent->rank))
{
if (v->parent->l_child == v)
{
zig(v->parent);
}
else
{
zag(v->parent);
}
}
}
inline void treap_insert(const int n)
{
treap_node *v = NULL;
for (int i = 1; i <= n; i++)
{
treap_node *insert_node = new_node(i);
if (v == NULL)
{
head = insert_node;
}
else
{
attach_as_r_child(v, insert_node);
treap_insert_size(v);
treap_route(insert_node);
}
v = insert_node;
}
}
inline void treap_reverse(const int l, const int r)
{
treap_node *treap_l = NULL, *treap_r = NULL, *treap_reverse = NULL;
treap_cut(head, treap_l, treap_r, l - 1);
treap_cut(treap_r, treap_reverse, treap_r, r - l + 1);
treap_swap(treap_reverse);
treap_l = treap_merge(treap_l, treap_reverse);
head = treap_merge(treap_l, treap_r);
head->parent = NULL;
}
void treap_print(treap_node *root)
{
if (root == NULL)
{
return;
}
treap_down(root);
treap_print(root->l_child);
printf("%d ", root->val);
treap_print(root->r_child);
}
#ifdef LOCAL_DEBUG
inline void treap_checker(treap_node *root = head, bool down_swap = false)
{
if (root == NULL)
{
return;
}
int size = 0;
if ((root->l_child != NULL) && (!down_swap))
{
if (root->l_child->parent != root)
{
printf("ERROR ");
}
if (root->l_child->rank < root->rank)
{
printf("ERROR_RANK ");
}
treap_checker(root->l_child, down_swap ^ root->down_swap);
size += root->l_child->size;
}
if ((root->r_child != NULL) && down_swap)
{
if (root->r_child->parent != root)
{
printf("ERROR ");
}
if (root->r_child->rank < root->rank)
{
printf("ERROR_RANK ");
}
treap_checker(root->r_child, down_swap ^ root->down_swap);
size += root->r_child->size;
}
printf("%d ", root->val);
if ((root->l_child != NULL) && down_swap)
{
if (root->l_child->parent != root)
{
printf("ERROR ");
}
if (root->l_child->rank < root->rank)
{
printf("ERROR_RANK ");
}
treap_checker(root->l_child, down_swap ^ root->down_swap);
size += root->l_child->size;
}
if ((root->r_child != NULL) && (!down_swap))
{
if (root->r_child->parent != root)
{
printf("ERROR ");
}
if (root->r_child->rank < root->rank)
{
printf("ERROR_RANK ");
}
treap_checker(root->r_child, down_swap ^ root->down_swap);
size += root->r_child->size;
}
if (size + 1 != root->size)
{
printf("E %d ERROR_SIZE ", root->val);
}
}
#endif
/*---treap---*/
int n, m;
int rec_l, rec_r;
int main()
{
#ifdef LOCAL_TIME
ll start_time_ = clock();
#endif
#ifdef READ_FILE
freopen("3223.in", "r", stdin);
#ifndef STD_DEBUG
freopen("3223.out", "w", stdout);
#endif
#endif
#ifdef READ_FREAD
//fread(fread_string, 1, MAXS, stdin);
#endif
srand(rand_base);
init_memory();
read(n);
read(m);
treap_insert(n);
#ifdef LOCAL_DEBUG
treap_checker();
printf("n");
#endif
for (int i = 0; i < m; i++)
{
read(rec_l);
read(rec_r);
treap_reverse(rec_l, rec_r);
#ifdef LOCAL_DEBUG
treap_checker();
printf("n");
#endif
}
treap_print(head);
#ifdef LOCAL_TIME
printf("nrun time: %lld msn", clock() - start_time_);
#endif
#ifdef READ_FILE
fclose(stdin);
#ifndef STD_DEBUG
fclose(stdout);
#endif
#endif
return 0;
}
Read other posts