MOCK NOIP 20231027 T2 – 缺金木 – 线段树的“双半群”模型

题意简述

给定长为 $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)$，常数大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#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;
}