Solve AOJ 1508 with Treap

Treap.cpp

#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;
}