一些数据结构技巧

值域树状数组求 $k-th$

这里以第 $k$ 小为例。

首先不难发现一定会有 $k-1$ 个数比第 $k$ 小的数小，那么只需要找到最大的满足 $[-\inf,pos]$ 中数的个数等于 $k-1$ 的 $pos$ ，答案即为 $pos+1$ 。

考虑倍增求出 $pos$ ，显然由于树状数组维护的区间的长度是 $2$ 的次幂，所以可以从大往小枚举 $2$ 的次幂 $2^p$ 并尝试加上这段区间。

具体实现

inline int kth(int k) // 这里假设值域 [1,n]
{
	k--;
	int pos=0,sum=0;
	for(int j=20;j>=0;j--) // 需要保证 2^j>=n
	{
		if(pos+(1<<j)<=n&&sum+tr[pos+(1<<j)]<=k)
		{
			sum+=tr[pos+(1<<j)];
			pos+=1<<j;
		}
	}
	if(sum!=k-1)
	{
		return -1; // 没有
	}
	return pos+1>n?-1:pos+1; // pos+1>n 也是没有的情况
}

值域倍增分块

经常用于解决把所有 $a_i> x$ 的 $a_i$ 减去 $x$ 之类的东西。

例题：P7447 [Ynoi2007] rgxsxrs

题解

把值域分成 $[2^k,2^{k+1})$ 这样的 $\log$ 个块，那么每次修改就找到 $x$ 所在的块 $[2^y,2^{y+1})$ ：

对于所有满足 $z>y$ 的 $[2^z,2^{z+1})$ ：这些块将会集体减掉 $x$ ，那么维护每一块的最小值，暴力让该跌落的值跌落到更低的块；

对于所有满足 $z<y$ 的 $[2^z,2^{z+1})$ ：这些块没有任何改变；

对于 $[2^y,2^{y+1})$ ：这一块中所有满足 $a_i>x$ 的 $a_i$ 都会跌落到更低的块，那么维护块内最大值暴力让该跌落的值跌落；

由于每个数最多只会跌落 $\log V$ 次，所以时间复杂度为 $O(m\log V\log n+n\log V)$ 。

更多例题：

减半报警器

用于解决类似这样的问题：

维护一个数据结构，刚开始给了一些范围，每个范围有对应的权值。每次把包含一个点的范围的权值减去 $x$ ，维护每个范围的权值最早被减完的时刻。

例题：Codeforces GYM 102452I

有 $n$ 个国家，每个国家有权值 $w_i$ 和若干个（ $\le 3$ ）观测点。有 $q$ 次操作，每次会将所有能观测到 $x$ 的国家的 $w_i$ 减去 $y$ 。你要求出每个国家的权值第一次被减完是在第几次操作。

题解

观测点个数为 $1$ 的情况是最简单的，直接把 $w_i$ 挂到观测点上即可；

观测点个数为 $2$ 比较复杂，设这两个观测点为 $x$ 和 $y$ ，把 $\lceil\frac{w_i}{2}\rceil$ 挂到 $x$ 上， $\lceil\frac{w_i}{2}\rceil$ 挂到 $y$ 上。这样两边都没减完则 $w_i$ 一定没被减完，有一边被减完则判一下 $w_i$ 是否被减完，若没减完则重新平均分配。注意到每次 $w_i$ 至少减半，所以最多重新分配 $\log V$ 次，均摊时间复杂度 $O(n\log V)$ ；

观测点个数 $3$ 的情况和观测点个数为 $2$ 的情况一样，只需要把 $w_i$ 平均分成三份，注意到每次重新分配会让 $w_i$ 变成原来的 $\frac{2}{3}$ ，那么均摊时间复杂度为 $O(n\log_{1.5}V)$ 。

每次操作的时间复杂度为 $O(\log n)$ ，那么总时间复杂度即为 $O(q\log n+n\log_{1.5}V)$ 。

注意挂的一定是向上取整的值，否则会出现 $(1,0,0)$ 这种尴尬情况。

例题 2：Codeforces GYM 104065B

你要邀请 $n$ 个人来参加会议，一个人同意参加当且仅当已经有至少 $k_i$ 个编号在 $[l_i,r_i]$ 内的人来参加，问最多能有多少个人参加。

也就是说你要确定一个邀请人的顺序。

题解

