LG P9844 [ICPC 2021 Nanjing R] Paimon Segment Tree Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，有 $m$ 次修改 $(l,r,v)$：

• 对每个 $i\in [l,r]$，令 $a_i\leftarrow a_i+v$.

执行完所有修改后，进行 $q$ 次查询 $(l,r,L,R)$，你需要求出 $a_l\sim a_r$ 在第 $[L,R]$ 秒间的历史平方和，对 $10^9+7$ 取模.
初始时为第 $0$ 秒，第 $i$ 次修改发生在第 $i$ 秒.

Limitations

$1\le n,m,q\le 5\times 10^4$
$1\le l\le r\le n$
$0\le L\le R\le m$
$|a_i|,|v|<10^9+7$
$4\text{s},256\text{MB}$

Solution

首先将询问拆成 $[0,y]$ 和 $[0,x-1]$，在时间轴上做扫描线.
然后需要一个 ds，支持区间加，区间历史平方和.
需要维护很多 $\text{tag}$，考虑矩阵，维护区间长度 $len$，区间和 $s_1$，区间平方和 $s_2$，历史平方和 $h$.
由左行右列的口诀，不难推导出转移矩阵：

• 标记一个版本：$\left[\begin{array}{c}l,s_1,s_2,h\end{array}\right]\times \left[\begin{array}{c}1,0,0,0\\ 0,1,0,0\\ 0,0,1,1\\ 0,0,0,1\end{array}\right]=\left[\begin{array}{c}l,s_1,s_2,h^{\prime }\end{array}\right]$
• 区间加 $v$：$\left[\begin{array}{c}l,s_1,s_2,h\end{array}\right]\times \left[\begin{array}{c}1,v,v^2,v^2\\ 0,1,2v,2v\\ 0,0,1,0\\ 0,0,0,1\end{array}\right]=\left[\begin{array}{c}l,s_1,s_2,h^{\prime }\end{array}\right]$

然后直接套 P7453 的矩阵线段树即可（甚至矩阵大小都一样）.
常数方面，如果你 P7453 的代码能稳过，应该没什么问题.
时间复杂度 $O(k^3(m+q)\log n)$，其中 $k=4$.

Code

$5.54\text{KB},0.99\text{s},18.14\text{MB}\text{(maximum,C++20 with O2)}$

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}namespace fastio {}
using fastio::read;
using fastio::write;constexpr int mod = 1e9 + 7;
inline int add(int x, int y) {return x + y >= mod ? x + y - mod : x + y; }namespace matrix {}
using matrix::Mat;namespace seg_tree {struct Node {int l, r;Mat val, tag;};inline int ls(int u) { return 2 * u + 1; }inline int rs(int u) { return 2 * u + 2; }struct SegTree {vector<Node> tr;inline SegTree() {}inline SegTree(const vector<int>& a) {const int n = a.size();tr.resize(n << 1);build(0, 0, n - 1, a);}inline void pushup(int u, int mid) {tr[u].val = tr[ls(mid)].val + tr[rs(mid)].val;}inline void apply(int u, const Mat& mat) {tr[u].val = tr[u].val * mat;tr[u].tag = tr[u].tag * mat;}inline void pushdown(int u, int mid) {if (tr[u].tag == Mat()) return;apply(ls(mid), tr[u].tag);apply(rs(mid), tr[u].tag);tr[u].tag = Mat();}void build(int u, int l, int r, const vector<int>& a) {tr[u].l = l, tr[u].r = r;if (l == r) {tr[u].val[0][0] = 1;tr[u].val[0][1] = add(a[l], mod);tr[u].val[0][2] = tr[u].val[0][3] = 1LL * a[l] * a[l] % mod;return;}const int mid = (l + r) >> 1;build(ls(mid), l, mid, a);build(rs(mid), mid + 1, r, a);pushup(u, mid);}void modify(int u, int l, int r, const Mat& mat) {if (l <= tr[u].l && tr[u].r <= r) return apply(u, mat);const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u, mid);if (l <= mid) modify(ls(mid), l, r, mat);if (r > mid) modify(rs(mid), l, r, mat);pushup(u, mid); }Mat query(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;const int mid = (tr[u].l + tr[u].r) >> 1;Mat res = Mat(0);pushdown(u, mid);if (l <= mid) res = res + query(ls(mid), l, r);if (r > mid) res = res + query(rs(mid), l, r);return res;}inline void range_mul(int l, int r, const Mat& mat) { modify(0, l, r, mat); }inline Mat range_sum(int l, int r) { return query(0, l, r); }};
}
using seg_tree::SegTree;struct Query {int l, r, t, id;inline Query() {}inline Query(int _l, int _r, int _t, int _id) : l(_l), r(_r), t(_t), id(_id) {}
};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);const int n = read<int>(), m = read<int>(), q = read<int>();vector<int> a(n), sum(n);for (int i = 0; i < n; i++) {a[i] = read<int>();sum[i] = add(i ? sum[i - 1] : 0, 1LL * a[i] * a[i] % mod);}vector<int> L(m), R(m), X(m);for (int i = 0; i < m; i++) {L[i] = read<int>(), R[i] = read<int>(), X[i] = read<int>();L[i]--, R[i]--;}vector<vector<Query>> adj(m + 1);for (int i = 0, l, r, x, y; i < q; i++) {l = read<int>(), r = read<int>(), x = read<int>(), y = read<int>(), l--, r--;adj[y].emplace_back(l, r, 1, i);if (x > 0) adj[x - 1].emplace_back(l, r, -1, i);}Mat A; A[2][3] = 1;SegTree sgt(a);vector<int> ans(q);for (auto & [l, r, t, id] : adj[0]) {ans[id] = add(ans[id], add(add(sum[r] - (l > 0 ? sum[l - 1] : 0), mod) * t, mod));}for (int i = 0; i < m; i++) {Mat tmp;tmp[0][1] = add(X[i], mod);tmp[0][2] = tmp[0][3] = 1LL * X[i] * X[i] % mod;tmp[1][2] = tmp[1][3] = 2LL * add(X[i], mod) % mod;tmp[2][3] = 1;sgt.range_mul(L[i], R[i], tmp);if (L[i] > 0) sgt.range_mul(0, L[i] - 1, A);if (R[i] < n - 1) sgt.range_mul(R[i] + 1, n - 1, A);for (auto & [l, r, t, id] : adj[i + 1]) {ans[id] = add(ans[id], add(sgt.range_sum(l, r)[0][3] * t, mod));}}for (int i = 0; i < q; i++) {write(ans[i]);putchar_unlocked('\n');}return 0;
}