```cpp
// luogu-judger-enable-o2
#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string.h>
#include <type_traits>
#include <unordered_map>
#include <cstdint>
#include <utility>
#if defined(_MSC_VER)
#define __LANG__ _MSVC_LANG
#elif defined(__cplusplus)
#define __LANG__ __cplusplus
#else
#define __LANG__ 0L
#endif
#if __LANG__ < 201703L
#error This file requires compiler and library support for the ISO C++ 2017 standard. \
This support must be enabled with the -std=c++17 or -std=gnu++17 compiler options.
#endif
namespace OY {
#define cin OY::inputHelper<1 << 20, 20>::getInstance()
#define getchar() ({char c=cin.getChar_Checked();cin.next();c; })
#define cout OY::outputHelper<1 << 20>::getInstance()
#define putchar cout.putChar
#define endl '\n'
#define putlog(...) OY::printLog(", ", __VA_ARGS__)
template <uint64_t _BufferSize = 1 << 20, uint64_t _BlockSize = 20>
class inputHelper {
public:
FILE *m_filePtr;
char m_buf[_BufferSize], *m_end, *m_cursor;
bool m_ok;
void flush() {
uint64_t a = m_end - m_cursor;
if (a >= _BlockSize) return;
memmove(m_buf, m_cursor, a);
uint64_t b = fread(m_buf + a, 1, _BufferSize - a, m_filePtr);
m_cursor = m_buf;
if (a + b < _BufferSize) {
m_end = m_buf + a + b;
*m_end = EOF;
}
}
public:
explicit inputHelper(const char *inputFileName) : m_ok(true) {
if (!*inputFileName) m_filePtr = stdin;
else m_filePtr = fopen(inputFileName, "rt");
m_end = m_cursor = m_buf + _BufferSize;
}
~inputHelper() { fclose(m_filePtr); }
static inputHelper<_BufferSize, _BlockSize> &getInstance() {
static inputHelper<_BufferSize, _BlockSize> s_obj("");
return s_obj;
}
static constexpr bool isBlank(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }
static constexpr bool isEndline(char c) { return c == '\n' || c == EOF; }
const char &getChar_Checked() {
if (m_cursor < m_end) return *m_cursor;
uint64_t b = fread(m_buf, 1, _BufferSize, m_filePtr);
m_cursor = m_buf;
if (b < _BufferSize) {
m_end = m_buf + b;
*m_end = EOF;
}
return *m_cursor;
}
const char &getChar_Unchecked() const { return *m_cursor; }
void next() { ++m_cursor; }
void setState(bool _ok) { m_ok = _ok; }
template <typename _Tp, typename std::enable_if<std::is_signed<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
while (isBlank(getChar_Checked())) next();
flush();
if (getChar_Unchecked() == '-') {
next();
if (isdigit(getChar_Unchecked())) {
ret = -(getChar_Unchecked() - '0');
while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 - (getChar_Unchecked() - '0');
}
else m_ok = false;
}
else {
if (isdigit(getChar_Unchecked())) {
ret = getChar_Unchecked() - '0';
while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
}
else m_ok = false;
}
return *this;
}
template <typename _Tp, typename std::enable_if<std::is_unsigned<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
while (isBlank(getChar_Checked())) next();
flush();
if (isdigit(getChar_Unchecked())) {
ret = getChar_Unchecked() - '0';
while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
}
else m_ok = false;
return *this;
}
template <typename _Tp, typename std::enable_if<std::is_floating_point<_Tp>::value>::type * = nullptr>
inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
bool neg = false, integer = false, decimal = false;
while (isBlank(getChar_Checked())) next();
flush();
if (getChar_Unchecked() == '-') {
neg = true;
next();
}
if (!isdigit(getChar_Unchecked()) && getChar_Unchecked() != '.') {
m_ok = false;
return *this;
}
if (isdigit(getChar_Unchecked())) {
integer = true;
ret = getChar_Unchecked() - '0';
while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
}
if (getChar_Unchecked() == '.') {
next();
if (isdigit(getChar_Unchecked())) {
if (!integer) ret = 0;
decimal = true;
_Tp unit = 0.1;
ret += unit * (getChar_Unchecked() - '0');
while (next(), isdigit(getChar_Unchecked())) {
unit *= 0.1;
ret += unit * (getChar_Unchecked() - '0');
}
}
}
if (!integer && !decimal) m_ok = false;
else if (neg) ret = -ret;
return *this;
}
inputHelper<_BufferSize, _BlockSize> &operator>>(char &ret) {
while (isBlank(getChar_Checked())) next();
ret = getChar_Checked();
if (ret == EOF) m_ok = false;
else next();
return *this;
}
inputHelper<_BufferSize, _BlockSize> &operator>>(std::string &ret) {
while (isBlank(getChar_Checked())) next();
if (getChar_Checked() != EOF) {
ret.clear();
do {
ret += getChar_Checked();
next();
} while (!isBlank(getChar_Checked()) && getChar_Unchecked() != EOF);
}
else m_ok = false;
return *this;
}
explicit operator bool() { return m_ok; }
};
template <uint64_t _BufferSize = 1 << 20>
class outputHelper {
FILE *m_filePtr = nullptr;
char m_buf[_BufferSize], *m_end, *m_cursor;
char m_tempBuf[50], *m_tempBufCursor, *m_tempBufDot;
uint64_t m_floatReserve, m_floatRatio;
public:
outputHelper(const char *outputFileName, int prec = 6) : m_end(m_buf + _BufferSize) {
if (!*outputFileName) m_filePtr = stdout;
else m_filePtr = fopen(outputFileName, "wt");
m_cursor = m_buf;
m_tempBufCursor = m_tempBuf;
precision(prec);
}
static outputHelper<_BufferSize> &getInstance() {
static outputHelper<_BufferSize> s_obj("");
return s_obj;
}
~outputHelper() {
flush();
fclose(m_filePtr);
}
void precision(int prec) {
m_floatReserve = prec;
m_floatRatio = pow(10, prec);
m_tempBufDot = m_tempBuf + prec;
}
outputHelper<_BufferSize> &flush() {
fwrite(m_buf, 1, m_cursor - m_buf, m_filePtr);
fflush(m_filePtr);
m_cursor = m_buf;
return *this;
}
void putChar(const char &c) {
if (m_cursor == m_end) flush();
*m_cursor++ = c;
}
void putS(const char *c) { while (*c) putChar(*c++); }
template <typename _Tp, typename std::enable_if<std::is_signed<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
_Tp _ret = _Tp(ret);
if (_ret >= 0) {
do {
*m_tempBufCursor++ = '0' + _ret % 10;
_ret /= 10;
} while (_ret);
do putChar(*--m_tempBufCursor);
while (m_tempBufCursor > m_tempBuf);
}
else {
putChar('-');
do {
*m_tempBufCursor++ = '0' - _ret % 10;
_ret /= 10;
} while (_ret);
do putChar(*--m_tempBufCursor);
while (m_tempBufCursor > m_tempBuf);
}
return *this;
}
template <typename _Tp, typename std::enable_if<std::is_unsigned<_Tp>::value &std::is_integral<_Tp>::value>::type * = nullptr>
outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
_Tp _ret = _Tp(ret);
do {
*m_tempBufCursor++ = '0' + _ret % 10;
_ret /= 10;
} while (_ret);
do putChar(*--m_tempBufCursor);
while (m_tempBufCursor > m_tempBuf);
return *this;
}
template <typename _Tp, typename std::enable_if<std::is_floating_point<_Tp>::value>::type * = nullptr>
outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
if (ret < 0) {
putChar('-');
return *this << -ret;
}
_Tp _ret = ret * m_floatRatio;
uint64_t integer = _ret;
if (_ret - integer >= 0.4999999999) integer++;
do {
*m_tempBufCursor++ = '0' + integer % 10;
integer /= 10;
} while (integer);
if (m_tempBufCursor > m_tempBufDot) {
do putChar(*--m_tempBufCursor);
while (m_tempBufCursor > m_tempBufDot);
putChar('.');
}
else {
putS("0.");
for (int i = m_tempBufDot - m_tempBufCursor; i--;) putChar('0');
}
do putChar(*--m_tempBufCursor);
while (m_tempBufCursor > m_tempBuf);
return *this;
}
outputHelper<_BufferSize> &operator<<(const char &ret) {
putChar(ret);
return *this;
}
outputHelper<_BufferSize> &operator<<(const std::string &ret) {
putS(ret.data());
return *this;
}
};
template <uint64_t _BufferSize, uint64_t _BlockSize>
inputHelper<_BufferSize, _BlockSize> &getline(inputHelper<_BufferSize, _BlockSize> &ih, std::string &ret) {
ret.clear();
if (ih.getChar_Checked() == EOF) ih.setState(false);
else {
while (!inputHelper<_BufferSize, _BlockSize>::isEndline(ih.getChar_Checked())) {
ret += ih.getChar_Unchecked();
ih.next();
}
ih.next();
}
return ih;
}
template <typename D, typename T, typename... S>
void printLog(D delim, const T &x, S... rest) {
cout << x;
if (sizeof...(rest) > 0) {
cout << delim;
printLog(delim, rest...);
}
}
}
using OY::getline;
namespace OY {
template <typename _ModType, _ModType _P>
struct Modular {
static constexpr _ModType mod() { return _P; }
static constexpr _ModType mod(uint64_t __a) { return __a % _P; }
static constexpr _ModType plus(_ModType __a, _ModType __b) {
if (__a += __b; __a >= _P) __a -= _P;
return __a;
}
static constexpr _ModType minus(_ModType __a, _ModType __b) {
if (__a += _P - __b; __a >= _P) __a -= _P;
return __a;
}
static constexpr _ModType multiply(uint64_t __a, uint64_t __b) {
if constexpr (std::is_same<_ModType, uint64_t>::value) return multiply_ld(__a, __b);
else return multiply_64(__a, __b);
}
static constexpr _ModType multiply_64(uint64_t __a, uint64_t __b) { return mod(__a * __b); }
static constexpr _ModType multiply_128(uint64_t __a, uint64_t __b) { return __uint128_t(__a) * __b % _P; }
static constexpr _ModType multiply_ld(uint64_t __a, uint64_t __b) {
if (std::__countl_zero(__a) + std::__countl_zero(__b) >= 64) return multiply_64(__a, __b);
int64_t res = __a * __b - uint64_t(1.L / _P * __a * __b) * _P;
if (res < 0) res += _P;
else if (res >= _P) res -= _P;
return res;
}
static constexpr _ModType pow(uint64_t __a, uint64_t __n) {
if constexpr (std::is_same<_ModType, uint64_t>::value) return pow_ld(__a, __n);
else return pow_64(__a, __n);
}
static constexpr _ModType pow_64(uint64_t __a, uint64_t __n) {
_ModType res = 1, b = mod(__a);
while (__n) {
if (__n & 1) res = multiply_64(res, b);
b = multiply_64(b, b);
__n >>= 1;
}
return res;
}
static constexpr _ModType pow_128(uint64_t __a, uint64_t __n) {
_ModType res = 1, b = mod(__a);
while (__n) {
if (__n & 1) res = multiply_128(res, b);
b = multiply_128(b, b);
__n >>= 1;
}
return res;
}
static constexpr _ModType pow_ld(uint64_t __a, uint64_t __n) {
_ModType res = 1, b = mod(__a);
while (__n) {
if (__n & 1) res = multiply_ld(res, b);
b = multiply_ld(b, b);
__n >>= 1;
}
return res;
}
template <typename _Tp>
static constexpr _Tp divide(_Tp __a) { return __a / _P; }
template <typename _Tp>
static constexpr std::pair<_Tp, _Tp> divmod(_Tp __a) {
_Tp quo = __a / _P, rem = __a - quo * _P;
return {quo, rem};
}
};
template <uint32_t _P>
using Modular32 = Modular<uint32_t, _P>;
template <uint64_t _P>
using Modular64 = Modular<uint64_t, _P>;
}
namespace OY {
template <typename _ModType, _ModType _P, bool _IsPrime = false>
struct StaticModInt {
using mint = StaticModInt<_ModType, _P, _IsPrime>;
_ModType m_val;
static_assert(_P > 1 && _P < 1ull << 63);
constexpr StaticModInt() : m_val(0) {}
template <typename _Tp, typename std::enable_if<std::is_signed<_Tp>::value, bool>::type = true>
constexpr StaticModInt(_Tp __val) : m_val(0) {
int64_t x = int64_t(__val) % int64_t(mod());
if (x < 0) x += mod();
m_val = x;
}
template <typename _Tp, typename std::enable_if<std::is_unsigned<_Tp>::value, bool>::type = true>
constexpr StaticModInt(_Tp __val) : m_val(__val % mod()) {}
static constexpr mint raw(_ModType __val) {
mint res;
res.m_val = __val;
return res;
}
static constexpr _ModType mod() { return _P; }
constexpr _ModType val() const { return m_val; }
constexpr mint pow(uint64_t __n) const { return Modular<_ModType, _P>::pow(m_val, __n); }
constexpr mint inv() const {
if constexpr (_IsPrime) return inv_Fermat();
else return inv_exgcd();
}
constexpr mint inv_exgcd() const {
_ModType x = mod(), y = m_val, m0 = 0, m1 = 1;
while (y) {
_ModType z = x / y;
x -= y * z;
m0 -= m1 * z;
std::swap(x, y);
std::swap(m0, m1);
}
if (m0 >= mod()) m0 += mod() / x;
return raw(m0);
}
constexpr mint inv_Fermat() const { return pow(mod() - 2); }
constexpr mint &operator++() {
if (++m_val == mod()) m_val = 0;
return *this;
}
constexpr mint &operator--() {
if (m_val == 0) m_val = mod();
m_val--;
return *this;
}
constexpr mint operator++(int) {
mint old(*this);
++*this;
return old;
}
constexpr mint operator--(int) {
mint old(*this);
--*this;
return old;
}
constexpr mint &operator+=(const mint &__other) {
m_val = Modular<_ModType, _P>::plus(m_val, __other.m_val);
return *this;
}
constexpr mint &operator-=(const mint &__other) {
m_val = Modular<_ModType, _P>::minus(m_val, __other.m_val);
return *this;
}
constexpr mint &operator*=(const mint &__other) {
m_val = Modular<_ModType, _P>::multiply(m_val, __other.m_val);
return *this;
}
constexpr mint &operator/=(const mint &__other) { return *this *= __other.inv(); }
constexpr mint operator+() const { return *this; }
constexpr mint operator-() const { return raw(m_val ? mod() - m_val : 0); }
constexpr bool operator==(const mint &__other) const { return m_val == __other.m_val; }
constexpr bool operator!=(const mint &__other) const { return m_val != __other.m_val; }
constexpr bool operator<(const mint &__other) const { return m_val < __other.m_val; }
constexpr bool operator>(const mint &__other) const { return m_val > __other.m_val; }
constexpr bool operator<=(const mint &__other) const { return m_val <= __other.m_val; }
constexpr bool operator>=(const mint &__other) const { return m_val <= __other.m_val; }
template <typename _Tp>
constexpr explicit operator _Tp() const { return _Tp(m_val); }
constexpr friend mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
constexpr friend mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
constexpr friend mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
constexpr friend mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }
template <typename _Istream>
friend _Istream &operator>>(_Istream &is, mint &self) { return is >> self.m_val; }
template <typename _Ostream>
friend _Ostream &operator<<(_Ostream &os, const mint &self) { return os << self.m_val; }
};
template <uint32_t _P, bool _IsPrime>
using StaticModInt32 = StaticModInt<uint32_t, _P, _IsPrime>;
template <uint64_t _P, bool _IsPrime>
using StaticModInt64 = StaticModInt<uint64_t, _P, _IsPrime>;
}
using mint = OY::StaticModInt32<1000000007, true>;
inline bool my_is_nullptr(void *ptr) { return (long long)ptr <= 0ll; }
template <typename _Tp, typename _UIntType>
class node {
public:
size_t size;
_Tp value, sum, cover, tag;
bool is_reversed, is_covered;
_UIntType priority;
node *left, *right;
inline node(size_t 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), cover(cv), tag(tg), is_reversed(rev), is_covered(cvd), 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 node(const node<_Tp, _UIntType>&) = default;
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 (!nd || !nd->tag) return;
nd->pushdown();
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{};
static inline void erase_nullptr(node_type *cur) {
dfs_helper.dfs(cur);
while (ppos) delete q[--ppos];
}
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* 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(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 reverse(size_t version1, size_t version2, 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_type *l, node_type *r, _Priority_comp comp) {
if (my_is_nullptr(l)) return r;
if (my_is_nullptr(r)) return l;
if (comp(l->priority, r->priority)) {
node_type* rt = l;
rt->pushdown();
rt->right = merge(rt->right, r, comp);
rt->update();
return rt;
}
node_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_type* cur, size_t rk, node_type *&l, node_type *&r) {
if (my_is_nullptr(cur)) {
l = r = nullptr;
return;
}
cur->pushdown();
size_t ls_siz = my_is_nullptr(cur->left) ? 0 : cur->left->size;
if (rk <= ls_siz) {
r = new node_type;
*r = *cur;
r->pushdown();
split_by_rank(r->left, rk, l, r->left);
r->update();
return;
}
l = new node_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_type(1, v, v, false, _Tp(), false, _Tp(), rd(), nullptr, nullptr);
return;
}
node_type *l = nullptr, *r = nullptr;
split_by_rank(_M_root[version], pos, l, r);
node_type *tmp = new node_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_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_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_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_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->pushdown();
if (tmp->is_covered) tmp->cover += v;
else {
tmp->tag += v;
tmp->sum += v * tmp->size;
tmp->value += 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>::
copy(size_t version1, size_t version2, size_t il, size_t ir, size_t il_, size_t ir_) {
bool flg = false;
if (il > il_) {
std::swap(il, il_);
std::swap(ir, ir_);
flg = true;
}
node_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) _M_root[version2] = merge(merge(l, rmid, priority_comp), merge(merge(mid, rmid, priority_comp), r, priority_comp), priority_comp);
else _M_root[version2] = merge(merge(l, lmid, 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>::
exchange(size_t version1, size_t version2, size_t il, size_t ir, size_t il_, size_t ir_) {
if (il > il_) {
std::swap(il, il_);
std::swap(ir, ir_);
}
node_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_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_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_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{};
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_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);
}
template <typename _Tp, typename _Rand, uint32_t _MAXN>
inline void persistent_segment_nrotate_treap<_Tp, _Rand, _MAXN>::
reverse(size_t version1, size_t version2, size_t il, size_t ir) {
node_type *l = nullptr, *tmp = nullptr, *r = nullptr;
split_by_rank(_M_root[version1], ir, l, r);
split_by_rank(l, il - 1, l, tmp);
if (!my_is_nullptr(tmp)) tmp->is_reversed ^= 1;
_M_root[version2] = 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, 1048576> tree;
mint arr[20000005];
int main() {
int n, q;
cin >> n >> q;
uint32_t 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.reverse(i - 1, i, l, r);
break;
}
}
tree.pushdown(i);
}
tree.out(cout, q);
}
```
by Ruiqun2009 @ 2023-03-31 23:31:39