关于我复习 noip 数据结构这件小事

平衡树与 $LCT$ 待更.

$STL$

关键是会用.比较常用的有 $set,mutiset,priority\ queue,map$ 这几个.

简单说一下 $bitset$ .

1	bitset<MAXN> s;

这样就定义了一个 $bitset$ .默认所有位置都是 $0$ .

可以把它看成是一个长度为 $MAXN$ 的布尔数组,也可以看成是有 $MAXN$ 位的二进制数.

它支持直接调用/修改某一位上的值,

1 2	s[0]=1; s[1]=1;

也可以用它直接进行位运算,

1	s=s\|(s<<10);

一次位运算耗时是长度/系统位数,一般是 $32$ 或者 $64$ .

这个东西就可以把一些只有 $0/1$ 运算的做法给优化 $32/64$ 倍.

原理也很好理解,就是把每 $32/64$ 位压成一个整数参与运算,所以也可以手写它,不过会比较麻烦.

贪心只能过样例 sol

并查集

一定记得要初始化.

优化的方式主要有两种,路径压缩和按秩合并.按秩合并就是把小的合并进大的里面.

如果需要支持退回上一步操作,那么就只能选用按秩合并.

单独使用路径压缩或者按秩合并,查询一次的时间复杂度是 $O(\log n)$ ,同时使用是 $O(\alpha(n))$ .

但大多数情况我们都只写路径压缩,因为很难将它卡到 $\log$ 的级别去.

有些并查集会顺带维护这个块内的其他信息,合并的时候一起合并就可以了.

树状数组

一维的树状数组比起线段树的优势就是代码容易编写与常数较小,而功能远不如线段树全面.

它的优点是可以比较简单的拓展到高维,而二维线段树就已经比较难写了.

如二维平面上的数点/求和,但坐标可能需要离散化.

上帝造题的七分钟

线段树

经典数据结构,使用的方法也很多.

经典应用

线段树的经典应用,维护区间内的信息,并支持单点/区间修改.如维护区间和,支持区间加,区间乘.

本质上只有这三个点是会根据不同的题而产生差别的.

如何将两个小区间内的信息合并起来得到大区间.
一个修改操作执行后,区间内的各个信息分别会怎样变化.
如何合并两个懒标记(如果有区间修改).

如果你发现这三点都能在很短的时间内做到,那么这个信息就可以用线段树来维护.

算术天才⑨与等差数列 sol

排序 sol

序列 sol

动态开点线段树

就是新到一个点的时候,如果没有,你再新建一个节点作为这个节点.

回转寿司 sol

可持久化线段树

又称主席树,因为发明者的姓名拼音缩写为 hjt ,与中华人民共和国前国家主席的缩写一样…

可以存储 $m$ 个版本的线段树信息,要求每次修改都只是单点修改,每颗线段树的管辖范围都是 $[1,n]$ .

考虑线段树的一次单点修改操作,影响到的节点只有对应叶子节点到根节点路径上的所有节点.

这些节点数目是 $O(\log n)$ 的,所以在维护新版本的线段树时,只用新建出这些节点,其它节点沿用上个版本的.

并不用每次都把上个版本的所有节点拷贝出来,因为每个节点只需要知道儿子节点,直接将儿子节点指过去.

显然需要使用动态开点.

经典的使用方法是利用主席树对 $[1,1],[1,2],[1,3]\dots,[1,n]$ 这 $n$ 个前缀建出 $m$ 颗线段树.

这样在查询可减的信息时(如某数的个数),就可以直接用 $[1,R]$ 的线段树答案减去 $[1,L-1]$ 的线段树答案了.

Kth number sol

混合果汁 sol

李超线段树

解决的经典问题是每次可以在平面内添加一条 $y=kx+b$ 的线段,或者询问当 $x=x_0$ 时,各个线段中最大的 $y$ .

如果是先添加完所有线段,再进行若干次询问,可以求出上凸壳, $O(n\log n)$ 解决.

李超线段树维护的是各段区间内 优势线段 的编号.

