非旋 treap 的核心代码：

inline bool my_is_nullptr(void *ptr) { return (long long)ptr <= 0ll; }
template <typename _Tp, typename _UIntType>
class node {
public:
    int size;
    _Tp value, sum, cover, tag;
    bool is_reversed, is_covered;
    _UIntType priority;
    node *left, *right;
    inline node(int s = 0, const _Tp &v = _Tp(), const _Tp& sm = _Tp(), bool rev = false, const _Tp& tg = _Tp(),
        bool cvd = false, const _Tp& cv = _Tp(), const _UIntType &pro = _UIntType(), node *l = nullptr, node *r = nullptr)
		: size(s), value(v), sum(sm), is_covered(cvd), cover(cv), tag(tg), is_reversed(rev), priority(pro), left(l), right(r) {}
    inline ~node() = default;
    inline node<_Tp, _UIntType> &operator=(const node<_Tp, _UIntType> &o) {
        size = o.size;
        value = o.value;
        sum = o.sum;
        is_covered = o.is_covered;
        cover = o.cover;
        is_reversed = o.is_reversed;
        priority = o.priority;
        left = o.left;
        right = o.right;
        return *this;
    }
    inline void pushdown() {
        if (is_reversed) {
            is_reversed = false;
            if (is_covered) goto cover_pushdown;
            std::swap(left, right);
            if (!my_is_nullptr(left)) {
                left = new node<_Tp, _UIntType>(*left);
                left->is_reversed ^= 1;
            }
            if (!my_is_nullptr(right)) {
                right = new node<_Tp, _UIntType>(*right);
                right->is_reversed ^= 1;
            }
        }
        if (tag != _Tp()) {
            if (is_covered) {
                cover += tag;
                tag = _Tp();
                goto cover_pushdown;
            }
            if (!my_is_nullptr(left)) {
                left = new node<_Tp, _UIntType>(*left);
                left->tag += tag, left->value += tag, left->sum += tag * left->size;
            }
            if (!my_is_nullptr(right)) {
                right = new node<_Tp, _UIntType>(*right);
                right->tag += tag, right->value += tag, right->sum += tag * right->size;
            }
            tag = _Tp();
        }
        if (is_covered) {
cover_pushdown:
            if (!my_is_nullptr(left)) {
                left = new node<_Tp, _UIntType>(*left);
                left->is_covered = true;
                left->cover = left->value = cover;
                left->sum = cover * left->size;
            }
            if (!my_is_nullptr(right)) {
                right = new node<_Tp, _UIntType>(*right);
                right->is_covered = true;
                right->cover = right->value = cover;
                right->sum = cover * right->size;
            }
            is_covered = false;
            cover = _Tp();
        }
    }
    inline void update() {
        size = 1;
        sum = value;
        if (!my_is_nullptr(left)) size += left->size, sum = left->sum + sum;
        if (!my_is_nullptr(right)) size += right->size, sum = sum + right->sum;
    }
    template <typename _Ostream>
    friend inline _Ostream& operator<<(_Ostream& os, node<_Tp, _UIntType>* nd) {
    	if (!nd) return os;
        nd->pushdown();
    	os << nd->left;
    	os << nd->value << ' ';
    	os << nd->right;
    	return os;
	}
    static inline void pd(node<_Tp, _UIntType>* nd) {
    	if (my_is_nullptr(nd) || nd->size == 1) return;
        nd->pushdown();
        if (nd == nd->left) abort();
        if (nd == nd->right) abort();
    	pd(nd->left);
    	pd(nd->right);
    	return;
	}
};
template <typename _Tp, typename _Rand, uint32_t _MAXN>
class persistent_segment_nrotate_treap {
    typedef typename _Rand::result_type _UIntType;
    typedef node<_Tp, _UIntType> node_type;
    node_type *_M_root[_MAXN];
    std::greater<_UIntType> priority_comp;
    _Rand rd;
    static inline node_type *q[3000005];
    static inline size_t ppos;
    struct __DFS__ {
	    inline constexpr void dfs(node<_Tp, _UIntType>* cur) const {
			if (my_is_nullptr(cur)) return;
			//cur->pushdown();
			if (cur->left) dfs(q[ppos++] = cur->left);
			if (cur->right) dfs(q[ppos++] = cur->right);
		}
    	inline constexpr __DFS__() {}
	};
	static constexpr __DFS__ dfs_helper{};
#if 1
    static inline void erase_nullptr(node_type *cur) {
        dfs_helper.dfs(cur);
        while (ppos) delete q[--ppos];
    }
#else
    static inline void erase_nullptr(node_type *cur) {}
#endif
    static void split_by_rank(node_type *cur, size_t rk, node_type *&l, node_type *&r);
    template <typename _Priority_comp>
    static node_type *merge(node_type *l, node_type *r, _Priority_comp comp);
    template <typename _Priority_comp>
    static node_type *merge_no_new(node_type *l, node_type *r, _Priority_comp comp);
    template <typename _Priority_comp>
    static node_type* build(_Priority_comp comp, size_t l, size_t r, const _Tp* arr, _Rand& rd) {
        if (l == r) return new node_type(1, arr[l], arr[l], false, _Tp(), false, _Tp(), rd(), nullptr, nullptr);
        size_t mid = (l + r) >> 1;
        return merge_no_new(build(comp, l, mid, arr, rd), build(comp, mid + 1, r, arr, rd), comp);
    }
public:
    inline persistent_segment_nrotate_treap() = default;
    inline ~persistent_segment_nrotate_treap() = default;
    inline void insert(size_t version, size_t pos, const _Tp &v);
    inline void insert(size_t version, size_t pos, node_type * const ptr);
    inline void set(size_t version, size_t pos, const _Tp &v);
    inline void set(size_t version, size_t l, size_t r, const _Tp& v);
    inline void erase(size_t version, size_t pos);
    inline void erase(size_t version, size_t l, size_t r);
    inline void add(size_t version, size_t l, size_t r, const _Tp& v);
    inline void copy(size_t version1, size_t version2, size_t l, size_t r, size_t l_, size_t r_);
    inline _Tp kth(size_t version, size_t index);
    inline node_type* build(size_t l, size_t r, const _Tp* arr) { return build(priority_comp, l, r, arr, rd); }
    inline void build_root(size_t version, size_t l, size_t r, const _Tp* arr) { _M_root[version] = build(priority_comp, l, r, arr, rd); }
    inline int size(size_t version) {
        if (my_is_nullptr(_M_root[version])) return 0;
        _M_root[version]->update();
        return _M_root[version]->size;
    }
    inline _Tp query(size_t version, size_t l, size_t r);
    inline void reverse(size_t version, size_t l, size_t r);
    inline void exchange(size_t version1, size_t version2, size_t l, size_t r, size_t l_, size_t r_);
    inline void copy_from(size_t from, size_t to) { _M_root[to] = _M_root[from]; }
    template <typename _Ostream>
    inline void out(_Ostream& os, size_t version) const { os << _M_root[version]; }
    inline void pushdown(size_t version) const { node_type::pd(_M_root[version]); }
    inline node_type* root(size_t version) {
        _M_root[version]->pushdown();
        _M_root[version]->update();
        return _M_root[version];
    }
};
template <typename _Tp, typename _Rand, uint32_t _MAXN>
template <typename _Priority_comp>
node<_Tp, typename _Rand::result_type> *persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
merge(node<_Tp, typename _Rand::result_type> *l,
      node<_Tp, typename _Rand::result_type> *r,
      _Priority_comp comp) {
    if (my_is_nullptr(l)) return r;
    if (my_is_nullptr(r)) return l;
    l->pushdown();
    r->pushdown();
    if (comp(l->priority, r->priority)) {
        node<_Tp, typename _Rand::result_type>* rt = l;
    	rt->pushdown();
        rt->right = merge(rt->right, r, comp);
        rt->update();
        return rt;
    }
    node<_Tp, typename _Rand::result_type>* rt = r;
    rt->pushdown();
    rt->left = merge(l, rt->left, comp);
    rt->update();
    return rt;
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
template <typename _Priority_comp>
node<_Tp, typename _Rand::result_type> *persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
merge_no_new(node<_Tp, typename _Rand::result_type> *l,
      node<_Tp, typename _Rand::result_type> *r,
      _Priority_comp comp) {
    if (my_is_nullptr(l)) return r;
    if (my_is_nullptr(r)) return l;
    l->pushdown();
    r->pushdown();
    if (comp(l->priority, r->priority)) {
        node<_Tp, typename _Rand::result_type>* rt = l;
    	rt->pushdown();
        rt->right = merge(rt->right, r, comp);
        rt->update();
        return rt;
    }
    node<_Tp, typename _Rand::result_type>* rt = r;
    rt->pushdown();
    rt->left = merge(l, rt->left, comp);
    rt->update();
    return rt;
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
split_by_rank(node<_Tp, typename _Rand::result_type>* cur, size_t rk,
	node<_Tp, typename _Rand::result_type> *&l,
	node<_Tp, typename _Rand::result_type> *&r) {
	if (my_is_nullptr(cur)) {
		l = r = nullptr;
		return;
	}
	cur->pushdown();
	if (rk == 0) {
	    r = new node<_Tp, typename _Rand::result_type>;
	    *r = *cur;
	    l = nullptr;
	    return;
	}
	size_t ls_siz = my_is_nullptr(cur->left) ? 0 : cur->left->size;
	if (rk <= ls_siz) {
		r = new node<_Tp, typename _Rand::result_type>;
		*r = *cur;
		r->pushdown();
		split_by_rank(r->left, rk, l, r->left);
		r->update();
		return;
	}
	l = new node<_Tp, typename _Rand::result_type>;
	*l = *cur;
	l->pushdown();
	split_by_rank(l->right, rk - ls_siz - 1, l->right, r);
	l->update();
	return;
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
insert(size_t version, size_t pos, const _Tp &v) {
    if (my_is_nullptr(_M_root[version])) {
        _M_root[version] = new node<_Tp, typename _Rand::result_type>(1, v, v, false, _Tp(), false, _Tp(), rd(), nullptr, nullptr);
        return;
    }
    node<_Tp, typename _Rand::result_type> *l = nullptr, *r = nullptr;
    split_by_rank(_M_root[version], pos, l, r);
    node<_Tp, typename _Rand::result_type> *tmp = new node<_Tp, typename _Rand::result_type>(1, v, v, false, _Tp(), false, _Tp(), rd(), nullptr, nullptr);
    _M_root[version] = merge(merge(l, tmp, priority_comp), r, priority_comp);
    if (!my_is_nullptr(_M_root[version])) _M_root[version]->update();
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
insert(size_t version, size_t pos, node_type* const ptr) {
    if (my_is_nullptr(_M_root[version])) {
        _M_root[version] = ptr;
        return;
    }
    node<_Tp, typename _Rand::result_type> *l = nullptr, *r = nullptr;
    split_by_rank(_M_root[version], pos, l, r);
    _M_root[version] = merge(merge(l, ptr, priority_comp), r, priority_comp);
    if (!my_is_nullptr(_M_root[version])) _M_root[version]->update();
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
set(size_t version, size_t pos, const _Tp &v) {
    node<_Tp, typename _Rand::result_type> *l = nullptr, *tmp = nullptr, *r = nullptr;
    split_by_rank(_M_root[version], pos, l, r);
    split_by_rank(l, pos - 1, l, tmp);
    if (!my_is_nullptr(tmp)) tmp->value = tmp->sum = v;
    _M_root[version] = merge(merge(l, tmp, priority_comp), r, priority_comp);
    if (!my_is_nullptr(_M_root[version])) _M_root[version]->update();
    return;
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
set(size_t version, size_t il, size_t ir, const _Tp &v) {
    node<_Tp, typename _Rand::result_type> *l = nullptr, *tmp = nullptr, *r = nullptr;
    split_by_rank(_M_root[version], ir, l, r);
    split_by_rank(l, il - 1, l, tmp);
    if (!my_is_nullptr(tmp)) {
        tmp->is_covered = true;
        tmp->cover = tmp->value = v;
        tmp->sum = v * tmp->size;
    }
    _M_root[version] = merge(merge(l, tmp, priority_comp), r, priority_comp);
    if (!my_is_nullptr(_M_root[version])) _M_root[version]->update();
    return;
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
add(size_t version, size_t il, size_t ir, const _Tp &v) {
    node<_Tp, typename _Rand::result_type> *l = nullptr, *tmp = nullptr, *r = nullptr;
    split_by_rank(_M_root[version], ir, l, r);
    split_by_rank(l, il - 1, l, tmp);
    if (!my_is_nullptr(tmp)) {
        if (tmp->is_covered) tmp->cover += v;
        else {
            tmp->tag += v;
            tmp->sum += v * tmp->size;
            tmp->value += v;
        }
        tmp->pushdown();
    }
    _M_root[version] = merge(merge(l, tmp, priority_comp), r, priority_comp);
    if (!my_is_nullptr(_M_root[version])) _M_root[version]->update();
    return;
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
copy(size_t version1, size_t version2, size_t il, size_t ir, size_t il_, size_t ir_) {
    if (il > ir) std::swap(il, ir);
    if (il_ > ir_) std::swap(il_, ir_);
    bool flg = false;
    if (il > il_) {
        std::swap(il, il_);
        std::swap(ir, ir_);
        flg = true;
    }
    node<_Tp, typename _Rand::result_type> *l = nullptr, *lmid = nullptr, *mid = nullptr, *rmid = nullptr, *r = nullptr;
    split_by_rank(_M_root[version1], ir_, rmid, r);
    split_by_rank(rmid, il_ - 1, mid, rmid);
    split_by_rank(mid, ir, lmid, mid);
    split_by_rank(lmid, il - 1, l, lmid);
    if (!flg) {
        if (!my_is_nullptr(rmid)) erase_nullptr(rmid);
        _M_root[version2] = merge(merge(l, lmid, priority_comp), merge(merge(mid, lmid, priority_comp), r, priority_comp), priority_comp);
    }
    else {
        if (!my_is_nullptr(lmid)) erase_nullptr(lmid);
        _M_root[version2] = merge(merge(l, rmid, priority_comp), merge(merge(mid, rmid, priority_comp), r, priority_comp), priority_comp);
    }
    if (!my_is_nullptr(_M_root[version2])) _M_root[version2]->update();
    return;
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
exchange(size_t version1, size_t version2, size_t il, size_t ir, size_t il_, size_t ir_) {
    if (il > ir) std::swap(il, ir);
    if (il_ > ir_) std::swap(il_, ir_);
    if (il > il_) {
        std::swap(il, il_);
        std::swap(ir, ir_);
    }
    node<_Tp, typename _Rand::result_type> *l = nullptr, *lmid = nullptr, *mid = nullptr, *rmid = nullptr, *r = nullptr;
    split_by_rank(_M_root[version1], ir_, rmid, r);
    split_by_rank(rmid, il_ - 1, mid, rmid);
    split_by_rank(mid, ir, lmid, mid);
    split_by_rank(lmid, il - 1, l, lmid);
    _M_root[version2] = merge(merge(l, rmid, priority_comp), merge(merge(mid, lmid, priority_comp), r, priority_comp), priority_comp);
    if (!my_is_nullptr(_M_root[version2])) _M_root[version2]->update();
    return;
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
erase(size_t version, size_t pos) {
    node<_Tp, typename _Rand::result_type> *l = nullptr, *tmp = nullptr, *r = nullptr;
    split_by_rank(_M_root[version], pos, l, r);
    split_by_rank(l, pos - 1, l, tmp);
    if (!my_is_nullptr(tmp)) erase_nullptr(tmp);
    _M_root[version] = merge(l, r, priority_comp);
    if (!my_is_nullptr(_M_root[version])) _M_root[version]->update();
    return;
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
erase(size_t version, size_t il, size_t ir) {
    node<_Tp, typename _Rand::result_type> *l = nullptr, *tmp = nullptr, *r = nullptr;
    split_by_rank(_M_root[version], ir, l, r);
    split_by_rank(l, il - 1, l, tmp);
    if (!my_is_nullptr(tmp)) erase_nullptr(tmp);
    _M_root[version] = merge(l, r, priority_comp);
    if (!my_is_nullptr(_M_root[version])) _M_root[version]->update();
    return;
}
template <typename _Tp, typename _UIntType>
_Tp kth(node<_Tp, _UIntType>* cur, int index) {
    if (my_is_nullptr(cur)) return _Tp();
    int left_siz = (my_is_nullptr(cur->left) ? 0 : cur->left->size);
    if (index <= left_siz) return kth(cur->left, index);
    if (index <= left_siz + 1) return cur->value;
    return kth(cur->right, index - left_siz - 1);
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline _Tp persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
kth(size_t version, size_t index) { return ::kth(_M_root[version], index); }
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline _Tp persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
query(size_t version, size_t il, size_t ir) {
    node<_Tp, typename _Rand::result_type> *l = nullptr, *tmp = nullptr, *r = nullptr;
    split_by_rank(_M_root[version], ir, l, r);
    split_by_rank(l, il - 1, l, tmp);
    _Tp ans = 0;
    if (!my_is_nullptr(tmp)) ans = tmp->sum;
    _M_root[version] = merge(merge(l, tmp, priority_comp), r, priority_comp);
    return ans;
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
reverse(size_t version, size_t il, size_t ir) {
    node<_Tp, typename _Rand::result_type> *l = nullptr, *tmp = nullptr, *r = nullptr;
    split_by_rank(_M_root[version], ir, l, r);
    split_by_rank(l, il - 1, l, tmp);
    if (!my_is_nullptr(tmp)) tmp->is_reversed ^= 1;
    _M_root[version] = merge(merge(l, tmp, priority_comp), r, priority_comp);
}
struct my_rand {
    typedef unsigned int result_type;
    unsigned int _M_seed;
    inline unsigned int u32_hasher(unsigned int x) {
        float tmp = x;
        return *(unsigned int*)&tmp;
    }
    inline unsigned int operator()() { return _M_seed += u32_hasher(_M_seed); }
    inline my_rand(unsigned int sd = 5489u) : _M_seed(sd) {}
};
persistent_segment_nrotate_treap<mint, my_rand, 300005> tree;
int main() {
    int n = 0, q = 0;
    cin >> n >> q;
    int lastans = 0;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    tree.build_root(0, 1, n, arr);
    int op, l, r, l_, r_;
    mint value;
    for (int i = 1; i <= q; i++) {
        cin >> op >> l >> r;
        switch (op) {
            case 1: {
                tree.copy_from(i - 1, i);
                lastans = tree.query(i, l, r).val();
                cout << lastans << '\n';
                break;
            }
            case 2: {
                tree.copy_from(i - 1, i);
                cin >> value;
                tree.set(i, l, r, value);
                break;
            }
            case 3: {
                tree.copy_from(i - 1, i);
                cin >> value;
                tree.add(i, l, r, value);
                break;
            }
            case 4: {
                cin >> l_ >> r_;
                tree.copy(i - 1, i, l, r, l_, r_);
                break;
            }
            case 5: {
                cin >> l_ >> r_;
                tree.exchange(i - 1, i, l, r, l_, r_);
                break;
            }
            case 6: {
                tree.copy_from(i - 1, i);
                tree.reverse(i, l, r);
                break;
            }
        }
    }
    tree.out(cout, q);
}

总是在 copy 操作时出现无限递归。