[题解]CFgym103470E Paimon Segment Tree

Paimon Segment Tree

区间加，求一段时间内的区间平方和。
\(n, m, q \le 5 \times 10^4\)。

对时间维差分一下，变成询问区间历史平方和。

离线下来扫描线，扫描线维护时间维，数据结构维护序列维。

考虑维护二元组 \((a, s)\) 表示当前位置值为 \(a\)，历史平方和为 \(s\)。

可以发现怎么修改最后的形式都会固定在 \((a + x, s + y a^2 + za + w)\)。

所以信息要多维护一个平方和，tag 维护 \((add, add1, add2, add3)\)。

tag 的复合手算一下就行。

时间复杂度 \(O((n + q) \log n)\)。

constexpr int MAXN = 5e4 + 9;
int n, m, q, a[MAXN];
tuple<int, int, int> q1[MAXN];
vector<tuple<int, int, int, int> > q2[MAXN];

struct Modint {
	int a;
	
	Modint(): a(0) { return; }
	Modint(int x): a((x % MOD + MOD) % MOD) { return; }
	
	friend Modint operator + (Modint x, Modint y) { return Modint(add(x.a, y.a)); }
	friend Modint operator - (Modint x, Modint y) { return Modint(del(x.a, y.a)); }
	friend Modint operator * (Modint x, Modint y) { return Modint((int)(1ll * x.a * y.a % MOD)); }
	friend Modint operator / (Modint x, Modint y) {
		static auto qpow = [&](Modint a, int b) {
			Modint ans = 1;
			for (; b; b >>= 1, a = a * a)
				if (b & 1) ans = ans * a;
			return ans;
		};
		return x * qpow(y, MOD - 2);
	}
	friend Modint operator + (Modint x, int y) { return x + Modint(y); }
	friend Modint operator - (Modint x, int y) { return x - Modint(y); }
	friend Modint operator * (Modint x, int y) { return x * Modint(y); }
	friend Modint operator / (Modint x, int y) { return x / Modint(y); }
	friend Modint operator + (int x, Modint y) { return Modint(x) + y; }
	friend Modint operator - (int x, Modint y) { return Modint(x) - y; }
	friend Modint operator * (int x, Modint y) { return Modint(x) * y; }
	friend Modint operator / (int x, Modint y) { return Modint(x) / y; }
	Modint& operator += (Modint x) { return (*this) = (*this) + x; }
	Modint& operator -= (Modint x) { return (*this) = (*this) - x; }
	Modint& operator *= (Modint x) { return (*this) = (*this) * x; }
	Modint& operator /= (Modint x) { return (*this) = (*this) / x; }
	Modint& operator += (int x) { return (*this) = (*this) + x; }
	Modint& operator -= (int x) { return (*this) = (*this) - x; }
	Modint& operator *= (int x) { return (*this) = (*this) * x; }
	Modint& operator /= (int x) { return (*this) = (*this) / x; }
	operator bool() const { return a; }
} ans[MAXN];

struct Info {
	Modint sum, sqr, ans;
	
	Info(): sum(Modint()), sqr(Modint()), ans(Modint()) { return; }
	Info(int _sum, int _sqr, int _ans):
		sum(Modint(_sum)), sqr(Modint(_sqr)), ans(Modint(_ans)) { return; }
	Info(int x): sum(Modint(x)), sqr(Modint(x) * Modint(x)), ans(0) { return; }
	friend Info operator + (Info x, Info y) {
		Info ans;
		ans.sum = x.sum + y.sum;
		ans.sqr = x.sqr + y.sqr;
		ans.ans = x.ans + y.ans;
		return ans;
	}
};
struct Tag {
	Modint add, add1, add2, add3;
	//		a	a^2		a	c
	
