Rikka with Sequence

题目链接

题意

支持序列三种操作：
1.求(l,r)区间和。
2.执行代码”for (int i=l;i<=r;i++) A[i]=A[i-k];”
3.将区间(l,r)，序列还原。

思路

可持久化treap，在无旋treap的基础上发展而来，这道题算是我的第一次可持久treap吧。
要注意的一个是操作二，有可能涉及到一个区间重复很多遍，我们可以用类似快速幂的操作将这个区间复制到一个目的长度。
还有要及时回收多余的结点，暴力重建整棵树。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50

const int N = 2e5 + 10;
#define ls(x) treap[x].child[0]
#define rs(x) treap[x].child[1]
int rt, root, rtop, utop, sz, ver;
int a[N], res[N << 2], used[N << 2], pos[N << 2];

int n;

struct node
{
	int child[2], val, size;
	ll sum;
	void init()
	{
		child[0] = child[1] = val = sum = 0;
		size = 1;
	}
}treap[N << 2];

int newnode(int val = 0)
{
	int x;
	if (rtop)
		x = res[rtop--];
	else
		x = ++sz;
	used[++utop] = x;
	treap[x].init();
	treap[x].val = val;
	return x;
}

void push_up(int u)
{
	treap[u].size = treap[ls(u)].size + treap[rs(u)].size + 1;
	treap[u].sum = treap[ls(u)].sum + treap[rs(u)].sum + treap[u].val;
}

void dfs(int u)
{
	if (!u)
		return;
	pos[u] = ver;
	dfs(ls(u));
	dfs(rs(u));
}

void rebuild()
{
	ver++;
	dfs(root);
	dfs(rt);
	int top = 0;
	for (int i = 1; i <= utop; i++)
		if (pos[used[i]] == ver)
			used[++top] = used[i];
		else
			res[++rtop] = used[i];
	utop = top;
}

int build(int l, int r)
{
	if (l > r)
		return 0;
	int mid = (l + r) >> 1;
	int u = newnode(a[mid]);
	ls(u) = build(l, mid - 1);
	rs(u) = build(mid + 1, r);
	push_up(u);
	return u;
}

ll seed = 17121197;

ll Rand()
{
    return seed = seed * 48271 % 2147483647;
}

int merge(int x, int y)
{
	if (!x && !y)
		return 0;
	int u = newnode();
	if (!x || !y)
	{
		treap[u] = treap[x + y];
		return u;
	}
	if (Rand() & 1)
	{
		treap[u] = treap[x];
		rs(u) = merge(rs(x), y);
	}
	else
	{
		treap[u] = treap[y];
		ls(u) = merge(x, ls(y));
	}
	push_up(u);
	return u;
}

int Pow(int a, int b)
{
	int ret = 0;
	while (b)
	{
		if (b & 1)
			ret = merge(ret, a);
		a = merge(a, a);
		b >>= 1;
	}
	return ret;
}

int split(int x, int l, int r)
{
	if (l > r)
		return 0;
	if (l == 1 && r == treap[x].size)
	{
		int u = newnode();
		treap[u] = treap[x];
		return u;
	}
	if (r <= treap[ls(x)].size)
		return split(ls(x), l, r);
	if (l > treap[ls(x)].size + 1)
		return split(rs(x), l - treap[ls(x)].size - 1, r - treap[ls(x)].size - 1);
	int u = newnode(treap[x].val);
	ls(u) = split(ls(x), l, treap[ls(x)].size);
	rs(u) = split(rs(x), 1, r - treap[ls(x)].size - 1);
	push_up(u);
	return u;
}

void update(int l, int r, int k)
{
	int x = split(rt, 1, l - k - 1), y = split(rt, l - k, l - 1);
	int z = Pow(y, (r - l + 1) / k);
	int a = split(rt, l - k, l - k + 1 + (r - l + 1) % k);
	int b = split(rt, r + 1, n);
	rt = merge(x, y);
	rt = merge(rt, z);
	rt = merge(rt, a);
	rt = merge(rt, b);
}

void back(int l, int r)
{
	int x = split(rt, 1, l - 1), y = split(root, l, r), z = split(rt, r + 1, n);
	rt = merge(x, y);
	rt = merge(rt, z);
}

int main()
{
	int q;
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	int limit = 450;
	ls(0) = rs(0) = treap[0].sum = 0;
	treap[0].size = 0;
	rt = root = build(1, n);
	while (q--)
	{
		int type;
		scanf("%d", &type);
		int l, r;
		scanf("%d%d", &l, &r);
		if (q % limit == 0)
			rebuild();
		if (type == 1)
			printf("%lld\n", treap[split(rt, l, r)].sum);
		else if (type == 2)
		{
			int k;
			scanf("%d", &k);
			update(l, r, k);
		}
		else
			back(l, r);
	}
	return 0;
}