Language: C++

#include <bits/stdc++.h>
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;

template <typename Monoid>
struct AccRandomizedBinarySearchTree {
public:
    static constexpr int POOL_SIZE = 200000;

private:
    struct Node {
        using BaseMonoid = Monoid;
        using T = typename BaseMonoid::T;
        using Ptr = Node*;
        using PtrPair = pair<Ptr, Ptr>;
        Node() : left{}, right{}, value{}, accum{}, size{1} {}
        Node(const T& value) : left{}, right{}, value{value}, accum{value}, size{1} {}
        Ptr left, right;
        T value;
        T accum;
        int size;

        static void serialize(Ptr a, vector<T>& v)
        {
            if (a == nullptr) {
                return;
            } else {
                serialize(a->left, v);
                v.push_back(a->value);
                serialize(a->right, v);
            }
        }
        static unsigned xor128()
        {
            static unsigned x = 123456789;
            static unsigned y = 362436069;
            static unsigned z = 521288629;
            static unsigned w = 88675123;
            const unsigned t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            return w = (w ^ (w << 19)) ^ (t ^ (t >> 8));
        }

        static unsigned getRand(const int maximum)
        {
            return xor128() % maximum;
        }

        static T acc(const T& a, const T& b)
        {
            static const BaseMonoid ACC{};
            return ACC(a, b);
        }

        static int getSize(const Ptr a)
        {
            return (a == nullptr) ? 0 : a->size;
        }
        static T getAcc(const Ptr a)
        {
            return (a == nullptr) ? BaseMonoid::identity() : a->accum;
        }

        static Ptr update(Ptr a)
        {
            a->size = getSize(a->left) + getSize(a->right) + 1;
            a->accum = acc(acc(getAcc(a->left), getAcc(a->right)), a->value);
            return a;
        }

        static Ptr merge(Ptr a, Ptr b)
        {
            if (a == nullptr) {
                return b;
            } else if (b == nullptr) {
                return a;
            }
            const int asize = getSize(a);
            const int bsize = getSize(b);
            if (getRand(asize + bsize) < asize) {
                a->right = merge(a->right, b);
                return update(a);
            } else {
                b->left = merge(a, b->left);
                return update(b);
            }
        }

        static PtrPair split(Ptr a, const int k)  // size = (k,n-k)
        {
            if (a == nullptr) {
                return make_pair(Ptr{}, Ptr{});
            }
            if (k <= getSize(a->left)) {
                const PtrPair s = split(a->left, k);
                a->left = s.second;
                return make_pair(s.first, update(a));
            } else {
                const PtrPair s = split(a->right, k - getSize(a->left) - 1);
                a->right = s.first;
                return make_pair(update(a), s.second);
            }
        }
        static Ptr insert(Ptr a, const int k, Ptr b)
        {
            const PtrPair s = split(a, k);
            return merge(merge(s.first, b), s.second);
        }

        static PtrPair erase(Ptr a, const int k)
        {
            const PtrPair sr = split(a, k + 1);
            const PtrPair sl = split(sr.first, k);
            return make_pair(merge(sl.first, sr.second), sl.second);
        }
    };

    using Ptr = typename Node::Ptr;
    using PtrPair = typename Node::PtrPair;

    int head = 0;
    static Node pool[POOL_SIZE];
    Ptr alloc(const typename Node::T& x)
    {
        assert(head < POOL_SIZE);
        pool[head].value = x;
        pool[head].size = 1;
        pool[head].left = nullptr;
        pool[head].right = nullptr;
        pool[head].accum = x;
        head++;
        return pool + head - 1;
    }
    void garbage_collect()
    {
        vector<T> v;
        Node::serialize(root, v);
        head = 0;
        root = nullptr;
        rev_root = nullptr;
        for (int i = 0; i < v.size(); i++) {
            root = Node::insert(root, i, alloc(v[i]));
            rev_root = Node::insert(rev_root, v.size() - i - 1, alloc(v[i]));
        }
    }

    Ptr root;
    Ptr rev_root;

public:
    using BaseMonoid = Monoid;
    using T = typename Node::T;
    AccRandomizedBinarySearchTree() : root{}, rev_root{} {}

    int getSize() const
    {
        return Node::getSize(root);
    }
    void insert(const int k, const T& value)
    {
        const int s = Node::getSize(root);
        assert(0 <= k);
        assert(k <= s);
        if (head == POOL_SIZE) {
            garbage_collect();
        }
        root = Node::insert(root, k, alloc(value));
        rev_root = Node::insert(rev_root, s - k, alloc(value));
    }
    void erase(const int k)
    {
        const int s = Node::getSize(root);
        assert(0 <= k);
        assert(k < s);
        Ptr p;
        tie(root, p) = Node::erase(root, k);
        if (p != nullptr) {
            p->left = Ptr{};
            p->right = Ptr{};
        }
        tie(rev_root, p) = Node::erase(rev_root, s - k - 1);
        if (p != nullptr) {
            p->left = Ptr{};
            p->right = Ptr{};
        }
    }
    T get(int k) const
    {
        assert(0 <= k);
        assert(k < Node::getSize(root));
        Ptr v = root;
        while (v != nullptr) {
            const int s = Node::getSize(v->left);
            if (s > k) {
                v = v->left;
            } else if (s == k) {
                return v->value;
            } else {
                v = v->right;
                k -= s + 1;
            }
        }
        return v->value;
    }

