线段树

P4681 [THUSC2015]平方运算

简要题意

给定一个序列，区间 .map([](int x) { x = x * x % p; });，区间求和。
p 给定，为小质数。\(N,M\le 105\)。

题解

而把一个数看作一个点，向其平方取模连一条边，则最终必然构成一个基环森林，注意到 \(P\)
很小，每个数经过至多 \(11\) 次迭代之后就会进入环中。对于一个区间，如果区间中的每个元素都已经在环里，则区间所有元素所在环的大小的 \(\operatorname{lcm}\)，即为区间的循环节。而对于题目给出的 \(P\)，\(\operatorname{lcm}\le 60\)，记为 \(C\)。

先考虑初始是每个元素都在环内的时候怎么做：发现可以用线段树维护，对于每个区间，我们可以直接维护该区间的一个完整循环节，以及当前在循环节内的位置 \(now\)，则如果要对整个区间进行 \(k\) 次修改，则直接让 \(now\) 向前移动 \(k\) 即可，故可以 \(O(1)\) pushdown，如果一个区间的子区间被修改了，那么在 pushup 的时候直接根据两个子区间的循环节算出当前区间的循环节即可，复杂度 \(O(C)\)。

如果一个区间内包含不在环内的元素，则无法维护循环节，我们只维护当前区间的和，需要 pushdown 时暴力递归向子区间 pushdown。由于每个元素经过至多 \(S=11\)
次操作后进入环，简单均摊分析发现这一部分增添的复杂度是 \(O(nSlogn)\) 的。

总时间复杂度 \(O(nlogn(C+S))\) 可以通过。

对于循环移位维护一个循环节和当前位置的指针是十分显然的。

CF526F Pudding Monster

线段树维护历史和，略。

P8969 Dream with Dynamic

简要题意

给定一个序列，区间加，区间 popcount，单点求值。

题解

对于一个操作序列 \(A\)，如果 \(A\) 包含了至少一次 popcount 操作，记该次操作及以前的操作为 \(U\)，以后的操作为 \(V\)。

注意到 \(U\) 操作后仅有 \([1,\operatorname{popcnt}(V)]\) 共 \(O(\log V)\) 种不同的结果，故我们可以把 \(V\) 的有效部分记为映射 \(V':[1,\operatorname{popcnt}(V)]\mapsto \mathbb{Z}\)。

对于 \(U\)，其为一系列加法操作复合一个 popcount 操作，记录加法操作的总和即可。

对于两个操作序列 \(u,v\) 及其复合 \(u\circ v\)，显然可以 \(O(\log V)\) 进行复合且结果仍可以使用以上方法记录。线段树维护即可，复杂度 \(O(n\log n\log V)\)。

record

2023 福建省队集训 Dream

简要题意

对于一个序列，维护：

• 区间加减一。
• 区间打标记，若有多个标记保留最小的。
• 区间回溯到标记，若不存在标记或 标记大于当前值 则忽略。

单点查询。

题解

想到可以用线段树维护之后的推导是平凡的，只是稍微有一些繁琐。

（下面记的东西价值不大，以后遇到这种题能想到线段树维护就肯定能够做出来了）

若有回溯操作，一个操作序列仅需要保留信息 \((minL,set,minR,tag,now)\)：
\(minL,minR\) 表示回溯前后的最小值。\(set\) 表示回溯到的值，\(tag\) 当前拥有的标记，\(now\) 表示当前的值。注意 \(minL,set\) 是相对于操作序列开始的增量，\(minR,tag,now\) 是相对于回溯到的值的增量。

若没有回溯操作则不记录 \(minL,set\) 即可。

record