题意简述
给定长为 $n$ 的序列 $a$。要求支持以下操作：
- 给定 $l,r,x$，将 $a_i,l\leq i\leq r$ 全部加上 $x$；
- 给定 $l,r,x$，将 $a_i,l\leq i\leq r$ 全部乘以 $x$；
- 给定 $l,r,x$，若这是第 $k$ 次操作，则保护 $a_i,l\leq i\leq r$ 直到第 $k+x$ 次操作（含），这期间操作 $1,2$ 对 $a_i$ 无效。若 $a_i$ 已经被保护到 $x’,x’>k+x$，则这一保护不会失效。
- 给定 $l,r$，输出 $\sum_{i=l}^{r} a_i$，对 $10^9+7$ 取余。
$n,m\leq 2\times 10^5$。
半群、双半群模型——线段树到底能维护怎样的信息？——caijianhong 的博客园
简而言之，带延迟标记的递归式线段树支持区间操作地维护“双半群”模型的信息，其中要维护的元素“和”在半群 $\newcommand\D{\mathcal D}\D$ 中，对元素的操作在半群 $\newcommand\M{\mathcal M}\M$ 中；还须满足
- $\D+\D\rightarrow \D$（两元素的结合），$(\D,+)$ 运算有结合律——否则无法区间查询；
- $\D\times \M\rightarrow \D$（对元素执行操作），$\times$ 运算对 $(\D,+)$ 有分配律（$(d_1+d_2)\times m=d_1\times m+d_2\times m, d_1,d_2\in\D,m\in\M$）——否则对元素的修改无法整区间地合并；
- $\M\cdot\M\rightarrow\M$（两操作的顺序执行），要求有结合律——否则无法合并修改序列的诸项。
以上任意性质不满足，都可能导致复杂度分析与“常规”线段树不同：例如 Segment Tree Beats! （区间取最值，不满足$\times$ 对 $+$ 的分配律），对其运用势能分析才得出正确的复杂度。其他所有能维护的信息都可用上述模型解释。
NOIP 2022 T4 亦可以说是考察了双半群的构造。
本题中双半群的构造
我们将“保护 $a_i$ 从 $l$ 到 $r$ 不受影响”视为“$a_i$ 的保护度在 $[l,r]$ 中时刻增加了 $1$”，且当保护度为 $0$ 时才可对 $a_i$ 进行加、乘操作。同时将对 $a_i$ 的未过滤的操作序列划为三种操作：$+,\times,\Delta$，其中 $\Delta$ 表示其保护度的变化量。$(\times c,+d)$ 的二元组容易合并：$(\times c_1,+d_1)\circ(\times c_2,+d_2)=(\times c_1c_2,+(d_1c_2+d_2))$。
“恰好为 $0$”这一条件似乎太苛刻了：只观察特定片段的未过滤的操作序列，不能得出哪一部分在结合其余操作以后保护度为 $0$。不过，若我们一字排开 $(\times c_1,+d_1,\Delta_1),\cdots,(\times c_t,+d_t,\Delta_t)$，并令 $p_i=\sum_{j=1}^{i}\Delta_j$，“$p_i=\min\{p_j\mid 1\leq j\leq t\}$”是“$(\times c_i,+d_i)$ 能出现在过滤后的操作序列”的必要条件。因此，我们的“操作”群 $\M$ 就呼之欲出了：其元素是四元素 $(c,d,\Delta,p)$（$p$ 即上文中 $\min\{p_j\mid 1\leq j\leq t\}$），合并运算 $\cdot$ 满足
$$
(c_1,d_1,\Delta_1,p_1)\cdot(c_2,d_2,\Delta_2,p_2)=
\begin{cases}
(c_1c_2,d_1c_2+d_2,\Delta_1+\Delta_2,p_1)& p_1=\Delta_1+p_2,\\
(c_1,d_1,\Delta_1+\Delta_2,p_1)& p_1<\Delta_1+p_2,\\ (c_2,d_2,\Delta_1+\Delta_2,\Delta_1+p_2)& p_1>\Delta_1+p_2
\end{cases}.
$$
那么我们维护的元素 $\D$ 呢？可以定义一个二元组 $(x,l)$，$x$ 是我们需求和的值，$l$ 是该元素目前的保护度。且不难写出 $\D,\M$ 之间的乘法 $\times$：
$$
(x,l)\times(c,d,\Delta,p)=
\begin{cases}
(x,l+\Delta)& l+p=0,\\
(cx+d,l+\Delta)& l+p>0
\end{cases}
$$
那么，$\D$ 中元素带有结合律的加法呢？这似乎很难定义了：$x$ 改变与 $l$ 的值强相关，难以直接求和；更别提与 $\times$ 之间的分配律了。但我们注意到，本题保证了 $l$ 恒为非负数；并且同 $\M$ 一样，在各个 $(x_i,l_i)$ 中，$\times$ 运算后 $x_i$ 发生改变的只可能是 $l_i$ 最小的一批——还需保证 $p=-l_{\text{min}}$！我们如法炮制，定义四元组 $(s,l,t,s’)$ 表示“对于一些 $(x_i,l_i)$，对于 $l_i$ 取到 $l=\min\{l_j\}$ 的所有 $x_i$，其和为 $s$，个数为 $t$；对于其他，其和为 $s’$”。这样，$(x,l)$ 就可以轻松合并了。我们不妨直接用该四元组作为 $\D$ 的元素（原来单个 $(x,l)$ 变为 $(x,l,1,0)$），得到
$$
(s_1,l_1,t_1,{s’}_1)+(s_2,l_2,t_2,{s’}_2)=
\begin{cases}
(s_1+s_2,l_1,t_1+t_2,{s’}_1+{s’}_2)&l_1=l_2,\\
(s_1,l_1,t_1,{s’}_1+{s’}_2+s_2)&l_1<l_2,\\ (s_2,l_2,t_2,{s’}_1+{s’}_2+s_1)&l_1>l_2\\
\end{cases}
$$
$$
(s,l,t,s’)\times(c,d,\Delta,p)=
\begin{cases}
(sc+td,l+\Delta,t,s’)&p+l=0,\\
(s,l+\Delta,t,s’)&p+l>0
\end{cases}
$$
时间复杂度 $\operatorname{O}(n+m\log n)$，常数大。
#include <bits/stdc++.h>
using namespace std;
#define inl inline
/* 快读已省略。 */
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 lll;
// typedef long double llf;
typedef pair <int, int> pint;
#define fst first
#define scd second
#define all(p) begin (p), end (p)
#define empb emplace_back
#ifdef SHIKEN
#define msg(args...) fprintf (stderr, args)
#else
#define msg(...) void ()
#endif
constexpr int N = 2e5 + 10, P = 1e9 + 7, G = 1<<19;
int n, m, a[N];
vector <pint> dim[N];
inl int& add (int &x, int y) { return x += y, x >= P ? x -= P : x; }
inl int& subt (int &x, int y) { return x -= y, x < 0 ? x += P : x; }
inl int sum (int x, int y) { return add (x, y); }
inl int diff (int x, int y) { return subt (x, y); }
struct seg_tree {
struct monoid {
int c, d, dt, mndt;
inl monoid operator + (const monoid &g) const {
monoid h { 1, 0, dt + g.dt, min (mndt, g.mndt + dt) };
if (mndt == h.mndt) h.c = c, h.d = d;
if (g.mndt + dt == h.mndt)
h.d = ((ll) h.d * g.c + g.d) % P,
h.c = (ll) h.c * g.c % P;
return h;
}
};
struct quark {
int mnl, mnls, mnlc, exts;
inl quark operator + (const quark &b) const {
quark c { min (b.mnl, mnl), 0, 0, sum (exts, b.exts) };
if (mnl == c.mnl)
add (c.mnls, mnls), c.mnlc += mnlc;
else add (c.exts, mnls);
if (b.mnl == c.mnl)
add (c.mnls, b.mnls), c.mnlc += b.mnlc;
else add (c.exts, b.mnls);
return c;
}
};
inl friend quark operator + (quark a, const monoid &f) {
auto &[mnl, mnls, mnlc, exts] = a;
const auto &[c, d, dt, mndt] = f;
if (mnl + mndt == 0)
mnls = ((ll) mnls * c + (ll) d * mnlc) % P;
return mnl += dt, a;
}
struct node {
quark dta; monoid tag;
} t[G];
inl void saku (int x, const monoid &p) {
t[x].dta = t[x].dta + p;
t[x].tag = t[x].tag + p;
}
inl void down (int x) {
saku (x<<1, t[x].tag);
saku (x<<1|1, t[x].tag);
t[x].tag = { 1, 0, 0, 0 };
}
inl void post (int x) {
t[x].dta = t[x<<1].dta + t[x<<1|1].dta;
}
void build (int x = 1, int l = 1, int r = n) {
t[x].tag = { 1, 0, 0, 0 };
if (l == r) {
t[x].dta = { 0, a[l], 1, 0 };
return;
}
int mid = l + r >> 1;
build (x<<1, l, mid);
build (x<<1|1, mid + 1, r);
post (x);
}
void upd (int L, int R, const monoid &p, int x = 1, int l = 1, int r = n) {
if (l >= L && r <= R) return saku (x, p);
int mid = l + r >> 1; down (x);
if (L <= mid) upd (L, R, p, x<<1, l, mid);
if (R > mid) upd (L, R, p, x<<1|1, mid + 1, r);
post (x);
}
quark query (int L, int R, int x = 1, int l = 1, int r = n) {
if (l >= L && r <= R) return t[x].dta;
int mid = l + r >> 1; down (x);
switch ((L<=mid)<<1|(R>mid)) {
case 0b10: return query (L, R, x<<1, l, mid);
case 0b01: return query (L, R, x<<1|1, mid + 1, r);
default: return query (L, R, x<<1, l, mid)
+ query (L, R, x<<1|1, mid + 1, r);
}
}
} seg;
int main () {
/* */
read (n, m);
for (int i = 1; i <= n; ++i)
read (a[i]);
seg.build ();
for (int i = 1, op, l, r, x; i <= m; ++i) {
for (const auto &[l, r] : dim[i])
seg.upd (l, r, { 1, 0, -1, -1 });
read (op, l, r);
if (op <= 3) {
read (x);
seg_tree::monoid p;
if (op == 1) p = { 1, x, 0, 0 };
else if (op == 2) p = { x, 0, 0, 0 };
else p = { 1, 0, 1, 0 }, dim[i + x + 1].empb (l, r);
seg.upd (l, r, p);
} else {
const auto res = seg.query (l, r);
print (sum (res.mnls, res.exts)), putc ('\n');
}
}
return 0;
}