treap

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <ctime>

class Treap {
private:
    class Node {
        //copyConstruct и т.д.
    public:
        long long element;

        bool reversed; //для next-prev
        long long sum; //уже насчитано на подотрезке
        long long add; //надо добавить
        //addFlag?
        long long assign;
        bool assignFlag;

        bool isIncreasing; //строго?
        bool isDecreasing;
        long long leftmost; //крайний левый
        long long rightmost; //крайний правый

        long long weight; //для неявного
        long long priority;

        Node * left;
        Node * right;

        Node(int x) : element(x), reversed(false), sum(x), add(0), assign(0), assignFlag(false),
            isIncreasing(true), isDecreasing(true), leftmost(x), rightmost(x), weight(1), priority(rand()),
            left(nullptr), right(nullptr) {}
        ~Node() {
            left = right = nullptr;
        }


        void updateSuffixInf() {
            if (this == nullptr) return;

            if (left == nullptr && right == nullptr) {
                isDecreasing = true;
                isIncreasing = true;
                leftmost = rightmost = element;
                return;
            }

            if (left == nullptr) {
                if (right->isDecreasing && element >= right->leftmost) isDecreasing = true;
                else isDecreasing = false;

                if (right->isIncreasing && element <= right->leftmost) isIncreasing = true;
                else isIncreasing = false;

                leftmost = element;
                rightmost = right->rightmost;
            }
            else if (right == nullptr) {
                if (left->isDecreasing && element <= left->rightmost) isDecreasing = true;
                else isDecreasing = false;

                if (left->isIncreasing && element >= left->rightmost) isIncreasing = true;
                else isIncreasing = false;

                leftmost = left->leftmost;
                rightmost = element;
            }
            else {
                if (left->isDecreasing && right->isDecreasing && left->rightmost >= element && element >= right->leftmost) isDecreasing = true;
                else isDecreasing = false;
                if (left->isIncreasing && right->isIncreasing && left->rightmost <= element && element <= right->leftmost) isIncreasing = true;
                else isIncreasing = false;

                leftmost = left->leftmost;
                rightmost = right->rightmost;
            }

        }


        long long getWeight() const {
            if (this == nullptr) return 0;
            else return this->weight;
        }
        void updateWeight() {
            weight = left->getWeight() + right->getWeight() + 1;
        }

        long long getSum() const {
            if (this == nullptr) return 0;
            return sum;
        }
        void updateSum() {
            sum = element + left->getSum() + right->getSum();
        }

        void pushAssign() {
            if (this == nullptr) return;

            if (!assignFlag) return;
            element = assign;
            sum = assign * this->getWeight();
            leftmost = rightmost = assign;
            isIncreasing = isDecreasing = true;

            assignFlag = false;
            if (left != nullptr) {
                left->assign = assign;
                left->assignFlag = true;
            }
            if (right != nullptr) {
                right->assign = assign;
                right->assignFlag = true;
            }
        }

        void pushAdd() {
            if (this == nullptr) return;

            element += add;
            leftmost += add;
            rightmost += add;
            sum += add * this->getWeight();

            if (left != nullptr) {
                left->add += add;
            }
            if (right != nullptr) {
                right->add += add;
            }

            add = 0;
        }
        void pushReversed() {
            if (this == nullptr) return;
            if (!reversed) return;

            std::swap(isDecreasing, isIncreasing);//??????????
            std::swap(leftmost, rightmost);
            std::swap(left, right);

            reversed = false;
            if (left != nullptr) left->reversed ^= true;
            if (right != nullptr) right->reversed ^= true;
        }
    };

    long long findIndForNext(Node * n) {
        if (n == nullptr) return 0;
        globalPush(n);

        if (n->right != nullptr && !n->right->isDecreasing) {
            return n->left->getWeight() + 1 + findIndForNext(n->right);
        }
        if (n->right != nullptr && n->element < n->right->leftmost) {
            return n->left->getWeight() + 1;
        }
        if (n->left != nullptr && n->element > n->left->rightmost) {
            return n->left->getWeight();
        }
        return findIndForNext(n->left);
    }

