P5350 序列

题意

维护一个序列：

• 区间查询
• 区间赋值
• 区间加法
• 区间复制
• 区间交换
• 区间翻转

数据随机。

Sol

珂朵莉。

前 \(3\) 个操作很 \(trivial\)。

考虑区间复制。

先把两个区间 \(split\) 出来。

然后扔进 \(vector\)，全部 \(erase\) 掉。再用 \(vector\) \(insert\) 进去。

随便搞搞就过了。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <set>
#include <vector>
#include <cassert>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
#define fi first
#define se second

const int mod = 1e9 + 7;

void Mod(int &x) {
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}

namespace Chtholly {

class Node {

public:

	int l, r;
	mutable int v;

	Node (int _l, int _r, int _v) : l(_l), r(_r), v(_v) {}

	bool operator <(const Node &t) const { return l < t.l; }

};

set <Node> Cht;

auto split(int x, int n) {
	if (x > n) return Cht.end();
	auto it = --Cht.upper_bound(Node(x, 0, 0));
	if (it -> l == x) return it;
	int l = it -> l, r = it -> r, v = it -> v;
	Cht.erase(it), Cht.insert(Node(l, x - 1, v));
	return Cht.insert(Node(x, r, v)).fi;
}

int query(int l, int r, int n) {
	auto itr = split(r + 1, n), itl = split(l, n);
	int ans = 0;
	for (auto it = itl; it != itr; it++)
		ans += it -> v * (it -> r - it -> l + 1) % mod, Mod(ans);
	return ans;
}

void assign(int l, int r, int v, int n) {
	auto itr = split(r + 1, n), itl = split(l, n);
	Cht.erase(itl, itr);
	Cht.insert(Node(l, r, v));
}

void modify(int l, int r, int v, int n) {
	auto itr = split(r + 1, n), itl = split(l, n);
	for (auto it = itl; it != itr; it++)
		it -> v += v, Mod(it -> v);
	return;
}

void copy(int l1, int r1, int l2, int r2, int n) {
	auto itr = split(r1 + 1, n), itl = split(l1, n);
	vector <Node> tp;
	for (auto it = itl; it != itr; it++)
		tp.push_back(Node(it -> l + l2 - l1, it -> r + l2 - l1, it -> v));
	itr = split(r2 + 1, n), itl = split(l2, n);
	Cht.erase(itl, itr);
	for (auto x : tp) Cht.insert(x);
}

void swap(int l1, int r1, int l2, int r2, int n) {
	auto itr = split(r1 + 1, n), itl = split(l1, n);
	vector <Node> tp1, tp2;
	for (auto it = itl; it != itr; it++)
		tp1.push_back(Node(it -> l + l2 - l1, it -> r + l2 - l1, it -> v));
	itr = split(r2 + 1, n), itl = split(l2, n);
	for (auto it = itl; it != itr; it++)
		tp2.push_back(Node(it -> l + l1 - l2, it -> r + l1 - l2, it -> v));
	Cht.erase(itl, itr); for (auto x : tp1) Cht.insert(x);
	itr = split(r1 + 1, n), itl = split(l1, n);
	Cht.erase(itl, itr); for (auto x : tp2) Cht.insert(x);
}

void reverse(int l, int r, int n) {
	auto itr = split(r + 1, n), itl = split(l, n);
	vector <Node> tp;
	for (auto x : Cht) {
		/* write(x.l), putchar(32); */
		/* write(x.r), putchar(32); */
		/* write(x.v), puts(""); */
	}
	for (auto it = itl; it != itr; it++) {
		int lp = it -> l, rp = it -> r, v = it -> v;
		lp = r - lp + l, rp = r - rp + l;
		if (lp > rp) std::swap(lp, rp);
		/* write(lp), putchar(32); */
		/* write(rp), puts(""); */
		tp.push_back(Node(lp, rp, v));
	}
	Cht.erase(itl, itr);
	for (auto x : tp) Cht.insert(x);
}

}

signed main() {
	int n = read(), q = read();
	for (int i = 1; i <= n; i++)
		Chtholly::Cht.insert(Chtholly::Node(i, i, read()));
	while (q--) {
		int op = read(), l = read(), r = read(), x, y;
		switch (op) {
		case 1:
			write(Chtholly::query(l, r, n)), puts("");
			break;
		case 2:
			x = read();
			Chtholly::assign(l, r, x, n);
			break;
		case 3:
			x = read();
			Chtholly::modify(l, r, x, n);
			break;
		case 4:
			x = read(), y = read();
			Chtholly::copy(l, r, x, y, n);
			break;
		case 5:
			x = read(), y = read();
			Chtholly::swap(l, r, x, y, n);
			break;
		default:
			Chtholly::reverse(l, r, n);
		}
	}

	int now = 0;
	for (auto x : Chtholly::Cht) {
		int tp = x.r - x.l + 1;
		now += tp;
		/* while (tp--) write(x.v), putchar(32); */
	}
	assert(now == n);
	for (auto x : Chtholly::Cht) {
		int tp = x.r - x.l + 1;
		now += tp;
		while (tp--) write(x.v), putchar(32);
	}
	puts("");

	return 0;
}