    void set(const int k, const T& value)
    {
        const int s = Node::getSize(root);
        assert(0 <= k);
        assert(k < s);
        const PtrPair sr = Node::split(root, k + 1);
        const PtrPair sl = Node::split(sr.first, k);
        const Ptr lr = sl.second;
        lr->value = value;
        root = Node::merge(Node::merge(sl.first, lr), sr.second);

        const PtrPair rev_sr = Node::split(rev_root, s - k);
        const PtrPair rev_sl = Node::split(rev_sr.first, s - k - 1);
        const Ptr rev_lr = rev_sl.second;
        rev_lr->value = value;
        rev_root = Node::merge(Node::merge(rev_sl.first, rev_lr), rev_sr.second);
    }

    T accumulate(const int l, const int r)  // [l,r)
    {
        assert(0 <= l);
        assert(l < r);
        assert(r <= Node::getSize(root));
        const PtrPair sr = Node::split(root, r);
        const PtrPair sl = Node::split(sr.first, l);
        const T ans = Node::getAcc(sl.second);
        root = Node::merge(Node::merge(sl.first, sl.second), sr.second);
        return ans;
    }
    void reverse(const int l, const int r)  // [l,r)
    {
        const int s = Node::getSize(root);
        assert(0 <= l);
        assert(l < r);
        assert(r <= s);
        const int width = r - l;
        if (width > 1) {
            const PtrPair sr = Node::split(root, r);
            const PtrPair sl = Node::split(sr.first, l);

            const PtrPair rev_sr = Node::split(rev_root, s - l);
            const PtrPair rev_sl = Node::split(rev_sr.first, s - r);

            root = Node::merge(Node::merge(sl.first, rev_sl.second), sr.second);
            rev_root = Node::merge(Node::merge(rev_sl.first, sl.second), rev_sr.second);
        }
    }

    void shiftRight(const int l, const int r, const int count)  // [l,r)
    {
        const int s = Node::getSize(root);
        assert(0 <= l);
        assert(l < r);
        assert(r <= s);
        const int width = r - l;
        const int shift = count % width;

        if (shift > 0) {
            const PtrPair sr = Node::split(root, r);
            PtrPair sl = Node::split(sr.first, l);
            const PtrPair sm = Node::split(sl.second, width - shift);

            const PtrPair rev_sr = Node::split(rev_root, s - l);
            PtrPair rev_sl = Node::split(rev_sr.first, s - r);
            const PtrPair rev_sm = Node::split(rev_sl.second, shift);

            root = Node::merge(Node::merge(sl.first, sm.second), Node::merge(sm.first, sr.second));
            rev_root = Node::merge(Node::merge(rev_sl.first, rev_sm.second), Node::merge(rev_sm.first, rev_sr.second));
        }
    }

    void shiftLeft(const int l, const int r, const int count)  // [l,r)
    {
        assert(0 <= l);
        assert(l < r);
        assert(r <= Node::getSize(root));
        const int width = r - l;
        const int shift = count % width;
        if (shift > 0) {
            shiftRight(l, r, width - shift);
        }
    }
};
template <typename T>
typename AccRandomizedBinarySearchTree<T>::Node AccRandomizedBinarySearchTree<T>::pool[AccRandomizedBinarySearchTree::POOL_SIZE];

template <typename T>
ostream& operator<<(ostream& os, const AccRandomizedBinarySearchTree<T>& rbst)
{
    os << "[";
    for (int i = 0; i < rbst.getSize(); i++) {
        os << rbst.get(i) << ",";
    }
    os << "]" << endl;
    return os;
}

struct RBST_Monoid_Min {
    using T = int;
    T operator()(const T& a, const T& b) const { return min(a, b); }
    static constexpr T identity() { return INF<T>; }
};
using RBST = AccRandomizedBinarySearchTree<RBST_Monoid_Min>;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    RBST rbst;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        rbst.insert(i, a);
    }
    for (int q = 0; q < Q; q++) {
        int x, y, z;
        cin >> x >> y >> z;
        if (x == 0) {
            rbst.shiftRight(y, z + 1, 1);
        } else if (x == 1) {
            cout << rbst.accumulate(y, z + 1) << "\n";
        } else {
            rbst.set(y, z);
        }
    }

    return 0;
}