转换后的题意相当于给定了 $m$ 个区间，第 $i$ 个区间的权值为 $k_i$ ，你需要动态维护这样的过程：

找到 $k_i\le 0$ 的某个区间 $i$ ；

把它删掉，答案加一，同时将所有包含 $i$ 的区间的 $k_i$ 都减去 $1$ ；

考虑所有区间都包含某个位置 $p$ 的特殊情况，那么每个区间都可以被分成 $[l_i,p]$ 和 $[p+1,r_i]$ 两段。可以把 $k_i$ 平均分到这两段上，每一次修改操作相当于找到左边的一个后缀或者右边的一个前缀减掉 $1$ 。

这样若一个区间的某一边被减完了则重新分配剩下的 $k_i$ ，每次至少减半，均摊时间复杂度为 $O(n\log V)$ 。

用线段树动态维护这个东西，每次区间减，暴力找到需要重构的区间编号即可。

若所有区间没有包含共同的位置，那么可以把区间分成三类：

包含 $\lfloor\frac{n}{2}\rfloor$ 的；

在 $\lfloor\frac{n}{2}\rfloor$ 左边的；

在 $\lfloor\frac{n}{2}\rfloor$ 右边的；

这是一个类似线段树的结构，那么分治下去，每次修改都不断往 $x$ 的方向走，改一下包含当前分治中心 $mid$ 的区间。

一次修改会分治 $O(\log n)$ 次，每次分治的时间复杂度为 $O(\log n)$ ，那么总的时间复杂度即为 $O(n\log^2n+n\log V)$ 。

更多例题：

P7603 [THUPC2021] 鬼街
Codeforces GYM 102331F
【2025NOI模拟赛27】防御

支配

$x$ 满足的条件包含 $y$ 满足的条件，并且 $x$ 的值比 $y$ 的优，那么 $y$ 就没有存在的必要了。

——《单调队列》

关于距离的支配

序列上

CF765F Souvenirs / CF1793F Rebrending

题解

CF 自己抄自己，两道题一模一样。

先假设只有 $i<j$ 且 $a_i<a_j$ 的 $(i,j)$ 有贡献，另一种取值再跑一次即可。

注意到若 $(i1,j1)$ 和 $(i2,j2)$ （ $i1<j2$ ， $i2<j2$ ）若满足 $a_{i1}-a_{j1}\le a_{i2}-a_{j2}$ 且 $i1\ge i2$ ， $j1\le j2$ 则 $(i2,j2)$ 被 $(i1,j1)$ 完全包含了，即 $(i1,j1)$ 支配了 $(i2,j2)$ ，所以只用统计 $(i1,j1)$ 的贡献。

固定 $i$ ，考虑找到所有有用的 $j$ 。设 $S_i=\{j|(i,j)\text{ 未被支配}\}$ ，考虑增量求解 $S_i$ ，设 $p=\max\{j|j\in S_i\}$ ，那么 $k$ （ $k>p$ ）想要加入 $S_i$ 就必须满足：

$a_k-a_i<a_p-a_i\Rightarrow a_k<a_p$ ；

$a_k-a_i<|a_p-a_k|\Rightarrow a_k-a_i<a_p-a_k\Rightarrow a_k<\frac{a_p+a_i}{2}$ ；

所以 $|S_i|$ 是 $\log V$ 级别的，那么未被支配的 $(i,j)$ 也就只有 $n\log V$ 个。

接下来就变成二维数点问题了，扫描线即可，时间复杂度 $O((q+n\log V)\log n)$ 。

树上

P9058 [Ynoi2004] rpmtdq

题解

考虑点分治，对于来自分治中心 $rt$ 不同两个子树中的两个点 $x,y$ ，显然有 $\operatorname{dis}(x,y)=\operatorname{dis}(x,rt)+\operatorname{dis}(y,rt)$ 。

那么不妨设 $a_u=\operatorname{dis}(u,rt)$ ，显然点对 $(i,j)$ （ $i<j$ ）未被支配当且仅当对于所有 $i<k<j$ 都有 $a_i+a_j<a_i+a_k$ 且 $a_i+a_j<a_k+a_j$ 。稍加化简可得 $a_i<a_k,a_j<a_k$ ， $\max(a_i,a_j)<a_k$ ，那么只有 $a_i$ 的前驱后继会和 $i$ 构成支配，所以每层分治每个点只会组成 $O(1)$ 个支配对，那么总支配对个数是 $O(n\log n)$ 的。

