标签：

「JSOI2014」序列维护

传送门
其实这题就是luogu的模板线段树2，，之所以要发题解就是因为被 \(\color{black}{\text{M}} \color{red}{\text{_sea}}\) 奉告了一种对照NB的 \(\text{update}\) 的方法。
我们可以把改削操纵统一化，视为 \(ax + b\) 的形式，然后我们凭据本来的套路来维护两个符号，分袂代表 \(a\) 和 \(b\) ，那么我们的更新就可以这么写：

inline void f(int p, int atag, int mtag, int l, int r) { t[p].sum = (t[p].sum * mtag % P + 1ll * atag * (r - l + 1) % P) % P; t[p].atag = (t[p].atag * mtag + atag) % P; t[p].mtag = t[p].mtag * mtag % P; }

然后我们就只需要写一个维护 \(ax + b\) 操纵的改削就可以了。
其实我们还可以发明这个对象还可以用于区间赋值 \((a = 0)\)。
的确很妙有没有
参考代码：

#include <cstdio> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) typedef long long LL; template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } const int _ = 100005; int n, m; LL P, a[_]; struct node { LL sum, atag, mtag; } t[_ << 2]; inline int lc(int p) { return p << 1; } inline int rc(int p) { return p << 1 | 1; } inline void pushup(int p) { t[p].sum = (t[lc(p)].sum + t[rc(p)].sum) % P; } inline void f(int p, int atag, int mtag, int l, int r) { t[p].sum = (t[p].sum * mtag % P + 1ll * atag * (r - l + 1) % P) % P; t[p].atag = (t[p].atag * mtag + atag) % P; t[p].mtag = t[p].mtag * mtag % P; } inline void pushdown(int p, int l, int r, int mid) { if (t[p].atag != 0 || t[p].mtag != 1) { f(lc(p), t[p].atag, t[p].mtag, l, mid); f(rc(p), t[p].atag, t[p].mtag, mid + 1, r); t[p].atag = 0, t[p].mtag = 1; } } inline void build(int p = 1, int l = 1, int r = n) { t[p].atag = 0, t[p].mtag = 1; if (l == r) { t[p].sum = a[l] % P; return ; } int mid = (l + r) >> 1; build(lc(p), l, mid), build(rc(p), mid + 1, r), pushup(p); } inline void update(int ql, int qr, LL atag, LL mtag, int p = 1, int l = 1, int r = n) { if (ql <= l && r <= qr) return f(p, atag, mtag, l, r); int mid = (l + r) >> 1; pushdown(p, l, r, mid); if (ql <= mid) update(ql, qr, atag, mtag, lc(p), l, mid); if (qr > mid) update(ql, qr, atag, mtag, rc(p), mid + 1, r); pushup(p); } inline LL query(int ql, int qr, int p = 1, int l = 1, int r = n) { if (ql <= l && r <= qr) return t[p].sum; int mid = (l + r) >> 1; LL res = 0; pushdown(p, l, r, mid); if (ql <= mid) res = (res + query(ql, qr, lc(p), l, mid)) % P; if (qr > mid) res = (res + query(ql, qr, rc(p), mid + 1, r)) % P; return res; } int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n), read(P); for (rg int i = 1; i <= n; ++i) read(a[i]); build(); read(m); for (rg int opt, l, r; m--; ) { read(opt); LL v; if (opt == 3) read(l), read(r), printf("%lld\n", query(l, r)); else read(l), read(r), read(v), update(l, r, opt != 2 ? 0 : v, opt != 1 ? 1 : v); } return 0; }

「JSOI2014」序列维护