Compiler output:
a.cc:3:19: error: 'numeric_limits' was not declared in this scope; did you mean 'std::numeric_limits'?
    3 | constexpr T INF = numeric_limits<T>::max() / 10;
      |                   ^~~~~~~~~~~~~~
      |                   std::numeric_limits
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:55,
                 from a.cc:1:
/usr/include/c++/14/limits:312:12: note: 'std::numeric_limits' declared here
  312 |     struct numeric_limits : public __numeric_limits_base
      |            ^~~~~~~~~~~~~~
a.cc:3:35: error: expected primary-expression before '>' token
    3 | constexpr T INF = numeric_limits<T>::max() / 10;
      |                                   ^
a.cc:3:38: error: '::max' has not been declared; did you mean 'std::max'?
    3 | constexpr T INF = numeric_limits<T>::max() / 10;
      |                                      ^~~
      |                                      std::max
In file included from /usr/include/c++/14/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: 'std::max' declared here
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
a.cc:15:25: error: 'pair' does not name a type
   15 |         using PtrPair = pair<Ptr, Ptr>;
      |                         ^~~~
a.cc:23:38: error: 'vector' has not been declared
   23 |         static void serialize(Ptr a, vector<T>& v)
      |                                      ^~~~~~
a.cc:23:44: error: expected ',' or '...' before '<' token
   23 |         static void serialize(Ptr a, vector<T>& v)
      |                                            ^
a.cc:91:16: error: 'PtrPair' does not name a type
   91 |         static PtrPair split(Ptr a, const int k)  // size = (k,n-k)
      |                ^~~~~~~
a.cc:112:16: error: 'PtrPair' does not name a type
  112 |         static PtrPair erase(Ptr a, const int k)
      |                ^~~~~~~
a.cc: In static member function 'static void AccRandomizedBinarySearchTree<Monoid>::Node::serialize(Ptr, int)':
a.cc:28:36: error: 'v' was not declared in this scope
   28 |                 serialize(a->left, v);
      |                                    ^
a.cc: In member function 'void AccRandomizedBinarySearchTree<Monoid>::garbage_collect()':
a.cc:138:9: error: 'vector' was not declared in this scope
  138 |         vector<T> v;
      |         ^~~~~~
a.cc:138:9: note: suggested alternatives:
In file included from /usr/include/c++/14/vector:66,
                 from /usr/include/c++/14/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53:
/usr/include/c++/14/bits/stl_vector.h:428:11: note:   'std::vector'
  428 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
/usr/include/c++/14/vector:93:13: note:   'std::pmr::vector'
   93 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
a.cc:138:17: error: expected primary-expression before '>' token
  138 |         vector<T> v;
      |                 ^
a.cc:138:19: error: 'v' was not declared in this scope
  138 |         vector<T> v;
      |                   ^
a.cc: At global scope:
a.cc:295:1: error: 'ostream' does not name a type
  295 | ostream& operator<<(ostream& os, const AccRandomizedBinarySearchTree<T>& rbst)
      | ^~~~~~~
a.cc: In member function 'RBST_Monoid_Min::T RBST_Monoid_Min::operator()(const T&, const T&) const':
a.cc:307:57: error: 'min' was not declared in this scope; did you mean 'std::min'?
  307 |     T operator()(const T& a, const T& b) const { return min(a, b); }
      |                                                         ^~~
      |                                                         std::min
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: 'std::min' declared here
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
a.cc: In function 'int main()':
a.cc:314:5: error: 'cin' was not declared in this scope; did you mean 'std::cin'?
  314 |     cin.tie(0);
      |     ^~~
      |     std::cin
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:146:
/usr/include/c++/14/iostream:62:18: note: 'std::cin' declared here
   62 |   extern istream cin;           ///< Linked to standard input
      |                  ^~~
a.cc:315:5: error: 'ios' has not been declared
  315 |     ios::sync_with_stdio(false);
      |     ^~~
a.cc: In instantiation of 'struct AccRandomizedBinarySearchTree<RBST_Monoid_Min>':
a.cc:318:10:   required from here
  318 |     RBST rbst;
      |          ^~~~
a.cc:121:11: error: no type named 'PtrPair' in 'struct AccRandomizedBinarySearchTree<RBST_Monoid_Min>::Node'
  121 |     using PtrPair = typename Node::PtrPair;
      |           ^~~~~~~
a.cc:330:13: error: 'cout' was not declared in this scope; did you mean 'std::cout'?
  330 |             cout << rbst.accumulate(y, z + 1) << "\n";
      |             ^~~~
      |             std::cout
/usr/include/c++/14/iostream:63:18: note: 'std::cout' declared here
   63 |   extern ostream cout;          ///< Linked to standard output
      |                  ^~~~