接下来就变成二维数点问题了，扫描线即可，时间复杂度 $O((q+n\log V)\log n)$ 。

一些特殊的支配

Mex 支配

对于一个长度为 $n$ 的序列 $a$ ，设 $b_{l,r}=\text{mex}_{l\le i\le r}\{a_i\}$ ，有性质：

$b_{l,r}\ge b_{l+1,r}$ ，证明显然；
$b_{*,r}\to b_{*,r+1}$ 相当于把所有 $b_{i,r}=a_{r+1}$ 的 $b_{i,r}$ 都修改为大于 $a_{r+1}$ 的数，由第一个性质，需要被修改的 $i$ 一定是在一个区间内，所以根据颜色段均摊的经典结论，所有 $r$ 造成的总修改数是 $O(n)$ 级别的；
满足不存在 $[l',r']\subset [l,r],b_{l',r'}=b_{l,r}$ 的区间 $[l,r]$ 个数最多有 $2n$ 个。

证明

对于每个满足条件的 $[l,r]$ ，显然 $a_l\not=a_r$ ，不妨假定 $a_l>a_r$ （另一种情况对称）。

现在来证明对于每个 $l$ ，都只有一个 $r$ 满足 $r>l,a_l>a_r$ 且 $[l,r]$ 满足条件。

考虑反证，设存在 $l<r1<r2$ 满足 $a_l>a_{r1},a_l>a_{r2}$ 且 $[l,r1]$ 与 $[l,r2]$ 均满足条件。显然由于 $[l,r1]$ 满足条件，一定有 $b_{l,r1}>a_l$ 。由于 $a_l>a_{r2}$ ，所以有 $b_{l,r1}>a_{r2}$ ，那么显然 $[l,r2-1]\sub [l,r2]$ 且 $b_{l,r2}=b_{l,r2-1}$ ，所以 $[l,r2]$ 不满足条件，矛盾。

那么对于每个位置 $i$ ，它作为 $a_{l}$ 和 $a_r$ 中最小值时最多有一个合法区间，作为最大值时也最多有一个合法区间，所以合法区间个数最多有 $2n$ 个。

Q.E.D.

三维计数技巧

对于满足某些条件的有序三元组 $(i,j,k)$ 且固定 $k$ 和 $j$ 后合法的 $i$ 在一段区间内时，可以考虑枚举 $k$ 同时维护每个 $j$ 对应的 $i$ 的合法区间 $[l_j,r_j]$ 。

例题：Nasty Donchik

题意：给定序列 $a_1,a_2,\dots,a_n$ ，求有多少有序三元组 $(i,j,k)$ 满足 $i\le j<k$ 且 $a_{[i,j]}$ 中出现的数集以及 $a_{[j+1,k]}$ 中出现的数放入两个不可重集后两个集合相等。

题解

固定 $k$ 和 $j$ 后显然 $i$ 是在一个区间内的，考虑维护 $l_p$ 和 $r_p$ 表示 $j=p$ 时 $i$ 的上界和下界减一，则固定 $k$ 后的答案即为 $\sum\limits_{j=1}^{k-1}\max(r_j-l_j,0)$ 。那么设 $L_i=\max\{j|j<i,a_j=a_i\},R_i=\min\{j|j>i,a_j=a_i\}$ ，则有 $l_j=\max\{i|i\le j,R_i>k\},r_j=\min\{L_i|j<i\le k\}$ 。

考虑 $k\to k+1$ 后对 $l_j$ 和 $r_j$ 的影响，注意到 $l_j$ 单调递增且 $r_j$ 单调递增，而 $k\to k+1$ 对 $l_j$ 的影响是删去了 $R_i=k+1$ 的元素，体现为后缀取 $\min$ 即区间赋值；对 $r_j$ 的影响则是加入了 $L_{k+1}$ ，也体现为后缀取 $\min$ 即区间赋值。注意到由于两个东西都是单调递增的，所以可以用线段树来维护。

时间复杂度 $O(n\log n)$ 。

更多例题：

GYM102900J Octasection

区间修改区间历史和线段树

考虑给线段树上每个点维护一个一次函数 $f(x)=kx+b$ ， $f(x)$ 为 $x$ 时的历史和。

