好像还有一些关心的小问题，但是太懒了，就懒得写了。暂时完结。
-1. Disclaimer
有很多的算法和内容来自于和 GPT-6 Astra 的讨论。
已经把纯 aigc，还没有 review 过的部分放到附录里了。
0. Retroactive Priority Queue 和 Convex Bipartite Graph 的定义
自己查一下。
1. 日程管理, Partially Retroactive Priority Queue
这个东西其实非常简单，但是不知道网上的讲稿都在放什么狗屁。
1.1 日程管理 或者 Dynamic Scheduling
考虑一个 Retroactive PQ 的一个特殊形式，容易得到这个形式和一般形式完全等价。
- 一共有 $m$ 个时刻，每个时刻会首先执行若干次
push(x)这样的操作，然后做一次pop()。 - 可以对 push 操作修改，比如加入或者删除一条记录。
如果你只需要知道最终队列的状态，那么等价于 Partially Retroactive PQ。如果想知道某个时刻的队列状态，那么等价于 Fully Retroactive PQ。
首先这个 Partially Retroactive PQ 显然与日程管理等价，只需要把时间倒过来就行。所以我们花 0 分钟，学会了 Partially Retroactive PQ。
1.2 Dynamic Adjustment
容易发现，写成贪心之后，约等于执行 push(a[i]); push(a[i]); pop()，维护最后的答案，等价于 Partially Retroactive PQ。
注意如果要对 pop 操作进行修改，那么可以插入或删除一条虚拟的 push(-inf) 即可。
1.3 Unevenness
前面是对偶和凸 DP，略。转化完，单组询问为
// 其中 1 <= g[i] <= 2, a[i] 会发生变化，d[i] 不变。
ll solve(int n, const int a[], const int g[], const int d[]) {
multiset<ll> s;
ll b = 0;
int m = 0;
for (int i = 1; i <= n; ++i) {
b -= g[i] * a[i];
m += g[i];
for (int j = 0; j < 2 * g[i]; ++j)
s.insert(a[i]);
while (m > d[i]) {
auto it = s.begin();
s.erase(it);
it = prev(s.end());
b += *it;
s.erase(it);
--m;
}
}
return b;
}我们发现了，这个问题，需要在头尾删除元素，然后 push 的值 a[i] 会发生变化。这个似乎比较难以转化到标准的 Partially Retroactive PQ 的形式。
所以问题大概为，有若干个 push, pop_min, pop_max 操作，你只会修改 push 的值，求所有 pop_max 的和。
我们可以把 pop_max 的元素理解成选中，pop_min 的元素理解成不选中，所以问题等价于对于每个前缀，你能选中的个数有一个上下界。即 pop_max 表示你至少要选几个，pop_min 表示你至多只能选几个。
那么类似日程管理，维护一下每个前缀和上下界的余量，每次发生变化，你在有余量的区间内找到对应的最大未选元素/最小已选元素进行调整即可。
再把它显式转化成任务的版本：
- 把每个
pop_max，当成一个时间点。 - 我们把任务的时间理解成如果按
push顺序重拍，它是第几个被选中的，而不是实际被pop_max的时刻。 - 每个数对应的任务的起始编号等价于被
push进去前面已经选中了几个加 $1$。 - 假设某个时刻
push了 $p$ 个元素，执行了 $s$ 次pop_min，那么，前 $p$ 个元素的终止编号不能超过 $p-s$，每个元素取后续限制最小值即可。
所以在这个问题里面，每个任务的起始编号和终止编号都是单调的，我们只会修改每个任务的权值，并不会加入或删除任务。同理，对于一般的起始和终止时间单调的日程管理问题，也可以转化为这个模型。
如果一般的 push, pop_min, pop_max 操作，支持加入，删除 push 操作，而不是修改权值，会破坏问题的上下界结构，似乎是困难的。
如果看成二分图匹配，那么解决了点带权 convex 二分图，并且两端点都是单调的，支持点权修改的最大权匹配问题。同时，这个匹配中的拟阵结构，也说明了调整一项元素一定是对的。
1.4 可能的扩展
日程管理，前缀查询
加入对于某个前缀的查询。即动态询问如果做到第 $k$ 天，能获得最大收益。只需要额外维护选中的前 $k$ 大的任务之和即可。
人员调度
树形结构，每个任务能够匹配子树内的所有位置，支持插入删除任务，求最大收益。这个好像和 RPQ 本质上关系不大。为了完整性，aigc 的做法放在附录里。
人员调度，祖先版本
每个点匹配子树改成每个点匹配祖先。和下面的 Fully RPQ 的做法联系更大一点，请大家自行 aigc 一下题解。
2. Sushi, Fully Retroactive Priority Queue
省流：好像根本跑不过 $O(\sqrt{n} \log n)$。
沿用前面的设定，考虑大根堆，现在加入查询某个时刻被弹掉的元素到底是什么。因为 push 操作修改之后，整个堆的变化量是 $O(1)$ 的，但是每个时刻会发生改变。
我们默认值域为 $O(n)$，并且认为一开始堆里有足够多的 $-\infty$。
2.1 分块
把所有操作按 $B = O(\sqrt{n})$ 分块，这里先不考虑修改后每块大小不平衡的问题。
对于每个块，从空堆开始执行块内操作，用权值线段树维护两个集合：
- $S$：最后留下的元素。
- $D$：被弹掉的元素。
修改时只需要重建所在的块，复杂度为 $O(B\log n)$。
查询时，我们需要知道前面传进来的元素，经过一个块之后会变成什么。直接维护整个集合比较麻烦，我们考虑二分 $x$，即只关心大于某个值 $x$ 的元素个数。
假设进入这个块时有 $c$ 个元素大于 $x$，那么经过这个块之后：$c$ 变为 $|S_{>x}|+\max(0,c-|D_{\le x}|)$。
可以理解成，原来弹出不大于 $x$ 的元素的那些位置，可以用来消耗前面传进来的大元素；原来留下的大元素则仍然会留下。
对末尾不完整的块临时重建，从前往后扫一遍块，就能知道查询时刻是否还存在大于 $x$ 的元素。因为我们使用权值线段树，那么可以在权值线段树上一起二分，每层都重新扫一遍即可。
查询复杂度为 $O((n/B+B)\log n)$。
对于一般性带增加删除的，这个做法看起来跑不过 $O(\log^2 n)$ 的。如果要后面的简化版分块做法，应该需要在外面套一个线段树分治，那么 $O(\sqrt{n} \log^2 n)$ 应该也没有跑过 $O(\log^2 n)$ 的风险。
2.2 线段树
类比上面的结构，把分块改成时间轴上的线段树，每个节点同样维护对应区间独立执行得到的 $S,D$。
考虑左右两个区间怎么合并。左边已经弹掉的元素不会再回来，右边原本留下的元素也一定会留下。剩下需要考虑的，就是左边留下的 $S_L$ 和右边弹掉的 $D_R$。把 $S_L$ 和 $D_R$ 放在一起，其中最大的 $|D_R|$ 个作为右边弹掉的元素，其余元素继续留下。
所以只需要维护这个大小分界。一次修改只会影响一条链，而且每个节点的 $S,D$ 都只有 $O(1)$ 个元素发生变化。把子节点的变化传上来，在分界两侧调整常数个元素即可，不需要重新合并整个集合。这里具体细节见附录 2。
每个集合用值域线段树维护，单个节点的调整是 $O(\log n)$，所以修改复杂度为 $O(\log^2 n)$。
查询时，把所需的操作前缀拆成 $O(\log n)$ 个节点，按时间顺序使用分块时的数量转移。同样让这些节点的值域线段树一起二分，每层花 $O(\log n)$，总复杂度也是 $O(\log^2 n)$。
注意： - 似乎因为可以离散化值域的关系，学界的复杂度为 $O(\log^2 m \log \log m)$，我们做到了更好的复杂度 $O(\log ^2 m)$。 - 空间是 $O(m \log^2 m)$ 的，似乎非常大。可以用压位 Trie 省掉一个 log，但还是不小。
2.3 Sushi
省流：跑不过分块。
我们发现，假设维护一个序列 $a_i$ 表示每个时刻 pop的数字。那么当我们在 $t$ 时刻插入一个 push(x)，对于 $a_i$ 的变化为：
for i = t to n
if (a[i] > x) swap(a[i], x)所以区间冒泡排序几乎自然的和 RPQ 有相关性。
问题的操作可以等价为，在 $l$ 位置插入 push(x) 操作。然后找到冒泡带出的数字（即区间最大值），把它对应的插入删除即可。
悲报：在 $n, q = 2\times 10^5$ 的范围的区间冒泡排序中，Astra 拼尽全力，两个 log 跑不过根号 log。因为这个问题中本身性质比较好，插入和删除配对，相当于本质上不需要做删除一个元素，所以有简单分块做法。但是一般插入删除操作，没有区间冒泡排序这么简单的根号做法。
2.4 一些扩展
省流：还是跑不过分块。
因为用了二分来确定每个值，我们似乎没有真正维护这个 $a_i$ 序列。实际上，我们能通过每个节点记录的 $S, D$ 某些程度上还原这个序列更多的信息。
考虑一个简单的扩展问题：
- 支持类似 Sushi 的对于一个区间，加入一个数冒泡排序。
- 求区间最大值。
- 求区间和。
区间最大值，原生 RPQ 就支持，只需要把原来查询时候对前缀二分，改成对区间内所有线段树节点二分即可。
下面的求和的做法好像也是 aigc 的，还没仔细看，加入附录 3。
2.5 可以做什么？做不了什么？
可以做的问题
- 日程管理，后缀查询：加入对于某个后缀的查询。即动态询问如果从第 $k$ 天开始工作，能获得最大收益。这个等价于 Fully RPQ。
- 把前面的一些其他题，加个前缀查询，应该也是可以做的。
稳健型选手：相当于没有修改的版本。只需要把 Fully RPQ 的做法，外层从线段树改成分治即可。分治之后保留每个左边每个后缀，右边每个前缀的 $S, D$，合并可以在可持久化线段树上二分，做到一个查询 log 时间复杂度。
不可以做的问题
本质上，Fully RPQ 修改等价于 $O(\log n)$ 个 Partially RPQ 修改，所以能做的事情局限在 Partially RPQ 能够快速回答的部分。
- 也就是我们更多地只能知道整体的信息，很难完全知道内部具体的变化方式。比如上一个问题如果维护 $\sum i \cdot a_i$，应该是没法做到的。
3. Conference, Convex Bipartite Graph Matching
说人话，考虑一类二分图匹配问题，左边每个点连向右边一个区间。也就是任务带起始时间和终止时间版本的日程管理问题。这些问题除了需要用到 RPQ，有的时候还需要比较深刻的二分图匹配相关的 insight，更加的深邃黑暗。
3.1 Conference
有个比较巧妙的方法，对于所有 $l_i$ 相同的任务，保留 $r_i$ 最小的一个，其他所有任务的左端点加一。实际上这个 idea 能做一些更加困难的问题，我们来重新审视一下这个想法，并且给出若干扩展。
这和前面的堆的设定是非常类似的。所以对于涉及权值，或者支持动态增删的问题，和 RPQ 有比较深刻的联系。好像暂时没有了。
补充一下：这个问题里，对日期做 Hall，只有把所有任务处理成端点不同才对。但是对任务这一侧做 Hall，只需要考虑日期的区间即可。
3.2 静态，无权，多组查询
具体设定：有若干个任务，每个任务都有起始终止日期 $l_i, r_i$。$q$ 个询问，每次询问 $[L, R]$ 这段日期最多能完成多少任务。
在 Conference 只需要双指针判断是否有完备匹配即可，这个问题严格强于上面问题。
可以继续沿用上文的做法，先处理左端点：相同左端点的任务，保留右端点最小的一个，剩下的左端点加一，直到所有左端点互不相同。右端点反过来同理：相同右端点的任务，保留左端点最大的一个，剩下的右端点减一。过程中变成空区间的任务直接删掉。下面把这个过程称为离散化。
两遍做完，剩下的任务左右端点分别互不相同。设与询问区间相交的任务有 $k$ 个，那么答案就是$\min(R-L+1,k)$。证明直接照抄 Conference 的 Hall 定理证明即可。
而相交的任务，只需要减去操作完 $r_i < L$ 和 $l_i > R$ 的任务即可。
3.3 静态，带权，单组查询
具体设定：有若干个任务，每个任务有起始终止日期 $l_i,r_i$ 和收益 $w_i$，问最大总收益。
一个显然的方向是，按照权值从大到小做，动态加入，然后 somehow 维护 Hall 定理的条件。但是直接 Hall 要考虑所有的区间，这个可能不那么简单。
有一个简单做法，把任务按照右端点从小到大加入。因为前面都是合法的，所以只需要考虑当前端点 $r$ 对应的 Hall 条件即可。所以可以像日程管理一样，维护每个左端点的余量，然后看能不能直接加入或者选择便宜的替换即可。
这样就可以做到 $O(n \log n)$ 的时间复杂度。
3.4 静态，带权，多组查询
GPT-6 Astar Max 只能两个 log？玩的太差了！
具体设定：有若干个任务，每个任务都有起始终止日期 $l_i, r_i$ 和收益 $w_i$。$q$ 个询问每次询问 $[L, R]$ 这段日期的最大总收益。
回到从大到小加入这个想法，记 $f(L, R, k)$ 表示收益大于等于 $k$ 的区间能选多少个，那么答案显然为 $\sum_{k\geq 1} f(L, R, k)$。
考虑 $p(L, k)$ 表示加入了所有大于等于 $k$ 的区间之后，经过离散化之后右端点小于 $L$ 的任务数，同理定义 $s(R, k)$。$t(k)$ 表示所有大于等于 $k$ 的区间，离散化之后非空区间个数。
可以首先求出最大的 $k_0$ 满足 $f(L, R, k_0) \geq R-L+1$，那么答案就是 $\sum_{k=1}^{k_0} (R-L+1) + \sum_{k\geq k_0+1} (t(k) - p(L,k) - s(R, k))$。
首先考虑 $t(k)$，等价于每次加入一个区间之后，匹配会不会增加。这个可以由 3.3 中的方法，求出所有区间之后解决。
对于 $t(k)$ 无法增加的区间，我们直接扔了即可。对于剩下的区间，我们能够保证经过离散化之后区间一定非空，于是左右端点的变化可以认为是独立的。考虑左端点，这个离散化的过程，等价于每个区间找到一个最靠左的左端点加入，于是可以认为，新增的左端点 $l$ 是大于等于加入区间左端点的第一个空位（可能会大于它的 $r_i$），新增的 $r$ 同理。
求出左右端点每个位置被占据的时间，然后用可持久化线段树维护 $p(L, k), s(R, k)$ 即可。整个问题可以做到 $O(n\log n)$ 时间复杂度。
3.5 动态，无权，整体查询
具体设定：有若干个任务，每个任务都有起始终止日期 $l_i, r_i$。支持加入，删除任务，询问最多能完成多少任务。
考虑贪心，等价于每次加入在 $l_i$ 时刻，加入截止日期为 $r_i$ 的任务，每天完成截止日期最早的任务。和 RPQ 相比，额外多了每天要扔掉过期的任务。
类似 Fully RPQ，对于时间建线段树，每个节点单独考虑起始时间在内部的任务，记录： - $S$：这段没完成，但截止时间没到，留到后面的任务。 - $D$：本段完成的任务。
合并的时候，只需要考虑 $S_L \cup D_R$，但是这里不能和 Fully RPQ 一样取最小值，还要满足右端点的限制。
这里有个比较神秘的观察：我们可以认为 $D_R$ 里所有任务的端点也是 $R$ 这一段的起点。大概的原因因为本来就可以完全匹配，用类似 Hall 的方法可以证明与起点无关。
于是维护 $S_L \cup D_R$ 这一部分，相当于你有若干个任务，有个截止日期，你要支持加入，删除任务，求出能安排哪些任务以及变化量。这个等价于普通的日程管理问题，也就是可以用 Partially RPQ 解决。
在线段树上把所有修改都求出来，然后往上传递即可。根据拟阵限制，一次修改之后，每个节点发生的变化都是 $O(1)$ 的。整体复杂度为修改 $O(\log^2 n)$，查询 $O(1)$。
区间查询能做到 $O(\log n)$，请大家自行 aigc。
3.6 动态，带权，整体查询
具体设定：有若干个任务，每个任务都有起始终止日期 $l_i, r_i$ 和收益 $w_i$。支持加入，删除任务，询问最大总收益。
这个问题好像有一篇论文声称能做到 $O(q\log^2 n)$。根据 GPT 对着这篇论文的中文版研究了一下，这个论文完全是错的。
因为加入删除的时候，虽然每次只会替换一个任务，但是找到被替换的任务好像有点困难。这里考虑离线，类似离线最小生成树，对操作时间分治，提前处理掉这一段里面选不选已经确定的任务。
在递归的过程中，我们把任务分成三类：
- 没有发生过修改，一定被选入的任务 $A$。
- 没有发生过修改，但可能被选入的任务 $B$。
- 发生修改的任务 $C$。
一定不被选入的任务就不用考虑，并且保证 $A$ 中的任务已经全部被选入。
我们按照假设 $C$ 不存在单独加入 $B$ ，假设 $C$ 全部存在和 $B$ 一起加入，分别做一遍按收益从大到小的贪心。如果第一遍贪心过程中 $B$ 中没被选中的任务，那么一定不会被选入。如果第二遍贪心过程中 $B$ 中被选中的任务，那么一定会被选入。
所以只需要 $B$ 中考虑发生变化的任务，以及 $C$ 中的任务。而根据拟阵的性质，$B$ 中发生变化的任务最多只有 $|C|$ 个。所以问题会收缩到只有 $O(|C|)$ 的规模。
然后我们套一个全局性的支持加入删除的无权区间查询结构，把一定选入的任务加入到结构中，每次贪心就把需要判断的任务按顺序加入，做完之后撤回。
那么需要做 $O(q\log n)$ 次无权区间插入删除问题，整体时间复杂度为 $O(q \log^3 n)$。
区间查询能做到 $O(\log^2 n)$，请大家自行 aigc。
3.7 环上的扩展
无权的多组区间询问
首先对所有区间进行离散化，注意这里任选一个起点，然后扫两圈即可。设与询问区间相交的任务有 $k$ 个，那么答案就是$\min(R-L+1,k)$，这个结论依然成立，所以可以变成数点。
有权的单组询问
按照我的理解，根据 Insects 这个题，任意无权匹配加上沿着交错路找可达点集能做到 $O(M(n))$，那么带权匹配只需要多一个 log 就能做。
Astra claim 了可以做到 $O(n \log n)$，但是需要圆弧凸二分图的线性匹配，以及线性并查集之类的，本质上就是把分治之后把上面的东西全都做到了线性。
无权的多组动态询问
Astra claim 了可以怎么转化一下，用上面的区间的做法做，可以做到两个 log，具体懒得看了。请大家自行 aigc。
附录
附录 1. 人员调度做法
树上的版本，可以理解成把日程管理的前缀限制换成了子树限制。对于每个子树，起点在里面的已选任务个数，不能超过这个子树的大小。由 Hall 定理，这也是充分条件，因为子树之间只可能包含或者不交。
那么类似日程管理，维护一下每个子树的余量。选中一个任务，就把它的起点到根路径上的余量都减一；取消选中则加一。原来链上从截止日期到最后一天的余量修改，就变成了树上的路径修改。
- 加入任务时，从起点往根找到第一个没有余量的子树。如果没有，就直接选中；否则，在起点属于这个子树的已选任务里找到权值最小的，看看要不要替换。这和日程管理中找到最紧的前缀，再换掉里面最小的任务是一样的。
- 删除已选任务时，先恢复它占用的余量，再找一个能够加入的最大权未选任务补上。一个任务能够加入，就是它的起点到根一路都有余量。没有候选就不补，删除未选任务则不需要调整答案。
- 如果外面套一层线段树分治，没有删除操作，但是复杂度会多一个 log。这个删除操作，可以用动态 DP 的方法维护，但显然很不好写。
这里仍然有拟阵结构，所以一次修改只需要做一次这样的调整。也就是说，链上和树上的贪心其实没有变，变化的是约束从一串前缀变成了一族子树，以及对应的余量和最值怎么维护。可以看作 Partially RPQ 对应的日程管理模型的树上推广。
附录 2. 线段树维护的具体方法
我们来 aigc 一下具体的细节。
先解释为什么可以这样合并。考虑在右区间开始之前，额外放入一个元素 $x$。比较新旧两次执行，可以一直认为新堆比旧堆多一个元素 $c$，初始 $c=x$。
遇到 push，两边一起插入，差异不变。遇到 pop，假设原来弹出 $d$，现在就会弹出 $\max(c,d)$，继续携带 $\min(c,d)$。也就是大的弹掉，小的继续往后走。
所以，右区间原本留下的元素仍然会留下。如果右区间有 $k$ 次 pop，新的弹出集合就是 $D_R$ 和 $x$ 放在一起后最大的 $k$ 个，剩下的元素继续留下。把 $S_L$ 中的元素逐个这样放进去，就得到了前面的合并规则。
具体维护时，每个内部节点除了保存 $S,D$，再保存两个集合：
- $H$：$S_L$ 和 $D_R$ 放在一起后，最大的 $|D_R|$ 个元素。
- $T$：剩下的元素。
父节点的 $D$ 由 $D_L,H$ 合并得到，$S$ 由 $S_R,T$ 合并得到。集合均允许重复元素，加入 $S$ 时忽略虚拟的 $-\infty$。
记 $k=|D_R|$，需要始终满足 $|H|=k$，并且 $T$ 中的元素都不大于 $H$ 中的元素。只修改 push 时，$k$ 不变。
子节点发生变化之后：
- $D_L$ 的变化直接修改父节点的 $D$。
- $S_R$ 的变化直接修改父节点的 $S$。
- $S_L,D_R$ 的变化修改 $H,T$，再调整分界。
这里不需要重新合并集合，因为 $H,T$ 已经保存了上一次合并的结果。插入元素时，按当前分界放进对应的集合；删除元素时，从所在集合删掉。如果 $H$ 多于 $k$ 个元素，就把其中最小的移到 $T$；如果少于 $k$ 个，就把 $T$ 中最大的移到 $H$。
每次增删一个元素，只需要在分界处移动常数个元素。同步修改父节点的 $S,D$，再把它们的净变化继续向上传递即可。
最后说明一下，为什么变化量不会随着向上传递而扩大。
在一个区间内部加入一条 push，从插入位置开始，同样可以用前面的“携带一个元素”来描述。最终 $S$ 至多增加一个元素，$D$ 至多替换一个元素。删除是逆过程，修改权值则是删除再插入，所以每个区间的 $S,D$ 始终只有常数个元素发生变化。
因此，上传时把相互抵消的增删去掉，只传递最终的净变化，每层就只需要进行常数次集合操作。内层用值域线段树维护，单层复杂度为 $O(\log n)$，总修改复杂度为 $O(\log^2 n)$。
附录 3. 区间冒泡，求和的具体做法
求和仍然可以做到两个 log。先把区间和拆成两个前缀和。一个前缀弹出的总和，等于这个前缀所有 push 的总和，减去最后留下的元素之和。
把前缀拆成 $O(\log n)$ 个节点。每个节点的 $(S,D)$，可以理解成先加入 $D$，弹出规定数量的元素，再加入 $S$。忽略虚拟元素后，又回到了每个前缀留下的元素个数有上界的模型；我们要留下尽量多且总和最小的元素。各个上界可以由加入和弹出的数量直接算出。
设这些集合依次为 $G_1,\ldots,G_k$，前 $i$ 组至多留下 $b_i$ 个，$b_0=0$。对值域二分，设第 $i$ 组的小值有 $c_i$ 个。那么最多能留下的小值个数为 $R=\min_{0\le p\le k}(b_p+\sum_{i>p}c_i)$。
取一个达到最小值的位置 $p$。前 $p$ 组恰好留下 $b_p$ 个小值，后面各组的小值全部留下。因此，前 $p$ 组只递归小值一侧。后面的组直接加入小值的和，扣掉已经占用的名额，再递归大值一侧。值域线段树额外维护和即可。
这样虽然递归了值域的两边，但每一组在每层只进入一边。每层总共处理 $O(\log n)$ 组，查询复杂度为 $O(\log^2 n)$。修改仍然是原来的两个 log。
