Description
Hint
- (1le n,qle 3 imes 10^5)
- (0le a_i, kle 10^9)
- 对于 (4,5) 操作，保证 (r_1-l_1=r_2-l_2) 且 ([l_1,r_1]cap[l_2, r_2] = varnothing)
- 数据不保证随机。
Solution
ODT 被卡了，于是考虑使用平衡树（FHQ-Treap）。
区间求和
在结点中维护一个 sum 字段，表示子树的数值之和。
区间赋值
在结点中维护一个标记 cov，如果等于 (-1) 则没有。
区间加法
在结点中维护一个标记 add，如果等于 (0) 则没有。
区间反转
同样用一个标记 rev 表示。
区间交换
将整个数列截成 ([1, l_1),[l_1,r_1],(r_1,l_2),[l_2,r_2],(r_2,n]) 五段，再把第二段，第四段交换，依次重新合并即可。
区间复制
难点。如果是朴素的 FHQ-Treap 进行复制，那么区间一大直接爆炸。
索性直接 可持久化，复制对应区间的根结点然后接上，原来的直接 throw away。
注意到空间上的问题，处理地不恰当可能会导致 MLE，于是当节点数大于某一个定值时就将当前树重构，然后把无效结点丢弃。
然后就是卡卡常就过了。细节比较多，写了一个上午。
Code
不保证这份代码的每次提交都是 AC 的。
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : Luogu P5586 序列 (加强版)
*/
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long llint;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
namespace fastIO_int{
inline int get_int()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
x=x*10+c-'0',c=getchar();
return f*x;
}
void put_int(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)put_int(x/10);
putchar(x%10+'0');
}
};
struct Node {
int lc, rc, size;
int sum, val, add, cov;
bool rev;
} t[N << 7];
int total, root;
#define lc(x) t[x].lc
#define rc(x) t[x].rc
#define size(x) t[x].size
#define sum(x) t[x].sum
#define val(x) t[x].val
#define add(x) t[x].add
#define rev(x) t[x].rev
#define cov(x) t[x].cov
inline int create(int v) {
int x = ++total;
size(x) = 1, val(x) = sum(x) = v;
rev(x) = false, cov(x) = -1, add(x) = 0;
lc(x) = rc(x) = 0;
return x;
}
inline int copy(int x) {
int y = ++total;
t[y] = t[x];
return y;
}
inline void pushup(int x) {
size(x) = size(lc(x)) + size(rc(x)) + 1;
sum(x) = ((sum(lc(x)) + sum(rc(x))) % mod + val(x)) % mod;
}
inline void setRev(int x) {
swap(lc(x), rc(x)), rev(x) ^= 1;
}
inline void setAdd(int x, int v) {
sum(x) = (sum(x) + (llint)size(x) * v) % mod;
(val(x) += v) %= mod, (add(x) += v) %= mod;
}
inline void setCov(int x, int v) {
sum(x) = (llint)size(x) * v % mod;
val(x) = cov(x) = v, add(x) = 0;
}
inline void pushdown(int x) {
if (cov(x) != -1 || rev(x) || add(x)) {
if (lc(x)) lc(x) = copy(lc(x));
if (rc(x)) rc(x) = copy(rc(x));
}
if (cov(x) != -1) {
if (lc(x)) setCov(lc(x), cov(x));
if (rc(x)) setCov(rc(x), cov(x));
cov(x) = -1;
}
if (add(x)) {
if (lc(x)) setAdd(lc(x), add(x));
if (rc(x)) setAdd(rc(x), add(x));
add(x) = 0;
}
if (rev(x)) {
if (lc(x)) setRev(lc(x));
if (rc(x)) setRev(rc(x));
rev(x) = 0;
}
}
int merge(int u, int v) {
if (!u || !v) return u | v;
if (rand() % (size(u) + size(v)) < size(u)) {
pushdown(u), u = copy(u);
rc(u) = merge(rc(u), v);
return pushup(u), u;
} else {
pushdown(v), v = copy(v);
lc(v) = merge(u, lc(v));
return pushup(v), v;
}
}
void split(int x, int k, int& u, int& v) {
if (!x) return u = v = 0, void();
pushdown(x);
if (size(lc(x)) < k) {
u = copy(x);
split(rc(u), k - size(lc(x)) - 1, rc(u), v);
pushup(u);
} else {
v = copy(x);
split(lc(v), k, u, lc(v));
pushup(v);
}
}
inline void reverse(int l, int r) {
int pl, pm, pr;
split(root, r, pl, pr);
split(pl, l - 1, pl, pm);
setRev(pm = copy(pm));
root = merge(pl, merge(pm, pr));
}
inline void assign(int l, int r, int v) {
int pl, pm, pr;
split(root,r, pl, pr);
split(pl, l - 1, pl, pm);
setCov(pm = copy(pm), v);
root = merge(pl, merge(pm, pr));
}
inline void increase(int l, int r, int v) {
int pl, pm, pr;
split(root,r, pl, pr);
split(pl, l - 1, pl, pm);
setAdd(pm = copy(pm), v);
root = merge(pl, merge(pm, pr));
}
inline int getSum(int l, int r) {
int pl, pm, pr;
split(root,r, pl, pr);
split(pl, l - 1, pl, pm);
int ret = sum(pm);
root = merge(pl, merge(pm, pr));
return ret;
}
inline void swap(int l1, int r1, int l2, int r2) {
int pl, px, pm, py, pr;
if (l1 > l2) swap(l1, l2), swap(r1, r2);
split(root, r2, pl, pr);
split(pl, l2 - 1, pl, py);
split(pl, r1, pl, pm);
split(pl, l1 - 1, pl, px);
pl = merge(pl, py), pr = merge(px, pr);
root = merge(pl, merge(pm, pr));
}
inline void paste(int l1, int r1, int l2, int r2) {
bool f = 0; int pl, px, pm, py, pr;
if (l1 > l2) swap(l1, l2), swap(r1, r2), f = 1;
split(root, r2, pl, pr);
split(pl, l2 - 1, pl, py);
split(pl, r1, pl, pm);
split(pl, l1 - 1, pl, px);
f ? px = copy(py) : py = copy(px);
pl = merge(pl, px), pr = merge(py, pr);
root = merge(pl, merge(pm, pr));
}
int build(int l, int r, int* a) {
if (l > r) return 0;
int mid = (l + r) >> 1, x = create(a[mid]);
lc(x) = build(l, mid - 1, a), rc(x) = build(mid + 1, r, a);
return pushup(x), x;
}
void scan(int x, int* a, int& p) {
if (!x) return;
pushdown(x);
scan(lc(x), a, p);
a[++p] = val(x);
scan(rc(x), a, p);
}
int a[N], n, q;
void rebuild() {
scan(root, a, n = 0);
total = 0;
root = build(1, n, a);
}
signed main() {
srand(465125);
using fastIO_int::get_int;
using fastIO_int::put_int;
n = get_int(), q = get_int();
for (register int i = 1; i <= n; i++)
a[i] = get_int();
root = build(1, n, a);
for (int last = 0; q; --q) {
int cmd, v, l1, r1, l2, r2;
cmd = get_int(), l1 = get_int() ^ last, r1 = get_int() ^ last;
switch (cmd) {
case 1 : put_int(last = getSum(l1, r1)), putchar('
'); break;
case 2 : v = get_int() ^ last, assign(l1, r1, v); break;
case 3 : v = get_int() ^ last, increase(l1, r1, v); break;
case 4 : l2 = get_int() ^ last, r2 = get_int() ^ last, paste(l1, r1, l2, r2); break;
case 5 : l2 = get_int() ^ last, r2 = get_int() ^ last, swap(l1, r1, l2, r2); break;
case 6 : reverse(l1, r1); break;
}
if (total > 7500000) rebuild();
}
scan(root, a, n = 0);
for (register int i = 1; i <= n; i++)
put_int(a[i]), putchar(' ');
return putchar('
'), 0;
}