区间数颜色
LOJ #3751. [SDOI2009] HH 的项链
给定长度为 \(n\) 的序列，\(m\) 次询问 \([l,r]\) 内有多少不同的元素。
\(n\le 5\times 10^4\)，\(m\le 2\times 10^5\)。
区间数颜色是莫队算法的经典应用，可以用莫队在 \(\Theta(m\sqrt n)\) 内解决。
P1972 [SDOI2009] HH的项链（数据加强版）
题面同上题。\(n,m\le 10^6\)。
根号算法显然难以通过。我们考虑 \(\mathrm{polylog}\) 的算法。
我们不妨对右端点扫描线（将询问按右端点从小到大排序，令 \(i\) 遍历 \(1\sim r\)，并回答 \(r=i\) 的询问）。一旦以 \(i\) 为右端点的询问被处理完了，我们对 \([1,i]\) 修改就不会影响到前面的询问了。
综上，我们考虑如下的算法：
- 初始化 \(pos_i=0\)，表示 \(i\) 上次出现位置是 \(0\)（即没有出现过）；初始化 \(b\) 序列为全 \(0\)。
- 遍历 \(i=1\sim n\)。
- 记 \(pre=pos_{a_i}\)。令 \(b_{pre}\gets 0\)。
- 令 \(b_i\gets 1\)。
- 令 \(pos_{a_i}=i\)。
- 遍历所有 \(r=i\) 的询问，答案即为 \(b\) 序列 \([l,r]\) 的区间和。
正确性是比较显然的。
利用树状数组维护前缀和，我们在 \(\Theta(m\log n)\) 内解决了问题。
线段树与区间最值问题
线段树与历史最值问题
P4314 CPU 监控
给定序列 \(a\)，维护以下操作。定义辅助序列 \(b\)，初始时 \(b=a\)，每次操作完后对 \(\forall i\in [1,n]\)，令 \(b_i\gets \max(a_i,b_i)\)。
-
查询 \(\max_{i=l}^{r} a_i\)（区间最值）
-
查询 \(\max_{i=l}^{r} b_i\)（历史最值）
-
\(\forall i\in [l,r]\)，\(a_i\gets a_i+v\)（区间修改）
-
\(\forall i\in [l,r]\)，\(a_i\gets v\)（区间覆盖）
\(n,m\le 10^5\)，\(|a_i|,|v|\lt 2^{31}\)。
先只考虑修改操作。对于一个节点（记最大值为 \(v\)，历史最大值为 \(h\)），影响到它的操作可以放进一个队列：
\[[add_1,add_2,\cdots,add_k] \]考虑逐个处理这些操作的过程。当处理到操作 \(i\) 的时候，这个节点的最大值一定会变成 \(v+add_1+add_2+\cdots+add_i\)（我们引入 \(add\) 序列的前缀和序列 \(sum\)，则改记为 \(v+sum_i\)），但是历史最大值则不然。
为什么历史最大值不一定是 \(v+sum_i\)？因为 \(v+sum_i\) 不一定是出现过的最大值。 \(add_i\) 可以为负数，从而 \(sum_i\) 不具有单调性。 但是我们可以发现，历史最大值一定是 \(\max\left(h,v+\max_{j=1}^{i}sum_j\right)\)。于是我们可以维护 \(mx=\max_{j=1}^{k}sum_j\)。
我们当然不可能模拟这个队列，不过现在我们已经可以维护新元素的入队过程了。当加入一个新的修改操作 \(add\) 的时候：
\[v\gets v+add \]\[sum\gets sum+add \]\[mx\gets \max\left(mx,sum\right) \]\[h\gets\max\left(h,v+mx\right) \]（想一想：一定要按照这个顺序更新吗？为什么？）
那么我们考虑两个队列的拼接，在线段树上体现为将父节点 \(i\) 的标记下放到子节点 \(l\)（将 \(add_i\) 接到 \(add_l\) 后面）。
子节点标记：
\[add_{l,1},add_{l,2},\cdots,add_{i,k_l} \]父节点标记：
\[add_{i,1},add_{i,},\cdots,add_{i,k_i} \]接起来：
\[add_{l,1},add_{l,2},\cdots,add_{l,k_l},add_{i,1},add_{i,2},\cdots,add_{i,k_i} \]考虑这个新的队列的前缀和。
\[sum_i\gets \begin{cases} sum_{l,i} & (1\leq i\leq k_l) \\ sum_{l,k}+sum_{i,i-k} & (k_l+1\leq i\leq k_l+k_i) \end{cases} \]考虑这个新的 \(mx_i\)。
\[mx_l\gets \max\begin{cases} \max_{i=1}^{k_l} sum_{l,i} \\ sum_{l,k}+\max_{i=1}^{k_i} sum_{i,i} \end{cases} \]即
\[mx_l\gets \max(mx_l,sum_l+mx_i) \]于是我们就能够处理两个队列的拼接了。
具体地，对于队列 \(add_l\) 和 \(add_i\) 的合并：
\[v_l\gets sum_l+sum_i \]\[mx_l\gets \max\left(mx_l,sum_l+mx_i\right) \]\[sum_l\gets sum_l+sum_i \]\[h_l\gets \max(h_l,v_l+mx_i) \]于是修改操作被解决了。
然后我们考虑带覆盖操作的情况。将题目中的两种修改统一成一种：\((a,b)\)，表示将 \(v\) 改为 \(\max(v+a,b)\)。那么区间覆盖就是 \((-\infty, x)\)，区间修改就是 \((x,-\infty)\)。
我们将\(v=\max(v+a,b)\) 的操作记为 \(v=v\times (a,b)\)。
先考虑两个标记的合并。\(v\) 依次 apply \((a,b)\) 与 \((a',b')\) 后变成了 \(\max\left(\max(v+a,b)+a',b'\right)=\max\left(v+a+a',b+a',b'\right)\)，与 apply 标记 \((a+a',\max(b+a',b'))\) 等效。故 \((a,b)\odot (a',b')=(a+a',\max(b+a',b'))\)。
我们还是和之前一样写出某节点的操作队列。
\[op_1,op_2,\cdots,op_k \]于是，\(k\) 次操作后，我们的 \(v\gets v\times \left(op_1\odot op_2\odot\cdots\odot op_k\right)\)。而历史最大值 \(h\) 更新为 \(\max(h,h+sum_{op}\text{ 中最大的 }a,sum_{op}\text{ 中最大的 } b)\)。
我们不妨定义 \(\max\left((a,b),(a',b')\right)=(\max(a,a'),\max(b,b'))\)。于是每次入队一个新元素的时候，我们令
\[v\gets v\times op \]\[sum\gets sum\odot op \]\[tag\gets \max(tag,sum) \]其中 \(tag=(a,b)\) 意为 \(sum_{op}\) 中最大的 \(a\) 和 \(sum_{op}\) 中最大的 $ b$。
如法炮制，考虑节点 \(i\) 的操作队列 \(op_i\) 下放给儿子 \(l\)（操作队列为 \(op_l\)）。
于是
\[sum_l=\begin{cases} sum_{l,k} & (k\leq k_l) \\ sum_{l,k_l}\odot sum_{i,k-k_l} & (k_l+1\leq k\leq k_l+k_i) \end{cases} \]而这需要我们的 \(\odot\) 操作具有结合律。我们来证明一下其具有结合律。
由定义有，\((a,b)\odot (a',b')=(a+a',\max(b+a',b'))\)
则
\[\begin{aligned} & \left((a_1,b_1)\odot(a_2,b_2)\right)\odot (a_3,b_3)\\ &=(a_1+a_2,\max(b_1+a_2,b_2))\odot (a_3,b_3)\\ &=(a_1+a_2+a_3,\max(\max(b_1+a_2,b_2)+a_3,b_3)) \\ &=(a_1+a_2+a_3,\max(b_1+a_2+a_3,b_2+a_3,b_3)) \end{aligned} \]而
\[\begin{aligned} & (a_1,b_1)\odot\left((a_2,b_2)\odot (a_3,b_3)\right)\\ &=(a_1,b_1)\odot(a_2+a_3,\max(b_2+a_3,b_3))\\ &=(a_1+a_2+a_3,\max(b_1+a_2+a_3,\max(b_2+a_3,b_3))) \\ &=(a_1+a_2+a_3,\max(b_1+a_2+a_3,b_2+a_3,b_3)) \end{aligned} \]证毕。
我们证明了 \(\odot\) 运算是具有结合律的，那么就可以放心玩弄啦~
那么于是 \(tag_l=\max(tag_l,sum_l\odot tag_i)\)。
于是 \(op_i\) 接在 \(op_l\) 后面的时候，我们有
\[tag_l\gets \max(tag_l,sum_l\odot tag_i) \]\[sum_l\gets sum_l\odot sum_i \]\[h_l\gets \max(h_l,v_l\times tag_i) \]\[v_l\gets v_l\odot sum_i \]（请仔细思考为什么是这个更新顺序。）
然后就做完了。时间复杂度为 \(\Theta(m\log n)\)。
GSS 系列
GSS1 - Can you answer these queries I
给定长度为 \(n\) 的序列 \(a\)，\(m\) 次询问 \([l,r]\) 内的最大子段和（可以为空）。
\(|a_i|\le 15,007\)，\(n,m\le 10^5\)。
显然用线段树维护，我们考虑在节点 \([l,r]\) 处需要维护哪些信息。
- \(mx\)。即 \([l,r]\) 内最大子段和。
- \(lmx\)。即 \([l,r]\) 内最大子段和，但是一定要选中左端点。
- \(rmx\)。即 \([l,r]\) 内最大子段和，但是一定要选中右端点。
- \(sum\)。即 \([l,r]\) 的区间和。
考虑信息的合并。以下的下标 \(l,r\) 表示左右儿子。
\[lmx\gets \max(lmx_l, sum_l+lmx_r) \]\[rmx\gets \max(rmx_r, sum_r+rmx_l) \]\[mx\gets \max(mx_l,mx_r,rmx_l+lmx_r) \]时间复杂度 \(\Theta(m\log n)\)。
GSS2 - Can you answer these queries II
给定长度为 \(n\) 的序列 \(a\)，\(m\) 次询问 \([l,r]\) 内的最大子段和（可以为空），但是相同的数只计算一次。
\(|a_i|\le 15,007\)，\(n,m\le 10^5\)。
受 P1972 的启发，由于相同的数只出现一次，套路地考虑扫描线。
GSS3 - Can you answer these queries III
给定长度为 \(n\) 的序列 \(a\)，\(m\) 次操作：
- 查询 \([l,r]\) 内的最大子段和（可以为空）。
- 或单点修改。
GSS 1 的双倍经验，只需要加上单点修改就可以了，而单点修改是容易的。
\(|a_i|\le 15,007\)，\(n,m\le 10^5\)。
GSS4 - Can you answer these queries IV
给定长度为 \(n\) 的序列 \(a\)，\(m\) 次操作：
- 查询区间和。
- 或 \(\forall i\in [l,r]\)，令 \(a_i\gets \lfloor {\sqrt a_i}\rfloor\)。
\(\sum a_i \le 10^{18}\)，\(n,m\le 10^5\)。
GSS5 - Can you answer these queries V
给定长度为 \(n\) 的序列 \(a\)，\(m\) 次操作：
- 给定 \(x_1,y_1,x_2,y_2\)，查询 \([l,r]\) 内的最大子段和，其中 \(l\in [x_1,y_1]\)，\(r\in [x_2,y_2]\)。不保证 \([x_1,y_1]\) 与 \([x_2,y_2]\) 不重合。
- 或单点修改。
\(|a_i|\le 15,007\)，\(n,m\le 10^5\)。
GSS6 - Can you answer these queries VI
给定长度为 \(n\) 的初始序列 \(a\)，\(m\) 次操作：
- 查询 \([l,r]\) 内的最大子段和。
- 或在任意位置插入一个元素。
- 或单点修改。
- 或在任意位置删除一个元素。
\(|a_i|\le 15,007\)，\(n,m\le 10^5\)。
GSS7 - Can you answer these queries VII
给定一棵 \(n\) 个节点的树，点有点权。\(m\) 次操作：
- 查询 \((u,v)\) 路径上的最大子段和，可以为空。
- 或 \((u,v)\) 路径上的点权覆盖。
\(n,m\le 10^5\)，\(|a_i|\le 10^4\)。
GSS8 - Can you answer these queries VIII
给定长度为 \(n\) 的初始序列 \(a\)，\(m\) 次操作：
- 给定 \(l,r,k\)，查询 \(\displaystyle \sum_{i=l}^r a_i\cdot (i-l+1)^k\) 的值，对 \(2^{32}\) 取模。
- 或在任意位置插入一个元素。
- 或单点修改。
- 或在任意位置删除一个元素。
\(0\le a_i\lt 2^{32}\)，\(n,m\le 10^5\)，\(0\le k\le 10\)。
莫队
P5071 [Ynoi2015] 此时此刻的光辉
Yuno OI 四血祭。
Chtholly 给你了一个长度为 \(n\) 的正整数序列 \(a\)，\(m\) 次查询
\[\sigma_0\left(\prod_{i=l}^r a_i\right) \]对 \(19,260,817\) 取模。
其中 \(\sigma_0\) 表示约数个数函数。\(n,m\leq 10^5\)，\(1 \leq a_i \leq10^9\)。
我们有经典的结论
\[\sigma_0(n)=\prod (c_i+1) \]其中 \(c_i\) 为 \(n\) 的唯一分解中第 \(i\) 个素数的指数。
类似上题莫队的做法，我们考虑根号分治。具体地，设置一个阈值 \(B\)，对于不大于 \(B\) 的素数，我们维护其 \(\sigma_0\) 的前缀积；对于大于 \(B\) 的素数，我们用 hash 表记录下其指数，直接在莫队的时候处理。为了让复杂度正确，需要预处理乘法逆元。
我们可以将 \(B\) 设置成 \(10^3\) 左右（这样 \(\le 10^3\) 的素数有 \(168\) 个）。时间复杂度为 \(\displaystyle\Theta\left(n\sqrt n+m\frac{\sqrt B}{\log \sqrt B}\right)\)。
需要中等程度的卡常。如果 unordered_map 被卡可以用 __gnu_pbds::gp_hash_table/cc_hash_table。