单点修改区间查询是好做的，找到要修改的点，设在时刻 $y$ 结束后要修改为 $k'$ ，那么把那个点的一次函数修改为 $f(x)=k'x+y(k-k')+b$ 即可。

区间修改区间查询分为两种情况：

区间加区间查询：很好做，给 $k$ 和 $b$ 打 tag 即可；
区间赋值区间查询：
注意到此时区间内 $k$ 不同则无法一起修改，那么维护区间 $k$ 最小值 $mnk$ 和最大值 $mxk$ 。对于一个需要被修改的区间，若 $mnk\not=mxk$ 则递归左右儿子修改，否则直接打 tag 修改。
这样做时间复杂度均摊是 $O(n+q\log n)$ 的，其中 $n$ 为序列长度， $q$ 为操作数。因为刚开始最多有 $n$ 个区间需要额外往下递归，每次修改最多会让 $\log n$ 个区间在以后的修改中需要额外往下递归，所以总共需要额外往下递归的区间是 $O(n+q\log n)$ 的；

例题：

set 维护连续段

颜色段均摊若用线段树维护则会把一个连续段拆成 $\log$ 个，总连续段个数变为 $O(n\log n)$ 。

而用 set 维护则总连续段个数是 $O(n)$ 的，并且很好写。

代码如下：

struct seg
{
	int l,r,x;
	inline bool operator<(const seg &b)const{return l<b.l;}
};

typedef set<seg>::iterator iter;
set<seg> st;

inline iter split(int p)
{
	iter x=st.lower_bound((seg){p,0,0});
	if(x!=st.end()&&x->l==p) return x;
	x--;
	seg vx=*x;
	st.erase(x);
	st.insert((seg){vx.l,p-1,vx.x});
	return st.insert((seg){p,vx.r,vx.x}).first;
}

inline void ins(int lb,int rb,int x)
{
	split(lb);
	iter l,r=prev(split(rb+1));
	l=st.lower_bound((seg){lb,0,0});
	iter pr=l,ed=next(r);
	while(pr!=ed)
	{
		// a_{[pr->l,pr->r]} = x
		st.erase(pr++);
	}
	st.insert((seg){lb,rb,p});
}

摩尔投票

可以用来求集合中出现次数可能严格大于 $\lfloor\frac{r-l+1}{k}\rfloor$ 的 $k-1$ 个数。

为什么是可能呢，因为它的原理如下：

每次选 $k$ 个互不相同的数，将它们从集合中删去，剩下的至多 $k-1$ 种数就是答案。

这是显然的，因为答案一定不会被删去（出现次数比其它数出现次数总和的 $\frac{1}{k-1}$ 还多），而答案至多只有 $k-1$ 个。

这个东西满足可加性，维护两个集合最后剩下的 $k-1$ 个数即可。

那么可以做区间修改区间查询众数了。

没见过想不到。

例题：P3765 总统选举

NOI 考过：P8496 [NOI2022] 众数

模拟赛考过：【2024NOIP模拟赛73】数数

函数复合扫描线

给定一个函数的序列 $f_i$ ，每次给定一个输入 $x$ 和一个区间 $[l,r]$ ，查询 $f_r(f_{r-1}(f_{r-2}(\dots f_l(x)\dots)))$ ，即对 $x$ 依次应用区间内函数后的结果。

这种题有一个套路就是离线，然后从左往右扫描函数序列，动态维护一个集合 $S$ ：

遇到查询左端点的时候将 $x$ 加入 $S$ ，并保存好 $x$ 在 $S$ 中的指针；
扫过一个 $i$ 就将 $S$ 中元素集体应用 $f_i$ ；
遇到查询右端点就拿出指针查询 $x$ 的最终值；

”保存指针“：由于 $S$ 一般要用某些数据结构维护，而 $x$ 会不断改变，所以需要维护 $x$ 在对应数据结构中的指针（例如平衡树的节点编号）。

例题：

一些数据结构技巧

值域树状数组求 k−thk-thk−th

值域倍增分块

减半报警器

支配

关于距离的支配

序列上

树上

一些特殊的支配

Mex 支配

更多例题

三维计数技巧

区间修改区间历史和线段树

set 维护连续段

摩尔投票

函数复合扫描线

感谢您的支持，我会继续努力的!

值域树状数组求 $k-th$