优势线段 是指,这段区间内能成为最优线段的长度最大的那条线段.

往区间 $(l,r)$ 插入一条线段 $c$ 时,就与当前区间 $(l,r)$ 内维护的优势线段 $s$ 比较.

若这两条线段在 $(l,r)$ 内满足一条完全覆盖了另一条,就直接更新优势线段并返回.

否则,就递归下去,用 $c$ 去更新两个子区间.

因为至少在 $[l,mid]$ 与 $[mid+1,r]$ 这两个区间中的一者, $c$ 完全覆盖了 $s$ ,或 $s$ 完全覆盖了 $c$ .

所以更新一个线段树上的区间的时间复杂度是 $O(\log n)$ ,插入一条线段的总时间复杂度是 $O(\log^2 n)$ .

查询时就在线段上向下走,经过一个区间时,就用这个区间的优势线段来更新答案,每次的时间复杂度是 $O(\log n)$ .

适者 sol

游戏 sol)

吉司机线段树

区间取最值问题

维护一个长度为 $n$ 的整数序列 $a$ ,支持以下 $m$ 次操作:

区间 $[L,R]$ 内的所有数 $a_i$ 与 $x$ 取 $\min$ .
区间 $[L,R]$ 内所有数加上 $x$ .
询问区间 $[L,R]$ 中 $a_i$ 的最大值.
询问区间 $[L,R]$ 中 $a_i$ 的和.

对线段树每个区间维护最大值 $mx$ ,最大值的个数 $cnt$ ,次大值 $se$ ,区间和 $sum$ .

询问操作可以定位后直接做.

对于修改操作,若将一个线段树区间对 $x$ 取 $\min$ ,可以分情况讨论:

$mx\le x$ ,无效果,直接返回.
$se<x<mx$ .效果就是将所有 $mx$ 改为 $x$ ,其它不变.新的区间和 $sum’=sum-(mx-x)\cdot cnt$ 可以直接算出,再打上修改标记,返回.
$x\le se$ .递归下去,分别修改左右儿子.

复杂度为 $O(n\log^2 n)$ ,但实现效果接近 $O(n\log n)$ .如果没有操作 $2$ ,复杂度就是 $O(n\log n)$ .

最假女选手

历史最值问题

维护一个长度为 $n$ 的数列 $a$ ,支持以下 $m$ 次操作:

区间 $[L,R]$ 内所有数加上 $x$ .
区间 $[L,R]$ 内所有数变为 $x$ .
询问 $[L,R]$ 内数的最大值.
询问 $[L,R]$ 内数的历史最大值.

修改操作的 $x$ 可能 $<0$ .

尝试将两种修改操作归纳为一种修改操作 $(a,b)$ ,表示先加上 $a$ ,再与 $b$ 取 $\max$ .

那么修改 $1$ 对应的操作就是 $(x,-\inf)$ ,修改 $2$ 对应的操作就是 $(-\inf,x)$ .

考虑两个标记如何合并,假设当前权值为 $v$ ,依次经过 $(a,b),(c,d)$ 两次修改的效果:
$$
\begin{aligned}
v&\to \max{\max{v+a,b}+c,d} \\
&=\max{v+a+c,b+c,d} \\
&=\max{v+a+c,\max{b+c,d}}
\end{aligned}
$$
可以看出就等价于一次修改操作 $(a+c,\max{b+c,d})$ ,于是两个标记就合并为了一个.

为了能查询历史信息,维护一个意义一样的标记 $(a,b)$ ,表示区间内历史的最大增加量 $a$ ,历史最大与 $b$ 取 $\max$ .

将两个标记的 $+$ 定义为两个标记的合并,两个标记取 $\max$ 定义为两个元素分别取 $\max$ .

每次更新标记后,若当前标记为 $x$ ,历史标记为 $y$ ,则让 $y=\max(x,y)$ .

每个结点需要维护当前标记,历史标记,当前最大值,历史最大值 $4$ 个信息.

CPU监控