    long long findIndForPrev(Node * n) {
        if (n == nullptr) return 0;
        globalPush(n);

        if (n->right != nullptr && !n->right->isIncreasing) {
            return n->left->getWeight() + 1 + findIndForPrev(n->right);
        }
        if (n->right != nullptr && n->element > n->right->leftmost) {
            return n->left->getWeight() + 1;
        }
        if (n->left != nullptr && n->element < n->left->rightmost) {
            return n->left->getWeight();
        }
        return findIndForPrev(n->left);
    }


    void recalc(Node * n) {
        if (n == nullptr) return;
        globalPush(n);

        n->updateWeight();
        n->updateSum();
        n->updateSuffixInf();
    }
    void pushAll(Node * n) {
        if (n == nullptr) return;

        n->pushReversed();
        n->pushAdd();
        n->pushAssign();
    }

    void globalPush(Node * n) {
        if (n == nullptr) return;
        pushAll(n);
        pushAll(n->left);
        pushAll(n->right);

        //add
        if (n->left != nullptr) {
            pushAll(n->left->left);
            pushAll(n->left->right);
        }
        if (n->right != nullptr) {
            pushAll(n->right->left);
            pushAll(n->right->right);
        }
    }

    //[key)
    void splitByKey(Node * node, int key, Node * &l, Node * &r) {

        if (node == nullptr) {
            l = r = nullptr;
            return;
        }
        globalPush(node);

        if (node->element > key) {
            splitByKey(node->right, key, node->right, r);
            l = node;
            recalc(l);
        }
        else {
            splitByKey(node->left, key, l, node->left);
            r = node;
            recalc(r);
        }
    }

    //[)key
    std::pair <Node *, Node *> split(Node * node, int key) {
        pushAll(node);

        std::pair<Node*, Node*> result;

        if (node == nullptr) {
            result = std::make_pair(nullptr, nullptr);
        }

        if (node->left->getWeight() + 1 <= key) {
            std::pair <Node *, Node *> splitR = split(node->right, key - node->left->getWeight() - 1);
            node->right = splitR.first;
            recalc(node);
            result = std::make_pair(node, splitR.second);
        }
        else {
            std::pair <Node *, Node *> splitL = split(node->left, key);
            node->left = splitL.second;
            recalc(node);
            result = std::make_pair(splitL.first, node);
        }

        return result;
    }
    Node * merge(Node * l, Node * r) {

        if (l == nullptr) return r;
        if (r == nullptr) return l;

        if (l->priority < r->priority) {
            r->left = merge(l, r->left);
            recalc(r);
            return r;
        }
        else {
            l->right = merge(l->right, r);
            recalc(l);
            return l;
        }
    }

    //обход
    void inOrder(Node * n) {
        if (n == nullptr) return;

        globalPush(n);

        inOrder(n->left);
        std::cout << n->element << " ";
        inOrder(n->right);
    }
    //удаление
    void postOrder(Node * n) {
        if (n == nullptr) return;

        postOrder(n->left);
        postOrder(n->right);
        delete n->left;
        delete n->right; //??
    }


    Node * root;


public:
    Treap() : root(nullptr) {}
    //~Treap() ?? destruct all by postOrder

    void printTreap() {
        inOrder(root);
    }

    void insertOnPos(long long ind, long long x) {
        Node * newNode = new Node(x);
        std::pair <Node *, Node *> spl = split(root, ind);
        root = merge(merge(spl.first, newNode), spl.second);
    }

    long long getSumOnSubsegment(long long lInd, long long rInd) {
        long long ans;
        std::pair <Node *, Node *> rightPart = split(root, rInd + 1);
        std::pair <Node *, Node *> leftPart = split(rightPart.first, lInd);
        ans = leftPart.second->getSum();
        root = merge(merge(leftPart.first, leftPart.second), rightPart.second);

        return ans;
    }

    void deleteOnPos(long long ind) {
        std::pair <Node *, Node *> rightPart = split(root, ind + 1);
        std::pair <Node *, Node *> leftPart = split(rightPart. first, ind);
        delete leftPart.second;
        root = merge(leftPart.first, rightPart.second);
    }

    void assignOnSubsegment(long long x, long long lInd, long long rInd) {
        std::pair <Node *, Node *> rightPart = split(root, rInd + 1);
        std::pair <Node *, Node *> leftPart = split(rightPart.first, lInd);

        globalPush(leftPart.second);

        leftPart.second->assignFlag = true;
        leftPart.second->assign = x;
        //center->pushAssign();

        globalPush(leftPart.second);

        root = merge(merge(leftPart.first, leftPart.second), rightPart.second);
    }

