Last active
March 21, 2023 14:05
-
-
Save catupper/a51c9c3aeded909e22d8949f070122c0 to your computer and use it in GitHub Desktop.
Solve AOJ 1508 with Treap
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
#include<algorithm> | |
#include<vector> | |
using namespace std; | |
const int INF = 1 << 30; | |
struct Node{ | |
Node *left, *right, *parent; | |
int value; | |
int size; | |
int min; | |
int priority; | |
Node (int v): | |
value(v), | |
left(nullptr), | |
right(nullptr), | |
parent(nullptr), | |
size(1), | |
min(v), | |
priority(rand()){} | |
// update size and min | |
Node* update(); | |
Node *add_right_child(Node *c); | |
Node *add_left_child(Node *c); | |
// set value and update all ancestors; | |
void set_value(int value); | |
Node *rotate(); | |
}; | |
void view(Node *now){ | |
if(now->left) cout << now->value << " L " << now->left->value << endl; | |
if(now->right) cout << now->value << " R " << now->right->value << endl; | |
if(now->left && now->left != now)view(now->left); | |
if(now->right && now->right != now)view(now->right); | |
} | |
Node * Node::add_right_child(Node *c){ | |
this->right = c; | |
if(c)c->parent = this; | |
return this->update(); | |
} | |
Node * Node::add_left_child(Node *c){ | |
this->left = c; | |
if(c)c->parent = this; | |
return this->update(); | |
} | |
Node * Node::rotate(){ | |
if(this->parent == nullptr)return this; | |
Node *p = this->parent; | |
Node *pp = p->parent; | |
Node *center; | |
if(p->left == this){ | |
center = this->right; | |
p->left = center; | |
this->right = p; | |
} | |
else{ | |
center = this->left; | |
p->right = center; | |
this->left = p; | |
} | |
if(center)center->parent = p; | |
p->parent = this; | |
this->parent = pp; | |
if(pp && pp->left == p)pp->left = this; | |
if(pp && pp->right == p)pp->right = this; | |
p->update(); | |
this->update(); | |
return this; | |
} | |
int get_size(Node* node){ | |
return node ? node->size : 0; | |
} | |
int get_min(Node* node){ | |
return node ? node->min : INF; | |
} | |
Node *Node::update(){ | |
size = 1 + get_size(left) + get_size(right); | |
min = std::min({value, get_min(left), get_min(right)}); | |
return this; | |
} | |
void update_to_root(Node *node){ | |
while(node){ | |
node->update(); | |
node = node->parent; | |
} | |
} | |
void Node::set_value(int value){ | |
this->value = value; | |
update_to_root(this); | |
} | |
Node *access(Node *root, int pos){ | |
if(pos >= get_size(root))return nullptr; | |
int lsize = get_size(root->left); | |
if(lsize == pos)return root; | |
else if(lsize > pos)return access(root->left, pos); | |
else return access(root->right, pos - lsize - 1); | |
} | |
Node *insert(Node *root, int pos, int val){ | |
if(pos > get_size(root))return nullptr; | |
Node *new_node = new Node(val); | |
if(get_size(root) == 0)return new_node; | |
if(pos == get_size(root)){ | |
Node *current = root; | |
while(current->right)current = current->right; | |
current->add_right_child(new_node); | |
}else{ | |
Node *current = access(root, pos); | |
if(current->left){ | |
current = current->left; | |
while(current->right){ | |
current = current->right; | |
} | |
current->add_right_child(new_node); | |
} | |
else{ | |
current->add_left_child(new_node); | |
} | |
} | |
update_to_root(new_node); | |
while(new_node->parent && new_node->parent->priority > new_node->priority){ | |
new_node->rotate(); | |
} | |
Node *new_root = new_node; | |
while(new_root->parent){ | |
new_root = new_root->parent; | |
} | |
return new_root; | |
} | |
Node *remove(Node *root, int pos){ | |
Node *current = access(root, pos); | |
if(current == nullptr)return root; | |
while(current->left || current->right){ | |
if(current->left == nullptr)current->right->rotate(); | |
else if(current->right == nullptr)current->left->rotate(); | |
else if(current->left->priority < current->right->priority)current->left->rotate(); | |
else current->right->rotate(); | |
} | |
Node *p = current->parent; | |
if(p && p->left == current)p->left = nullptr; | |
if(p && p->right == current)p->right = nullptr; | |
current->parent = nullptr; | |
delete current; | |
update_to_root(p); | |
while(p && p->parent)p = p->parent; | |
return p; | |
} | |
Node *merge(Node *l, Node *r){ | |
if(l == nullptr)return r; | |
if(r == nullptr)return l; | |
if(l->priority < r->priority){ | |
if(l->right)l->right->parent = nullptr; | |
l->add_right_child(merge(l->right, r)); | |
return l; | |
} | |
else{ | |
if(r->left)r->left->parent = nullptr; | |
r->add_left_child(merge(l, r->left)); | |
return r; | |
} | |
} | |
pair<Node*, Node*> split(Node *root, int pos){ | |
if(pos == 0)return {nullptr, root}; | |
if(pos == get_size(root))return {root, nullptr}; | |
int lsize = get_size(root->left); | |
if(pos <= lsize){ | |
root->left->parent = nullptr; | |
auto [l, r] = split(root->left, pos); | |
root->add_left_child(r); | |
return {l, root}; | |
}else{ | |
root->right->parent = nullptr; | |
auto [l, r] = split(root->right, pos - lsize - 1); | |
root->add_right_child(l); | |
return {root, r}; | |
} | |
} | |
// using merge,split | |
Node *insert_with_merge_split(Node *root, int pos, int val){ | |
Node *new_node = new Node(val); | |
if(pos == get_size(root))return merge(root, new_node); | |
auto [l, r] = split(root, pos); | |
return merge(merge(l, new_node), r); | |
} | |
Node *remove_with_merge_split(Node *root, int pos){ | |
if(pos == 0)return split(root, 1).second; | |
if(pos == get_size(root) - 1)return split(root, pos).first; | |
auto [l, cr] = split(root, pos); | |
auto [c, r] = split(cr, 1); | |
return merge(l, r); | |
} | |
// using insert, remove | |
Node *merge_with_insert_remove(Node *l, Node *r){ | |
Node *tmp = new Node(0); | |
int lsize = get_size(l); | |
tmp->priority = -1; | |
tmp->add_left_child(l); | |
tmp->add_right_child(r); | |
return remove(tmp, lsize); | |
} | |
pair<Node*, Node*> split_with_insert_remove(Node *node, int pos){ | |
Node *tmp = insert(node, pos, 0); | |
Node *target = access(tmp, pos); | |
while(target->parent)target->rotate(); | |
if(target->left)target->left->parent = nullptr; | |
if(target->right)target->right->parent = nullptr; | |
pair<Node*, Node*> res = {target->left, target->right}; | |
delete target; | |
return res; | |
} | |
void test(int trial){ | |
Node *tree = nullptr; | |
vector<int> vec; | |
while(trial--){ | |
if(vec.empty() || rand() % 3 != 0){ | |
int val = rand(); | |
int pos = rand() % (vec.size() + 1); | |
vec.insert(vec.begin() + pos, val); | |
tree = insert(tree, pos, val); | |
//tree = insert_with_merge_split(tree, pos, val); | |
} | |
else{ | |
int pos = rand() % vec.size(); | |
int vec_val = vec[pos]; | |
int tree_val = access(tree, pos)->value; | |
if(vec_val == tree_val)cerr << "OK " << vec_val << " " << tree_val << endl; | |
else cerr << "NG " << vec_val << " " << tree_val << endl; | |
vec.erase(vec.begin() + pos); | |
tree = remove(tree, pos); | |
//tree = remove_with_merge_split(tree, pos); | |
} | |
cerr << vec.size() << " " << get_size(tree) << endl; | |
} | |
} | |
// AOJ 1508 | |
int main(){ | |
int n, q; | |
cin >> n >> q; | |
Node *tree = nullptr; | |
for(int i = 0;i < n;i++){ | |
int a; | |
cin >> a; | |
tree = insert_with_merge_split(tree, i, a); | |
} | |
while(q--){ | |
int x, y, z; | |
cin >> x >> y >> z; | |
if(x == 0){// shift | |
int l = y, r = z; | |
int moving_value = access(tree, r)->value; | |
tree = remove_with_merge_split(tree, r); | |
tree = insert_with_merge_split(tree, l, moving_value); | |
} | |
if(x == 1){// get_min of [l, r] | |
int l = y, r = z; | |
auto [ltree_center, rtree] = split_with_insert_remove(tree, r+1); | |
auto [ltree, center] = split_with_insert_remove(ltree_center, l); | |
cout << center->min << endl; | |
tree = merge_with_insert_remove(merge_with_insert_remove(ltree, center), rtree); | |
} | |
if(x == 2){// update | |
int pos = y, val = z; | |
auto target = access(tree, pos); | |
target->set_value(val); | |
} | |
} | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment