Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- using namespace std;
- struct node{
- int y, size, val, min_v;
- bool reversed;
- node * left, * right;
- };
- void push(node * &v){
- if(v -> left)
- v -> left -> reversed ^= true;
- if(v -> right)
- v -> right -> reversed ^= true;
- }
- inline void rev(node * &v){
- if(v -> reversed){
- v -> reversed = false;
- if(v -> right != nullptr && v -> left != nullptr){
- swap(v -> right, v -> left);
- }
- push(v);
- }
- }
- void update(node * &v) {
- if (!v) return;
- rev(v);
- v->size = (v->left ? v->left->size : 0) + (v->right ? v->right->size : 0) + 1;
- v -> min_v = min(min((v -> left ? v -> left -> min_v : 1000 * 1000 * 1000 + 10), (v -> right ? v -> right -> min_v : 1000 * 1000 * 1000 + 10)), v -> val);
- // v->sum = (v->left ? v->left->sum : 0) + v->val + (v->right ? v->right->sum : 0);
- }
- int my_rand() {
- return (rand() << 16) | rand();
- }
- node * merge(node * left, node * right) {
- if (!left) return right;
- if (!right) return left;
- if (left->y > right->y) {
- left->right = merge(left->right, right);
- update(left);
- return left;
- } else {
- right->left = merge(left, right->left);
- update(right);
- return right;
- }
- }
- pair<node *, node *> split(node * tree, int x) {
- if (!tree) return {tree, tree};
- int ind = tree->left ? tree->left->size : 0;
- if (ind > x) {
- auto res = split(tree->left, x);
- tree->left = res.second;
- update(tree);
- return {res.first, tree};
- } else {
- auto res = split(tree->right, x - ind - 1);
- tree->right = res.first;
- update(tree);
- return {tree, res.second};
- }
- }
- node * add(node * tree, node * x, int pos) {
- if (!tree)
- return x;
- if (tree->y > x->y) {
- int ind = tree->left ? tree->left->size : 0;
- if (ind >= pos) {
- tree->left = add(tree->left, x, pos);
- update(tree);
- return tree;
- } else {
- tree->right = add(tree->right, x, pos - ind - 1);
- update(tree);
- return tree;
- }
- } else {
- auto res = split(tree, pos - 1);
- tree = x;
- tree->left = res.first;
- tree->right = res.second;
- update(tree);
- return tree;
- }
- }
- int main(void){
- int n, m;
- cin >> n >> m;
- node * root = nullptr;
- int * a = new int[n];
- for(int i = 0; i < n; ++i){
- cin >> a[i];
- }
- for(int i = 0; i < n; ++i){
- node * v = new node({my_rand(), 1, a[i], a[i], false, nullptr, nullptr});
- root = add(root, v, i);
- }
- char c;
- int x, y;
- for(int i = 0; i < m; ++i){
- cin >> c >> x >> y;
- x--;
- y--;
- if(x > y){
- swap(x, y);
- }
- if(c == '1'){
- auto tree1 = split(root, y);
- pair<node *, node *> tree2;
- tree2 = split(tree1.first, x - 1);
- tree2.second -> reversed = true;
- rev(tree2.second);
- root = merge(merge(tree2.first, tree2.second), tree1.second);
- }
- if(c == '2'){
- auto tree1 = split(root, y);
- pair<node *, node *> tree2;
- tree2 = split(tree1.first, x - 1);
- cout << tree2.second -> min_v << endl;
- root = merge(merge(tree2.first, tree2.second), tree1.second);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement