Rockdu's Blog

原题地址

感觉还是很妙一个题，自己想了一会，看标签后茅塞顿开。

发现这个题的操作一直在用数列已经有的部分去覆盖一部分。

因为一直在用原来的，有点可持久化的意思。

发现其实我只要维护一个数据结构，可以把原来的一段提取出来插入到一个位置，

并且可以维护区间加区间和以及可以可持久化即可，这里的可持久化是为了不影响原来已有的部分，对于所有的修改都在新点上操作。

这样的数据结构就只有可持久化平衡树了。

非旋Treap的可持久化和线段树差不多，只要有修改的地方拉一个新点起来就行了。

时间复杂度O(n log n)，空间常数很大，注意不要爆空间。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<ctime>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m, o, l, r, x;
namespace Treap {
	struct node {
		int ch[2], sz, num, add;
		LL sum;
	} t[maxn * 350];
	const int L = 0, R = 1;
	int root, cnt;
	void push_up(int rt) {
		t[rt].sz = t[t[rt].ch[L]].sz + 1 + t[t[rt].ch[R]].sz;
		t[rt].sum = t[t[rt].ch[L]].sum + t[rt].num + t[t[rt].ch[R]].sum;
	}
	void push_down(int rt) {
		if(t[rt].add) {
			int &tl = t[rt].ch[L];
			if(tl) {
				t[++cnt] = t[tl], tl = cnt;
				t[tl].sum += t[tl].sz * t[rt].add;
				t[tl].num += t[rt].add;
				t[tl].add += t[rt].add;
			}
			int &tr = t[rt].ch[R];
			if(tr) {
				t[++cnt] = t[tr], tr = cnt;
				t[tr].sum += t[tr].sz * t[rt].add;
				t[tr].num += t[rt].add;
				t[tr].add += t[rt].add;
			}
			t[rt].add = 0;
		}
	}
	int Nmerge(int a, int b) {
		if(!a || !b) return a + b;
		if(rand() % (t[a].sz + t[b].sz) < t[a].sz) {
			t[a].ch[R] = Nmerge(t[a].ch[R], b);
			return push_up(a), a;
		} else {
			t[b].ch[L] = Nmerge(a, t[b].ch[L]);
			return push_up(b), b;
		}
	}
	int merge(int a, int b) {
		if(!a || !b) return a + b;
		if(rand() % (t[a].sz + t[b].sz) < t[a].sz) {
			push_down(a);
			t[++cnt] = t[a], a = cnt;
			t[a].ch[R] = merge(t[a].ch[R], b);
			return push_up(a), a;
		} else {
			push_down(b);
			t[++cnt] = t[b], b = cnt;
			t[b].ch[L] = merge(a, t[b].ch[L]);
			return push_up(b), b;
		}
	}
	void push_back(int x) {
		t[++cnt].sz = 1, t[cnt].sum = t[cnt].num = x;
		root = Nmerge(root, cnt);
		return ;
	}
	void split(int &a, int &b, int k) {
		push_down(a);
		if(t[a].sz == k) {b = 0; return ;}
		if(t[t[a].ch[L]].sz >= k) {
			t[++cnt] = t[a], a = cnt;
			split(t[a].ch[L], b, k);
			swap(t[a].ch[L], b);
			swap(a, b), push_up(b); // 现在重新接上的是右边的 
		} else {
			t[++cnt] = t[a], a = cnt;
			split(t[a].ch[R], b, k - t[t[a].ch[L]].sz - 1);
			push_up(a);
		}
	}
	void add(int l, int r, int dt) {
		int M = 0, L = root, R = 0;
		split(L, R, r + 1);
		split(L, M, l);
		t[M].add += dt;
		t[M].num += dt;
		t[M].sum += dt * t[M].sz;
		L = merge(L, M);
		L = merge(L, R);
		root = L;
	}
	LL query(int l, int r) {
		int lrt = root;
		int M = 0, L = root, R = 0;
		split(L, R, r + 1);
		split(L, M, l);
		return root = lrt, t[M].sum;
	}
	void replace(int l, int r, int x) {
		int lrt = root, nrt; 
		int M = 0, L = root, R = 0;
		split(L, R, l + x + 1);
		split(L, M, l), nrt = M;
		M = 0, L = lrt, R = 0;
		split(L, R, r + x + 1);
		split(L, M, r);
		L = merge(L, nrt);
		L = merge(L, R);
		root = L;
	}
}

int main() {
	using namespace Treap;
	//freopen("add10.in", "r", stdin);
	//freopen("my.out", "w", stdout);
	srand(66662333);
	scanf("%d%d", &n, &m);
	push_back(-inf);
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &x), push_back(x);
	push_back(inf);
	for(register int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &o, &l, &r);
		if(o == 1) scanf("%d", &x), add(l, r, x);
		else if(o == 2) scanf("%d", &x), replace(l, r, x);
		else printf("%lld\n", query(l, r));
	}
	return 0;
}