	Tag(int a = 0, int b = 0, int c = 0, int d = 0):
		add(Modint(a)), add1(Modint(b)), add2(Modint(c)), add3(Modint(d)) { return; }
	operator bool() const { return add || add1 || add2 || add3; }
	friend Tag operator * (Tag x, Tag y) {
		Tag ans;
		ans.add = x.add + y.add;
		ans.add1 = x.add1 + y.add1;
		ans.add2 = x.add2 + y.add2 + 2 * x.add1 * y.add;
		ans.add3 = x.add3 + y.add3 + x.add1 * y.add * y.add + x.add2 * y.add;
		return ans;
	}
	Info Apply(Info x, int len) {
		Info ans;
		ans.sum = x.sum + add * len;
		ans.sqr = x.sqr + 2 * add * x.sum + add * add * len;
		ans.ans = x.ans + add1 * x.sqr + add2 * x.sum + add3 * len;
		return ans;
	}
};
struct Node {
	Info dat; Tag tag;
} sgt[MAXN << 2];

void Push_Up(int p) {
	sgt[p].dat = sgt[p << 1].dat + sgt[p << 1 | 1].dat;
	return;
}
void Push_Tag(int p, Tag tg, int len) {
	sgt[p].tag = tg * sgt[p].tag;
	sgt[p].dat = tg.Apply(sgt[p].dat, len);
	return;
}
void Push_Down(int p, int l, int r) {
	if (sgt[p].tag) {
		int mid = l + r >> 1;
		Push_Tag(p << 1, sgt[p].tag, mid - l + 1);
		Push_Tag(p << 1 | 1, sgt[p].tag, r - mid);
		sgt[p].tag = Tag();
	}
	return;
}
void Build(int l = 1, int r = n, int p = 1) {
	if (l == r) { sgt[p].dat = Info(a[l]); return; }
	int mid = l + r >> 1;
	Build(l, mid, p << 1), Build(mid + 1, r, p << 1 | 1);
	Push_Up(p); return;
}
void Update(int l, int r, int k, int L = 1, int R = n, int p = 1) {
	if (l <= L && R <= r) { Push_Tag(p, Tag(k, 0, 0, 0), R - L + 1); return; }
	Push_Down(p, L, R); int Mid = L + R >> 1;
	if (l <= Mid) Update(l, r, k, L, Mid, p << 1);
	if (Mid < r) Update(l, r, k, Mid + 1, R, p << 1 | 1);
	Push_Up(p); return;
}
Modint Query(int l, int r, int L = 1, int R = n, int p = 1) {
	if (l <= L && R <= r) return sgt[p].dat.ans;
	Push_Down(p, L, R); int Mid = L + R >> 1;
	if (r <= Mid) return Query(l, r, L, Mid, p << 1);
	if (Mid < l) return Query(l, r, Mid + 1, R, p << 1 | 1);
	return Query(l, r, L, Mid, p << 1) + Query(l, r, Mid + 1, R, p << 1 | 1);
}

void slv() {
	n = Read<int>(), m = Read<int>(), q = Read<int>();
	for (int i = 1; i <= n; i ++) a[i] = Read<int>();
	for (int i = 1; i <= m; i ++) {
		int l = Read<int>(), r = Read<int>(), x = Read<int>();
		q1[i] = make_tuple(l, r, x);
	}
	for (int i = 1; i <= q; i ++) {
		int l = Read<int>(), r = Read<int>(), x = Read<int>(), y = Read<int>();
		if (x) q2[x - 1].emplace_back(l, r, -1, i);
		q2[y].emplace_back(l, r, 1, i);
	}
	Build(), Push_Tag(1, Tag(0, 1, 0, 0), n);
	for (auto _ : q2[0]) {
		int l, r, op, id; tie(l, r, op, id) = _;
		ans[id] += op * Query(l, r);
	}
	for (int i = 1; i <= m; i ++) {
		{
			int l, r, x; tie(l, r, x) = q1[i];
			Update(l, r, x), Push_Tag(1, Tag(0, 1, 0, 0), n);
		}
		for (auto _ : q2[i]) {
			int l, r, op, id; tie(l, r, op, id) = _;
			ans[id] += op * Query(l, r);
		}
	}
	for (int i = 1; i <= q; i ++) Write(ans[i].a, '\n');
	return;
}