LXL DS tricks

单侧递归系列

区间函数复合

每个节点是一个函数，区间询问给定值通过 $l,\cdots,r$ 这些函数值变成什么。

两种思路，直接维护和标记回收，都是没有修改的情况。

直接维护就是维护一棵线段树，每个节点的信息量是区间长度。

标记回收则比较牛，对于若干询问进行扫描线，扫到 $l$ 的时候把询问的 $x$ 扔进数据结构，扫到 $r$ 的时候掏出来，每次右移的时候就把所有节点进行一个操作。

如果函数只有 $O(1)$ 个变化的点，我们可以直接并查集把所有变化并上，再新建点给失去了根的值。

P9999 [Ynoi2000] tmostnrq & 2d-travel

修改对询问的反演

常见的，前缀加单点查变成单点加前缀和，树上差分。

UOJ 637. [美团杯2021] A. 数据结构

给一个长为 $n$ 的序列， $m$ 次查询：

如果将区间 $[l,r]$ 中所有数都 $+1$ ，那么整个序列有多少个不同的数？

询问间独立，也就是说每次查询后这个修改都会被撤销。

考虑修改对查询的贡献，也就是我们要维护 $(l,r)$ 的答案平面。

一个数不出现当且仅当 $\forall a_i=x,i\in[l,r]$ ，且 $\forall a_{i}=x-1,i\notin [l,r]$ 。

不出现的贡献是一个矩形。

扫描线换维

说的很轻松，实际上不练过很难反应过来。

P3863 序列

给定一个长度为 $n$ 的序列，给出 $q$ 个操作，形如：

$1~l~r~x$ 表示将序列下标介于 $[l,r]$ 的元素加上 $x$ （请注意， $x$ 可能为负）

$2~p~y$ 表示查询 $a_p$ 在过去的多少秒时间内不小于 $y$ （不包括这一秒，细节请参照样例）

开始时为第 $0$ 秒，第 $i$ 个操作发生在第 $i$ 秒。

对于 $100\%$ 的数据，保证 $2 \leq n,q \leq 100000$ ， $1 \leq l \leq r \leq n$ ， $1 \leq p \leq n$ ， $-10^9 \leq x,y,a_i \leq 10^9$ 。

扫序列，维护时间轴，变成区间加区间 rnk，分块即可。

有一类特殊的换维，当我们遇到一个正常区间数据结构问题的时候，别忘了还有 $t$ 这一维，扫区间维护时间轴有时更好用。

P7560 [JOISC 2021 Day1] フードコート

有 $n$ 个队列。

$[l,r]$ 入队 $k$ 次 $c$ 。

$[l,r]$ 出队 $k$ 次，出完了就停。

求第 $a$ 个队列的第 $b$ 个人，没有这个人需要报告。

$n,q\le2.5\times1 0^5,k\le 10^9$ 。

有一个初步的思路是如果没有“出完了就停”，我们可以直接扔掉 $2$ 操作，转而改一改 $3$ 操作的 $\rm id$ 。

扔掉之后我们可以用整体二分来求出哪个操作导致了这个询问的警报。

或者再松一松，“没有这个人”的情况也不存在，那再加上没有出队，我们可以把询问移到最后处理，所以我们可以直接线段树维护区间 $\min$ ，然后直接警报。

那么如何保证没有这两种讨厌的情况呢，我们可以转而维护 $i$ 时刻的每个队列的长度，这样我们首先可以判掉“没有这个人”，然后也可以利用入队了多少次来求出扔掉 $2$ 操作后询问的偏移量。

维护长度只需支持区间加，区间对 $0$ 取 $\max$ ，这个东西是单 $\log$ 的。

需要注意，如果仅仅是区间取 $\max$ ，区间取 $\min$ ，区间求 $\max$ ，区间求 $\min$ ，区间加，这是可以单 $\log$ 的，只有求区间和这种阴间东西的时候才需要 beats，带上区间加就 $\log^2$ 。

本题当然也可以换维，维护时间轴，需要支持单点修改，我们还需要找到最后一个队列为空的时刻，事实上就是后缀最大值。

显然这个时刻是空，因为如果此时非空前面还有一个空时刻，那么加上中间这段正数必定优，且后面不会是空，否则可以抛弃一段非正。

求出这个时刻后只需求出 pop 的总数，在 push 上线段树二分即可。