随便写一些算法（三）

树状数组上的二分

题目大意，给你 $n$ 个数，两种操作，第一种是修改 $a_x = d$
第二种是查询最大的 $T, T \in [0, n]$ 满足 $\displaystyle \sum_{i = 1}^{T} a_i \leqslant s$

树状数组二分算法描述如下，从高位往低位去遍历树状数组
用一个 $\text{pos}$ 去记录一下当前在树状数组 $C[\cdots]$ 的哪个位置
用一个 $t$ 去记录前缀和

$\displaystyle \textbf{for} \quad j \in \left\lceil \log n\right\rceil \to 0$
$\displaystyle \quad pos' \leftarrow pos + 2^j$
$\displaystyle \quad \textbf{if} \quad t + C[pos'] \leqslant s: pos \leftarrow pos', t += C[pos']$

算法实现原理
当 $pos$ 在第 $j$ 位的时候，此时下标满足第 $j$ 位以后都是 $0$，即有形式
$pos:\quad ?\ ?\ ? \ 0 \ 0\cdots 0$，将 $pos' \leftarrow pos + 2^j$, 相当于将第 $j$ 位置为 $1$
$pos': \quad ?\ ? \ ? \ 1 \ 0 \cdots 0$，可以看到 $C[pos']$ 恰好对应了原数组下标
$[(? \ ? \ ? \ 0 \ 0 \cdots 1 ) \to ( ? \ ? \ ? \ 1 \ 0 \cdots 0)]$

换句话说，$C[pos']$ 恰好对应原来数组中下标 $[pos+1\cdots pos']$ 的和
如果加到 $pos'$ 仍然不超过 $s$，那么就将这部分和加入到答案中

二维树状数组

与一维类似，二维树状数组的 $C(i, j)$ 维护的是
原数组下标范围 $\displaystyle a([i-\text{lowbit}(i)+1\cdots i], [j - \text{lowbit}(j)+1 \cdots j])$ 的和
对一维数组稍作修改，两个 $\text{for}$ 循环求和即可

线段树维护最大子段和

带区间修改的最大子段和维护，可以用线段树
假设线段树节点 $p$ 对应的区间最大子段和记为 $\text{mss}$

那么它的最大子段只可能来自 $3$ 个部分，分别是
左边的最大子段和，右边的最大子段和，左边的最大后缀加上右边的最大前缀

$\text{mss} = \max(l.\text{mss}, \quad r.\text{mss}, \quad l.\text{msuf} + r.\text{mpre})$
其中 $\text{msuf}, \text{mpre}$ 也要分别维护出来
一个节点的最大后缀，它要么是右边的最大后缀，要么是右边一整段的和加上左边的最大后缀

$\text{msuf} = \max(r.\text{msuf}, \quad r.sum + l.\text{msuf})$
$\text{mpre} = \max(l.\text{mpre}, \quad l.sum + r.\text{mpre})$
$sum = l.sum + r.sum$

这些信息分别维护出来就可以

线段树懒标记编程技巧

线段树处理懒标记的时候，应该让标记尽量少
比如假设有 $3$ 种操作，分别是区间 $+d$，区间 $\times d$，以及区间赋值成 $d$

那么可以考虑将这三种操作统一起来

假设用一个标记 $\textbf{tag}(a, b)$，类似矩阵变换 $\textbf{tag} \cdot x$ 表示将 $\textbf{tag}$ 作用在 $x$ 上
那么 $x \leftarrow x \cdot a + b$

这样区间 $+d$ 的操作打标记的时候，相当于 $\textbf{tag}(1, d)$
区间 $\times d$ 的操作打标记，相当于 $\textbf{tag}(d, 0)$
区间整体赋值成 $d$，相当于 $\textbf{tag}(0, d)$

接着考虑两件事情，分别是标记合并和信息更新
首先看信息更新，假设是对当前区间 $p$ 作用了 $\textbf{tag}(a, b)$
那么每一个数都变成 $x \leftarrow x \cdot a + b$，维护的区间和变成

$\displaystyle \left(\sum x \right) a + p.sz \times b$，即 $sum \leftarrow sum \cdot a + p.sz \times b$

考虑标记合并，假设当前两个标记 $\text{tg1}(a_1, b_1), \text{tg2}(a_2, b_2)$，因为矩阵乘法是不能交换的
不妨设原来标记是 $\text{tg1}(a_1, b_1)$，新标记是 $\text{tg2}(a_2, b_2)$，那么

$x \leftarrow (x \times a_1 + b_1) \times a_2 + b_2$，合并之后
$x \leftarrow x \times (a_1 \cdot a_2) + b_1 \cdot a_2 + b_2$
由此新的标记是 $\text{tg}(a_1 \cdot a_2, \quad b_1 \cdot a_2 + b_2)$

最后注意的是，标记清空的标志是 $tag = \textbf{tag}(1, 0)$
线段树建树的时候，也要初始化 $\textbf{tag}(1, 0)$

线段树上二分

问题描述，给你一个序列，支持单点修改，能够修改 $a_x = d$
给你 $q$ 个询问，问在 $[l, r]$ 上第一个 $\geqslant d$ 的位置 $pos$，不存在就返回 $-1$

可以用线段树维护一个区间最大值 $maxv$，对于每个询问，在线段树上查询 $[l, r]$

如果线段树当前区间和 $[l, r]$ 重合，并且当前区间的 $maxv < d$，那么当前区间是不可能有 $\geqslant d$ 的数的
直接返回 $-1$，否则的话一定能找到这样的 $pos$
接着优先去左边找，左边没有就去右边找

如果当前区间 $l = r$，那么直接返回 $l$，否则的话，继续递归
如果左儿子的 $l.maxv \geqslant d$，那么递归左儿子，返回 $\text{search}(p\ll 1, l, mid, d)$
否则返回 $\text{search}(p \ll 1+1, mid+1, r, d)$

如果当前区间需要分裂，同时递归左右子树，那么先递归左子树
记一下 $pos = \text{search}(p \ll 1, l, mid, d)$，如果 $pos \neq -1$ 立即返回 $pos$
否则就返回 $\text{search}(p \ll 1 + 1, mid+1, r, d)$

动态开点线段树

NOIP2017 列队

算法分析
本例中需要支持如下操作，在 $n \times m$ 的方阵中，如果让 $(x, y)$ 出方阵，那么

• 找到标号第 $x$ 大的行，并且在该行中找到第 $y$ 大的列，将对应的元素 $(x, y)$ 取出
  然后把该行中 $[y+1\cdots m]$ 整体往前挪一位
• 然后操作第 $m$ 列，将第 $m$ 列 $[x+1\cdots n]$ 整体往上挪一位
• 最后把取出来的元素插入 $(n, m)$ 处

注意到我们需要对 $n$ 行，以及第 $m$ 列求前缀第 $k$ 大
可以考虑一开始建 $n+1$ 棵线段树，其中每一棵线段树初始只有一个根节点
这样第 $[1\cdots n]$ 棵线段树维护 $[1 \to n]$ 行，第 $n+1$ 棵线段树维护第 $m$ 列

将线段树写成动态开点，这样就可以尝试维护操作了，维护区间内被删除了多少个数 $cnt$

• 对于删除 $(x, y)$，就是在第 $x$ 棵线段树 $tr(x)$ 中找到第 $y$ 大的数 $p$，然后返回 $p$
  如果要对应到方阵中的编号，那么就是 $id = (x-1)\cdot m + p$
  然后删除这个点，采用懒惰删除的方法，对线段树这个点标记为删除，即 $u.\text{cnt} + 1$
• 值得注意的是，懒惰删除的时候，和一般线段树不一样，我们 $\text{pull}(u)$ 的时候
  因为是动态开点的，$u$ 的左子树或者右子树可能不存在，要加判一下子树存在
  以左子树为例，如果 $u.l \neq \text{null}$，那么直接 $u.\text{cnt} += u.l.\text{cnt}$
  否则的话左子树不存在，也就是说我们并没有修改过左子树对应的区间，$u.\text{cnt} += 0$
• 修改的时候，比如要出列第 $y$ 个人，只需要把 $root \to y$ 路径上的点都开出来就可以
  唯一需要注意的是，递归子树的时候，如果子树是 $\textbf{null}$，那么要先 $\textbf{new}$ 出来节点然后递归
• 接着考虑查询第 $k$ 大，同样需注意，递归子树遇到 $\textbf{null}$ 要先将其 $\textbf{new}$ 出来
  假设当前递归到 $(u, l, r)$，那么左子树中的元素个数是 $tot = mid - l + 1$
  如果左子树非空，那么 $tot$ 还要扣除掉已经删除的元素，即 $tot -= u.l.\text{cnt}$
  否则，说明左子树对应的区间我们没有修改过，自然对应的 $\text{cnt} = 0$
• 然后执行很常见的二分查找逻辑，如果 $k \leqslant tot$，那么在左子树查找第 $k$ 大
  否则去右子树找第 $k - tot$ 大

综上所述

• 通过线段树维护，可以得到要出列的点编号，假设是 $id = (x-1) \cdot m + y$
  可以用一个 $\text{vector}$ 存储被取出的点，$\text{vector}[x] \leftarrow \{y\}$ 表示
  第 $x$ 棵线段树被删除点的情况就存储到 $\text{vector}[x]$ 中
• 接着是查询第 $x$ 大的下标 $p$，如果是叶子节点，就直接返回 $p = l$，否则二分查询左右子树
• 接下来有一些坑点，注意到对 $x$ 行修改，得到的前 $y$ 大 $\in [1, m-1]$
  最后一列我们是单独拿出来处理的，如果 $p \geqslant m$，那么查询到的这个人是
  “向左看齐” 之后由最后一列第 $x$ 大填补空缺补充上来的
• 由此对 $(x, y)$ 出列操作，还需要额外维护最后一列填补空缺的人的编号
  即在第 $n+1$ 棵线段树中查找第 $x$ 大，此时这个编号的人不需要出列，而是填补空缺

由此程序实现需要注意的

• 对最后一列操作，即第 $n+1$ 棵线段树，维护两种情况
• 第一种是 $solve(1)$
  这一列的第 $x$ 个人出列，此时 $\text{vector}[n+1] \leftarrow \{x\}$，这个人要重新插入到末尾
• 另外一种是 $solve(0)$
  前 $m-1$ 列的人出队，假设说是 $(x, y)$，在第 $n+1$ 棵线段树找到第 $x$ 大之后
  这个人是要填补空缺的，不需要真正出列，不需要将其放在 $\text{vector}[n+1]$ 的末尾
  而是要放到 $\text{vector}[x]$ 的末尾
• 对其他列操作，加入是 $(x, y)$，在第 $x$ 棵线段树中找到第 $y$ 大的编号 $id$，做两件事情
  第一是在将 $id$ 加入到第 $n+1$ 棵线段树对应的 $\text{vector}$ 末尾，即 $\text{vector}[n+1] \leftarrow \{id\}$
  第二就是填补空缺，在第 $n+1$ 棵线段树中找到第 $x$ 大的编号 $id2$，$\text{vector}[x] \leftarrow \{id2\}$

这样所有信息都维护好了

• 如果对第 $m$ 列操作，查询第 $x$ 大的下标是 $p$，$p \leqslant n$ 直接返回 $p$
  否则是出列过之后又进来的，返回 $\text{vector}[n+1][p-n-1]$
• 如果对让 $(x, y)$ 出列，$x \leqslant m-1$，那么同样查询第 $y$ 大的下标 $p$
  $p \leqslant m-1$ 直接返回，否则返回 $\text{vector}[x][p-m]$

珂朵莉树

珂朵莉树可以较快地实现

• 区间加
• 区间赋值
• 区间第 $k$ 大
• 求区间 $n$ 次方的和

珂朵莉树特别擅长处理区间 $[l, r]$ 之间数的值都是 $v$ 的情况
因为区间处理会把大量的数变成同一个数
用一个三元组 $\left<l, r, v \right>$ 表示区间 $[l, r]$ 的元素值都是 $v$

对三元组按区间左端点排序

struct Node {
    int l, r;
    mutable long long v;
    Node(int l, int r, long long v) : l(l), r(r), v(v) {}
    bool operator< (const Node &rhs) const {
        return l < rhs.l;
    }
};

区间分裂
区间操作常常需要把原本连续的区间断开，$\displaystyle \left<l, r, v\right> \to \left<l, pos-1, v \right> \cup \left<pos, r, v \right>$
将 Node 用 set 来维护的话很容易实现，我们按左端点排序
只需要找到右边第一个 $\geqslant pos$ 的元素 $it$

• 如果已经存在以 $pos$ 为左端点的区间，直接返回
• 否则，令 $it\leftarrow it-1$，则此时 $it$ 代表的区间就是 $[l\cdots pos \cdots r]$，为待分裂的区间
  将 $it$ 从 set 中删除，并且加入 $\left<l, pos-1, v \right>, \left<pos, r, v \right>$

return tr.insert(Node(pos, r, v)).first
返回插入的位置

区间赋值
将 $[l, r]$ 从原序列中分裂出来，然后在 set 中删掉 $[l, r]$
将新的值 $\left<l, r, now \right>$ 插入 set

区间加
同样采用暴力的方式，将 $[l, r]$ 从序列中断开，挨个加

void add(int l, int r, long long v) {
    auto end = split(r+1);
    for (auto it = split(l); it != end; it++) {
        it->v += v;
    }
}

区间第 k 大
同样先将 $[l, r]$ 分离出来，具体分离的操作如下

auto end = split(r+1);
for (auto it = split(l); it != end; it++)

这样每一次迭代器 $it$ 就分离出区间的第一个节点，用一个二元组 $(v, len)$ 来表示
区间的值都是 $v$，并且区间的长度为 $len$，将二元组放入到一个 $\text{vector}$ 中

二元组按值 $v$ 排序，求区间第 $k$ 大就很容易了

for (auto u : v) {
    k -= u.second;
    if (k <= 0) return u..first;
}

求区间所有数的 n 次方的和
同样分离区间，然后对 $x = \text{power}(x, n)$，再乘上区间长度即可

long long sum = 0;
auto end = split(r+1);

for (auto it = split(l); it != end; it++) {
    tot = tot + power(it->v, n) * (it->r - it->l + 1);
}

CF915E Physical Education Lessons
题目大意，现在到学期结束还有 $n$ 天，他们一开始都是工作日，接下来工作人员发出 $q$ 个指令
每个指令用 $(l, r, k)$ 描述
如果 $k = 1$，那么 $[l, r]$ 所有日子都变成非工作日
如果 $k = 2$，那么 $[l, r]$ 所有日子都是工作日
统计每个指令下发后，剩余工作日的天数

算法分析
一开始记一下所有日子都是工作日 $sum = n$
对于操作 $1$，相当于区间 $[l, r]$ 赋值成 $k$，同时 $\text{split}$ 的时候记一下 $len$ 表示区间内一共有多少个数
编程实现的时候用到了一个技巧
工作日赋值成 $1$，非工作日赋值成 $0$，假设区间长度是 $len$
这样 $v \cdot len$ 恰好就能表示区间内有多少个工作日了

这样对于每一个询问可以维护出 $[l, r]$ 中有多少个数 $len$

• 对于 $k = 2$，将所有日子都变成工作日，我们把 $[l, r]$ 区间所有数都赋值成 $1$
  那么我们需要知道哪些数原本就是 $1$（工作日），而原来就是工作日的数有 $tot = \sum v \cdot len$ 个
  这样 $\sum len - \sum v\cdot len$ 就是新增加的工作日天数，将其加入到答案中
• 对于 $k = 1$，将所有日子变成非工作日，区间内所有 $1$ 的数有多少个呢？恰好就是 $tot$ 个
  于是在答案中减去 $tot$ 即可