    void addOnSubSegment(long long x, long long lInd, long long rInd) {
        std::pair <Node *, Node *> rightPart = split(root, rInd + 1);
        std::pair <Node *, Node *> leftPart = split(rightPart.first, lInd);

        globalPush(leftPart.second);

        leftPart.second->add += x;
        //center->pushAdd();

        globalPush(leftPart.second);

        root = merge(merge(leftPart.first, leftPart.second), rightPart.second);
    }

    void nextPermutation(long long lInd, long long rInd) {
        Node *l, *r, *center;

        split(root, rInd + 1, l, r);
        split(l, lInd, l, center);
        globalPush(center);
        long long startInd = findIndForNext(center);

        if (startInd == 0) {
            center->reversed = true;
            /*center->pushReversed();

            center->left->pushReversed();
            center->right->pushReversed();*/

            globalPush(center);

            root = merge(l, merge(center, r));
            return;
        }

        Node * suffix, *swapElementC, *swapElementS, *suffixRight;
        split(center, startInd, center, suffix);
        split(center, center->getWeight() - 1, center, swapElementC);

        splitByKey(suffix, swapElementC->element, suffix, suffixRight);
        split(suffix, suffix->getWeight() - 1, suffix, swapElementS);

        suffix = merge(suffix, swapElementC);
        center = merge(center, swapElementS);
        suffix = merge(suffix, suffixRight);

        suffix->reversed = true;
        /*suffix->pushReversed();
        suffix->left->pushReversed();
        suffix->right->pushReversed();*/

        globalPush(suffix);

        root = merge(l, merge(merge(center, suffix), r));
    };

    void prevPermutation(long long lInd, long long rInd) {
        Node *l, *r, *center;
        split(root, rInd + 1, l, r);
        split(l, lInd, l, center);
        globalPush(center);
        long long startInd = findIndForPrev(center);

        if (startInd == 0) {
            center->reversed = true;
            /*center->pushReversed();
            center->left->pushReversed();
            center->right->pushReversed();*/

            globalPush(center);

            root = merge(l, merge(center, r));
            return;
        }

        Node * suffix, *swapElementC, *swapElementS, *suffixRight;
        split(center, startInd, center, suffix);
        split(center, center->getWeight() - 1, center, swapElementC);

        suffix->reversed = true;
        /*suffix->pushReversed();
        suffix->left->pushReversed();
        suffix->right->pushReversed();*/

        globalPush(suffix);

        splitByKey(suffix, swapElementC->element, suffix, suffixRight);
        split(suffixRight, 1, swapElementS, suffixRight);

        suffixRight = merge(swapElementC, suffixRight);
        center = merge(center, swapElementS);
        suffix = merge(suffix, suffixRight);

        root = merge(l, merge(merge(center, suffix), r));
    }
};


int main() {
    srand(time(0));

    long long n, q;
    long long x, l, r;
    long long comand, pos;
    std::cin >> n;
    Treap treap;

    //start tree
    for (long long i = 0; i < n; ++i) {
        std::cin >> x;
        treap.insertOnPos(i, x);
    }


    std::cin >> q;
    for (long long i = 0; i < q; ++i) {
        std::cin >> comand;
        if (comand == 1) {
            std::cin >> l >> r;
            std::cout << treap.getSumOnSubsegment(l, r) << std::endl;
        }
        else if (comand == 2) {
            std::cin >> x >> pos;
            treap.insertOnPos(pos, x);
            //treap.printTreap();
        }
        else if (comand == 3) {
            std::cin >> pos;
            treap.deleteOnPos(pos);
            //treap.printTreap();
        }
        else if (comand == 4) {
            std::cin >> x >> l >> r;
            treap.assignOnSubsegment(x, l, r);
            //treap.printTreap();
        }
        else if (comand == 5) {
            std::cin >> x >> l >> r;
            treap.addOnSubSegment(x, l, r);
            //treap.printTreap();
        }
        else if (comand == 6) {
            std::cin >> l >> r;
            treap.nextPermutation(l, r);
            //treap.printTreap();
            //std::cout << std::endl;
        }
        else if (comand == 7) {
            std::cin >> l >> r;
            treap.prevPermutation(l, r);
            //treap.printTreap();
            //std::cout << std::endl;
        }
    }
    treap.printTreap();
    return 0;
}