P5586 [P5350] 序列 (加强版) 题解
Mooncrying · · 题解
个人感觉本题和这题给我的感觉差不多（都很恶心）。
由于复制操作的存在，我们需要使用可持久化文艺平衡树（我用的 FHQ_Treap，主要是好写）。
然后就是根据每个操作要求给出操作就好。
逻辑什么的都是相当简单的，就是码量大了些。
把弱化版的代码拿过来加个强制在线直接就能过。
注意可持久化的写法：split，merge 和 Copy 都需要复制。
其次就是 pushdown 的写法，注意判断是否存在左右孩子，然后如果上面那个题的 pushdown 你会写了这个就没问题了。
然后笔者就没遇到什么问题了。
贴个代码：
#include<bits/stdc++.h>
using namespace std;
#define l(x) t[x].ls
#define r(x) t[x].rs
#define p 1000000007
const int M = 3e6 + 6e5 + 5;
const int N = 3e5 + 5;
int root, cnt, m, n, a[N], top, last;
struct FHQ_Treap
{
int sum, val, size, ls, rs, cov, add, rev, key;
}t[M];
template <typename T> void read(T &x)
{
T f = 1; x = 0; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
x *= f;
}
template <typename T> void write(T x, char ch)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10, 0); putchar(x % 10 + '0');
if(ch == ' ') putchar(' '); if(ch == '\n') putchar('\n');
}
int add(int a, int b) { return a + b >= p ? a + b - p : a + b; }
int clone(int now) { return t[++cnt] = t[now], cnt; }
void update(int x)
{
t[x].size = t[l(x)].size + t[r(x)].size + 1;
t[x].sum = add(add(t[l(x)].sum, t[r(x)].sum), t[x].val);
}
void Rev(int now)
{
swap(l(now), r(now));
t[now].rev ^= 1;
}
void Add(int now, int k)
{
t[now].val = add(t[now].val, k);
t[now].add = add(t[now].add, k);
t[now].sum = (t[now].sum + 1ll * t[now].size * k) % p;
}
void Cov(int now, int k)
{
t[now].add = 0;
t[now].val = t[now].cov = k;
t[now].sum = 1ll * t[now].size * k % p;
}
void pushdown(int now)
{
if(t[now].add || t[now].cov != -1 || t[now].rev)
{
if(l(now)) l(now) = clone(l(now));
if(r(now)) r(now) = clone(r(now));
}
if(t[now].cov != -1)
{
if(l(now)) Cov(l(now), t[now].cov);
if(r(now)) Cov(r(now), t[now].cov);
t[now].cov = -1;
}
if(t[now].add)
{
if(l(now)) Add(l(now), t[now].add);
if(r(now)) Add(r(now), t[now].add);
t[now].add = 0;
}
if(t[now].rev)
{
if(l(now)) Rev(l(now));
if(r(now)) Rev(r(now));
t[now].rev = 0;
}
}
void split(int now, int size, int &x, int &y)
{
if(!now) return x = y = 0, void();
pushdown(now);
if(t[l(now)].size < size)
x = clone(now), split(r(x), size - t[l(x)].size - 1, r(x), y), update(x);
else y = clone(now), split(l(y), size, x, l(y)), update(y);
}
int merge(int x, int y)
{
if(!x || !y) return x | y;
if(t[x].key > t[y].key)
return x = clone(x), pushdown(x), r(x) = merge(r(x), y), update(x), x;
else return y = clone(y), pushdown(y), l(y) = merge(x, l(y)), update(y), y;
}
int addnode(int val)
{
t[++cnt].cov = -1;
t[cnt].val = t[cnt].sum = val;
l(cnt) = r(cnt) = t[cnt].add = t[cnt].rev = 0;
t[cnt].key = rand();
t[cnt].size = 1;
return cnt;
}
int build(int l, int r)
{
int mid = l + r >> 1;
int now = addnode(a[mid]);
if(l > r) return 0;
l(now) = build(l, mid - 1); r(now) = build(mid + 1, r);
return update(now), now;
}
int Query(int l, int r)
{
int x, y, z, ans;
split(root, r, x, z);
split(x, l - 1, x, y);
return ans = t[y].sum, root = merge(merge(x, y), z), ans;
}
void Cover(int l, int r, int k)
{
int x, y, z;
split(root, r, x, z);
split(x, l - 1, x, y);
Cov(y, k); root = merge(merge(x, y), z);
}
void Change(int l, int r, int k)
{
int x, y, z;
split(root, r, x, z);
split(x, l - 1, x, y);
Add(y, k); root = merge(merge(x, y), z);
}
void Reverse(int l, int r)
{
int x, y, z;
split(root, r, x, z);
split(x, l - 1, x, y);
Rev(y); root = merge(merge(x, y), z);
}
void Copy(int l1, int r1, int l2, int r2)
{
int a, b, c, d, e; bool f = 0;
if(l1 > l2) swap(l1, l2), swap(r1, r2), f = 1;
split(root, r2, a, e);
split(a, l2 - 1, a, d);
split(a, r1, a, c);
split(a, l1 - 1, a, b);
if(!f) d = clone(b); else b = clone(d);
root = merge(merge(merge(merge(a, b), c), d), e);
}
void Swap(int l1, int r1, int l2, int r2)
{
int a, b, c, d, e;
if(l1 > l2) swap(l1, l2), swap(r1, r2);
split(root, r2, a, e);
split(a, l2 - 1, a, d);
split(a, r1, a, c);
split(a, l1 - 1, a, b);
root = merge(merge(merge(merge(a, d), c), b), e);
}
void ldr(int now)
{
pushdown(now);
if(l(now)) ldr(l(now));
a[++top] = t[now].val;
if(r(now)) ldr(r(now));
}
int main()
{
srand((unsigned)time(0)); srand(rand());
read(n); read(m);
for(int i = 1; i <= n; ++ i) read(a[i]);
root = build(1, n);
for(int i = 1, opt, l1, r1, l2, r2, val; i <= n; ++ i)
{
read(opt); read(l1); read(r1); l1 ^= last; r1 ^= last;
switch(opt)
{
case 1: write(last = Query(l1, r1), '\n'); break;
case 2: read(val); val ^= last; Cover(l1, r1, val); break;
case 3: read(val); val ^= last; Change(l1, r1, val); break;
case 4: read(l2); read(r2); l2 ^= last; r2 ^= last; Copy(l1, r1, l2, r2); break;
case 5: read(l2); read(r2); l2 ^= last; r2 ^= last; Swap(l1, r1, l2, r2); break;
case 6: Reverse(l1, r1); break;
}
if(cnt > 3200000)
{
top = 0; ldr(root);
root = cnt = 0;
root = build(1, n);
}
}
top = 0; ldr(root);// 这里注意 top 的初始化
for(int i = 1; i <= n; ++ i) write(a[i], ' ');
return 0;
}