考试

A

简单题，合并两个之后一定不劣，用个栈维护还没合并的东西。

B

计数题，容易发现等价于做保证全为 \(L,R\)，此时每一行的贡献独立，考虑计算每一行单独的答案，乘上其它行的方案数，得到最后的解。

计算一行的答案，考虑每一个的贡献，好像不太行，因为你需要枚举和它配对的是什么，然后就寄了，计算的时候，我们可以决定每一个选还是不选，最后取待选的个数为 \(0\) 的所有方案，同时记录方案数和答案的和，即可完成转移。

C

有趣的题。

如果采用常规的数位DP方式，那么必须记录进位数和卡界数，只能做到 \(O(nk^4)\)。

但是不妨从结果考虑，如果能计算出恰好取到 \(n\) 的方案数，并求出 \(f(n)\)，那么答案就是 \(\sum\limits_{n\ge 0} f(n)\times 取到\ n \ 的方案数\)。考虑取到 \(n\) 的方案数怎么算。

这里定义 \(\binom{a}{b}=0 \text{ when } a<0\)。

利用容斥原理，计算强制 \(k\) 个数大于 \(x\) 的方案数。 \[ ans=\sum\limits_{n\ge 0}\sum\limits_{i=0}^{k} (-1)^{i}\binom{n+k-1-i\times(x+1)}{k-1}f(n) \] 后面那个东西，\((k-1)!\) 是个常数。

提出来后是一个关于下降幂乘上 \(f(n)\)。

把下降幂展开成关于 \(n\) 的多项式，问题变成求 \[ \sum\limits_{n\ge0} f(n)n^x \] 这个可以数位DP，考虑往后面填什么，假设已经求了 \(10^i\) 以内所有答案，往后填 \(c\)，对应的变换就是求 \(\sum\limits_{0\le n<10^i} f(10n+c)(10n+c)^x\)，把 \(c\) 扔到外面，后面哪一项用二项式定理展开，就可以用原来的值推新的值了，这东西是个卷积，但是枚举 \(c\) 的部分可以扔到外面去，预处理后是 \(O(nk^2)\) 的。

但是这是有问题的，因为我们定义的组合数和下降幂算出来的组合数是不一样的，因此需要排除掉 \(n< i\times(x+1)\) 的部分，这个可以重新数位DP一次，过程是一样的。

但是有更优雅的办法，枚举每个可能的数与 \(i\times(x+1)\) 的 LCP，然后除掉当前位后面是没有限制的，后面没有限制的答案，我们已经算过了，就是前面那个值，前面的数，已经知道了，所以合并答案的过程和刚刚没有区别，由于合并答案的过程是 \(O(k^2)\) 的，所以这样会比一般的数位DP写法更加优雅。

预处理一些东西的时候要小心，注意不要超过数组或者处理少了。

D

数据结构题。

我终归还是不会区间数颜色。

区间数颜色

需要求的东西很丑，我们的数据结构，能维护的东西是满足一些偏序关系的元素的和，但是这个东西不是这样的比较优美的形式，所以考虑转化成我们的数据结构能维护的东西。

区间数颜色，就是把不好维护的，通过一个于询问无关的 \(pre\) 数组，转化成了利于维护的偏序关系。

如果考虑区间内相同数的贡献情况，它形如 \(100000\)。

这道题可能需要求一个形如 \(\text{1 -1 0 0 0 0 0}\) 的东西。

我们发现求 \(1100000\) 也是容易的，只需要记录 pre 的 pre 就可以了。于是可以加减消元得到结果。

然后树套树。

码量极其[数据删除]。

不过直接这么搞不太行，常数太大，所以可以把每个 \(\le 10^3\) 的质因子搞出来拿个块状链表维护，再转化一下，将同一质因子视为若干线段其中 \(1-3,2-4,3-5\) 这样连，可以直接得到答案，而不用做消元。

这种把颜色连成线段的思路还是有一定的启发意义。

我实在不想写这个，下面的假莫队做法好写好调还快些。

莫队

莫队思想其实是可以做强制在线题的，这基于我们能够快速从 \([l,r]\) 拓展到 \([l,r+1]\)。如果我们能够记录当前若干个状态的值，比如 \(O(n^{\frac{2}{3}})\) 个，相当于是让每个 \(O(n^{\frac{2}{3}})\) 大小的块都能记下对应的值，然后拓展的代价就是 \(O(n^\frac{2}{3})\) 的，有些题目可能会有空间问题，得就题目讨论。

这道题一个状态需要的空间大约是 \(80000\times 4 \div 1024\div1024\approx 0.3 MB\)，可以记录约 \(3000\) 个状态，这已经够用了， \(\sqrt {3000} \approx 54\)，我们能以 \(O(\frac{nq}{54})\) 的代价回答询问，对于修改，至多影响 \(3000\) 个状态，也是可以接受的。

当然，我们需要把小于 \(1000\) 的质因子提出来单独先做一遍，以免代价过大。

但是开 \(54\) 个端点不是最优的，实践表明块长小一点，比如 \(40\) ，会更加优秀，这种分块题还是需要看实际实现来调块长。

不过 \(10^5\) 的题，怎么玩都是基本不会出问题的。

总结

时隔接近一个月写的考试总结...

考试

T1

没有什么价值的题，分析一下相位这些就可以做出来。

T2

算区间最大值之和要枚举最大值位置算跨过的数量，所以考虑对这个东西动态规划，设 \(dp[l][r]\) 表示只考虑 \(l,r\) 区间的最优答案。

枚举最大值位置后，拆分成两个区间，其答案和最大值位置以及彼此无关，符合最优子结构性质，加上最大值的额外贡献，可以在每一个位置枚举取哪个值，有可能算出来答案比较劣，但是仍然可以遍历解空间，所以这样 DP 没有问题。

枚举取值的复杂度很高，发现每个位置的最优值和 dp 数组无关，考虑预处理每个位置的最优值，本质上是给定若干一次函数，再给定若干 \(x\)，求最值，很简单。

T3

考场上没有做出来的题，但是基本想出来了，ARC 那道期望题加深了对期望的理解。

根据期望线性性，\(E(dis_{u,v} ) = E(dis_u)+E(dis_v)-2\times E(dis_{lca(u,v)})\)。

前两者是好算的，考虑这样一个 \(dp\)，\(dp_u\) 表示 \(1\) 到 \(u\) 的期望距离，转移比较简单。

考虑后者怎么算，即 \(u,v\) 两点 \(lca\) 距离的期望，如果 \(v\) 在下面，由于 \(lca\) 一定在 \(u\) 及之前，所以 \(u,v\) 的 \(lca\) 的期望等价于 \(u,u+1\) 的 \(lca\) 的期望，归纳即可证明。

考虑计算 \(u,u+1\) 的 \(lca\) 的期望值，这个也是可以动态规划的了，枚举 \(u+1\) 的祖先即可，上前缀和优化。

T4

我的想法

考虑类似点分治一样去做，只不过是随机选点，期望层数应该是 \(O(\log n)\)，证明的话，考虑将 \(\frac{n}{4}\) 个点变成一个点，分两种情况，该点存在大小超过 \(\frac{n}{2}\) 的子树和不存在。后者已经证毕，每次问题规模有 \(\frac{1}{4}\) 的概率变为原来的 \(\frac{3}{4}\)。前者考虑在该子树中选取包含根的 \(\frac{n}{4}\) 个点重复以上过程，于是不存在大小超过 \(\frac{n}{2}\) 的子树，同样证毕。

基于点分治的原理（独立的子树不跨过分治中心），可以求出每棵子树包含的点集，但如果分治的叉过多，求叉的的过程需要反复尝试每一个叉，复杂度退化到 \(n^2\)。

树形态随机的情况下（随机父亲），每个点的分叉期望是 \(\ln n\) 级别的，复杂度为 \(O(n\log^2 n)\)。

Topsort

需要问树的形态，考虑单独的一次询问能干什么，可以判断一个点是否为叶子，所以考虑从叶子一层一层往上确定。一种比较暴力的方式是先找出所有的叶子，然后删掉后找出二级叶子，找一个点当根，直接确定某个点的父亲是不好做的，考虑为某个点确定一个儿子，方式是二分，重复若干次即可。

确定一层的均摊复杂度是 \(O(leaf\log{(leaf)})\)，外加找叶子的复杂度，总计 \(O(n^2)\)，考虑优化找叶子的复杂度，一种可行的方式是先弄出一个拓扑序排列，按照拓扑序去逐一确定。

弄拓扑序可以考虑以插入的方式构造排列，一个拓扑序合法当且仅当 $  i 满足  j[1,i), p_i 不是 p_j 的祖先$。插入构造时询问一个前缀到根是否包含当前插入的点，如果包含，那么这个点应该放在更前面，得到拓扑序之后就可以逆序构造。

Subtree

考虑递归的构造，确定父亲和子树内容，假设有一个函数 \(f(x)\) 可以求出 \(x\) 子树中所有点的父亲（除自身外），那么调用每个 \(f(x)\) 一次后就可以保证求出树的结构。维护一个没调用过 \(f(x)\) 的点集，在点集中找到一个是 \(x\) 后代的点 \(y\)，调用 \(f(y)\)，于是求出了 \(y\) 后代所有节点的父亲，维护一下没确定父亲点的点集，在没调用过 \(f(x)\) 的点集中，若找不到 \(x\) 的后代，那么就可以开始在没确定父亲的点集中找出 \(x\) 的所有儿子了。

分析复杂度为 \(O(n\log n)\)。

ABC

没什么价值的题。

D

首先每次选路径一定会选到根。

要求儿子相差不超过 \(1\)。

所以每个点被选的次数弄出来了，那么每个儿子只有两种选法，选 \(\lceil\frac{cnt_u}{cson_u}\rceil,\lfloor\frac{cnt_u}{cson_u}\rfloor\)。

根据经典结论，如果直接动态规划，状态数为 \(O(n)\)。

E1

趣味题

考虑二分，发现不可二分，因为问 \(S,\overline S\) 是等价的，所以随便糊弄你就行。

所以考虑三分或者四分。

考虑解决 \(n=3\) 的基本情况。

先确定问题再处理的方式看上去不太可取。

所以我们多半是需要根据回答来决定下一个问题。

这就是一颗决策树。

问一个时，\(Y\) 的限制较强。

不妨先问 \(1\)，如果是 \(N\)，那么再问一遍 \(1\) ，还是 \(N\) 则排除 \(1\)，如果是 \(Y\) 则回到最初的 \(Case\)，此时问 \(2\)，如果回答是 \(Y\) 则排除 \(3\)，\(N\) 则排除 \(2\)。

那么用了 \(3\) 步将问题规模变为 \(\frac{2}{3}\)。

总步数为 \(3\log_\frac{3}{2}(10^5) \approx 85\)，取整之后问题不大。

F

让人眼前一亮的随机化思路。

首先可以带修莫队 \(O(n^{\frac{5}{3}})\)。但是过不了。

先考虑 \(k\) 比较小的特殊情况，不妨就是 \(k=2\)。

左想右想，都没有办法比较好的合并信息，因为它没有办法写成经典的偏序计数问题。

没有办法这样合并，那就只能 \(O(n^2)\)。

所以我不会。

这是个判定问题，只需要回答 YES NO。

考虑条件，必要条件是比较好找的，显然每个数出现次数为 \(k\) 的倍数是必要条件，若干个必要条件加在一起就是充要条件。

考虑同时判定若干个必要条件，即某些数的出现次数是否为 \(k\) 的倍数，似乎不太可做，但是发现如果随机选取若干个数并判定，那么对于答案为 NO 的所有情况，通过判定的概率至多为\(\frac{1}{2}\)，所以随机对数个子集判定后对于通过的回答 YES，正确率足以接受。

对于一个判定问题，如果有某种检测算法，答案为 YES 一定可以通过，答案为 NO 概率通过，那么运行这个算法对数次后，可以以很高的正确率回答该判定问题。

如果有一个判定问题，某随机算法能以超过 \(50\%\) 的概率给出正确的答案，那运行这个算法对数次取众数即可解决问题

A

胡乱想了一通，做出来了。

形如要求 \(f(x)=f(y)\) 的问题，可以考虑 \(f(x)-f(y)=D\)，这样就可以考察 \(x,y\) 独立对 \(D\) 的贡献了。

字典序题，从前往后贪心。

B

字典序的题，一般的方式是考虑从前往后贪心，考虑前 \(i\) 个相等的情况，并查集维护一下前面要求相等的组数，然后就是简单的组合题。

另外一种特有的方式是考虑字典序小于，和字典序大于是等价的，总方案减掉字典序相等的方案除二即可。

C

SG 函数打表，没什么技术含量。

D

很有趣的题。

二进制位相关的题目，刻画一下变换的过程，等价为在图上走。

然后发现如果 \(X_i\) 相等是好做的。

我就没啥思路了。

看一下题解。

考虑交换两个 \(X_i\) 不同的，发现最终答案不变，因为图上走的过程是等价的，继续选上之前选的边就行。

然后就做完了。

C

这里的 C 指 C2。

首先来一波 \(\pm i\) 变成相对简单的判 \(> 0\) 问题。

Method1

考试的时候，比较自然的考虑计算跨过某个数的合法区间总数，发现可以把某个位置开头最远的区间给算出来。

然后就是个二维偏序。

然后对于新修改的元素，计算跨过它的合法区间个数，如果改小了，一定只会有一些数被这个东西限制，我选择做一个极度毒瘤的二维偏序。

如果改大了，一定只会有一些数在此处的限制被放开，再处理每个数放开一次限制后的最大位置即可，对于同一位置，可以处理单点前缀和，然后在上面 lower_bound。

显然两个都是可以在线做的，但是考试的时候没有发现被限制的数一定是一个区间，然后就出现了毒瘤。

不知道自己写的什么狗屎离线做法，奇丑无比。

Method2

上面那个搞什么二维偏序是邪道。

还是考虑求跨过每个数的合法区间个数，某个位置 \(x\) 会限制另一个位置 \(i\)，当且仅当 \(a_x+i\le 0\)，所有一个位置限制的位置一定是一个前缀，这部分前缀的前缀会在这个位置之前被另外的位置限制，这是是可二分的。

所以改小的影响就好算了，找到被改小的数限制的区间，这一部分求总长度然后减去 \(cnt\times x\) 得到答案减小值。

改大会比较麻烦，参考上面的处理方式。

Conclusion

多找点性质，又不妨碍做题。

多学着点二分，别去搞什么垃圾数据结构二维偏序。

D

比较清新的构造题，难度不大，但是场上没想出来。

先假设没有操作，尝试求解该问题，发现它比较困难（似乎不存在多项式做法），所以应该考虑能不能构造出特殊情况。

考场上我看成了 reverse，这也是可做的，只需要构造出形如 0000011111 的串就行，方法是选上末尾的，插在 1 之间的 0，然后和前面的 1 交换，设 1 的个数为 \(cnt_1\)，那么选择后面 \(cnt_1\) 个位置中所有的 0，再选出前面所有的 1，交换即可。

实际上是循环左移，同样考虑构造特殊情况，这次选择构造 001100111100 这种。

如果不是，就选一个，找到下一个同样不满足的，然后移过来，最后一定有偶数个不满足的，用不同的数隔开就行。

本质上，这个操作相当于选了偶数个相邻数不同的数，把它们 flip。

平衡树

既然标题敢写平衡树，那就需要来谈谈平衡树本身，而不仅仅是实现它的方法。

平衡树本身

平衡树是一颗二叉搜索树，每个节点权值大于左子树所有节点，小于右子树所有节点。

和线段树相比，它是一种动态结构，适合维护结构动态变化的信息，比如需要支持插入和删除以及翻转的序列，也可以用来维护一棵树（LCT）

和块状链表相比，它只能处理能够快速合并的信息，但是复杂度有所降低。

实现

Splay

已经很熟悉的方式，不再多说，不过可以多嘴提一句势能分析。

势能分析原理

定义势能函数 \(F(S)\) 表示状态 \(S\) 的势能，定义操作代价 \(p_i=c_i+F(S')-F(S)\)，其中 \(c_i\) 表示操作时间。

求解 \(\sum p_i=\sum c_i + F(S_m)-F(S_0)\)

移项得到 \(\sum c_i=\sum p_i+F(S_0)-F(S_m)\)

一般来说，\(c_i\) 会比较奇怪，但是通过 \(F\) 函数的变化值可以去抵消掉这个奇怪的值得到优雅的 \(p_i\)，然后一般来说最后的复杂度和 \(\sum p_i,F(S)\) 同阶

分析 Splay 的复杂度和单旋的复杂度

定义势能函数，定义单点势能 \(w(u)=\log_2(size_u)\)， \(F(S)=\sum\limits_{u\in S} w(u)=O(n\log n)\)。

旋转点为 \(x\)，父亲为 \(f\)，祖父为 \(g\)。

左旋代价

注意到 \(size_{x'}=size_{fa}\)。

\(1+w(x')+w(fa')-w(x)-w(fa)\le 1+w(fa)-w(x)\le 1+w(x')-w(x)\)

双左旋代价

\(1+w(x')+w(f')+w(g')-w(x)-w(f)-w(g)\le 1+w(f')+w(g')-w(x)-w(f)\)

\(w(f)\ge w(x),w(f')\le w(x')\)

\(w(x')-w(x)\ge w(f')-w(f)\)

\(1+w(f')+w(g')-w(x)-w(f) \le 1+ w(x')+w(g')-2w(x)\)

若 \(w(x')-w(x) \ge 1\)

则 $ 1+ w(x')+w(g')-2w(x)(w(x')-w(x))$

否则因为先旋的 \(f\)，所以 \(g'\) 下的点不包括 \(x\) 中的点，所以有 \(size_x\ge size_{g'}\)，因此 \(w(x')-w(g') \ge1\)

得到 \(1+ w(x')+w(g')-2w(x)\le 2(w(x')-w(x))\)

综上 \(1+w(x')+w(f')+w(g')-w(x)-w(f)-w(g)\le 3(w(x')-w(x))\)

左右旋代价

\(1+w(x')+w(f')+w(g')\le 1+w(f')+w(g')-w(x)-w(f)\le 1+w(f')+w(g')-2w(x)\)

由于最终 \(f',g'\) 都是 \(x'\) 的儿子，所以 \(1+w(f')+w(g')-2w(x)\le2w(x')-2w(x)\)

所以 \(1+w(x')+w(f')+w(g')\le 2w(x')-2w(x)\)

双旋代价

注意到只会进行一次 zig 操作，所以可以忽视 zig 的那个 1，其余代价直接相加，得到 \(3\)，因此 \(p_i=O(\log n)\)。

观察到一次 Splay 操作的每个子操作可以弄成 \(3\) ，然后相加抵消掉得到 \(3+3w(x')-3w(x)\)，是 \(O(n\log n)\) 级别，势能变化量为 \(O(n\log n)\) 级别，故时间为 \(O(n\log n)\) 级别。

单旋代价

单旋代价为左旋代价的和，每次 Splay 操作数为 \(O(n)\)，故单旋的复杂度上界是 \(O(n^2)\)

总结

以上势能分析对 Splay 操作的要求是非常严格的，因此如果在查询中没有进行 Splay 操作，那么操作时间无法导致对应的势能变化，最后出现不正确的复杂度。

Treap

数据随机的情况下，一个堆（每个节点的权值均大于它全部后代的权值）的期望高度是 \(\log n\) 的，通过左右旋保证堆的性质，可以保证 Treap 的复杂度，左旋右旋和 Splay 完全相同。

FHQ_Treap

元素 val：需要维护的值。

权值 height：随机的，用于保持堆性质的值。

核心操作是 Merge 和 Split。

过程中需要时刻保证满足堆的性质

merge(u,v)

合并两个子树 u,v ，保证 u 中元素全部小于 v，返回根。

和线段树合并非常像。

1
2
3
4
5
6
7
8
9
10
11

int merge(int u,int v){
    if(!u||!v)return u^v;
    if(height[u]>height[v]){
        son[u][1]=merge(son[u][1],v);
        push_up(u);return u;
    }
    else{
        son[v][0]=merge(u,son[v][0]);
        push_up(v);return v;
    }
}

Split(u,x,y,k)

按照元素值小于等于 \(k\) 划分为两颗树，较小的那棵树树根为 \(x\)，较大的那个树根为 \(y\)。

细看这个函数其实相当妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void split(int u,int &x,int &y,int k){
	if(u==0){
    	x=y=0;
        return ;
    }
    if(val<=k){
        x=u;
        split(son[u][1],son[u][1],y,k);
    }
    else{
		y=u;
        split(son[u][0],x,son[u][0],k)
    }
    push_up(u);
}

其实也可以按照子树大小划分，用于文艺平衡树。

其它操作

• get_l(element)：按照小于 element 划分，然后返回较小那边的大小，重新 merge
• get_element(rank)：与 splay 没有差异。
• insert(element)：按照小于等于它划分，然后 merge 两遍。
• erase(element)：按照小于等于它划分，然后按小于它划分，然后把划分得到的两个儿子 Merge 起来再 merge，然后再 merge，这样是能够处理元素相同节点的。
• get_prev(element)：按照小于它划分，用 get_element()
• get_next(element)：按照小于等于它划分，用 get_element()
• 合并的时候也可以按概率选择父亲，\(sz\) 较大的权重较大，期望复杂度可以证明是 \(O(n\log n)\) 的。

某些实验

采用佳老师的神奇插入删除方式：

可以发现正常的插入方式需要 \(14S\)，\(18S\) 是按子树大小概率合并，加上佳老师优化后变为 \(10S\)，有一定改进。

如果直接实现 get_rank 系列函数可以更快，但是没什么必要了。

手写 get_rank 系列后耗时为 \(9S\)，手写 get_rank 系列，采用正常插入方式，用时 \(12S\)。

全实现的 Splay 需要 11S。

vector

一般来说，如果数据范围 \(\le 5\times 10^4\)，或者时限比较宽松，可以用 vector 实现平衡树。

pb_ds

自带平衡树，一般用于操作比较简单的情况，如果需要打 Tag 之类的，重写 node_update 不如手写一颗。

可持久化平衡树

可持久化平衡树一般用于解决强制在线的历史版本问题，对于非强制在线问题，其实可以离线到树上实现一个支持撤销的平衡树。

对于强制在线问题，基本思路都是复制修改过的路径，复用没有修改过的路径。

可以发现其实任何一个版本创建之后就是静态的，所以可持久化数据结构的核心是：任何时刻访问先前的版本，都能得到正确的结果，任何修改不能影响到先前的版本。

Splay 实现

其它操作不变，Splay 时复制涉及的所有点作为一个新版本。

但是，这玩意的复杂度有问题，Splay 的复杂度保证在于对操作进行势能分析，引入可持久化后，势能的变化量会变成 \(n^2\log n\) ,因此复杂度会退化。

由于实际应用中，很少存在只能用 Splay 的情况，因此没有必要深究 Splay 的可持久化。

FHQ-Treap 实现

听说这种实现有点问题，但是实际中并没有出现过问题，如果觉得不太行可以换下面那种奇怪的实现。

Split

由于操作都是从 Split 开始的，所以每次 Split 前都复制一个版本出来，具体的，像可持久化线段树一样把不变的儿子共用，改变的儿子复制。

Split 的路径上所有点的信息都被改变了，需要复制一遍得到新的，这样原先版本的所有节点不会有任何变化。

大致刻画以下 Split 中被修改的点，它呈一条链

Merge

Merge 过程中的复制不是必须的，原因是每个被修改的点都是被新建出来的点，这个证明可以考虑归纳，合并深度为 \(1\) 的节点时，两点显然都是被复制的，不影响原树，合并任何被复制的两个节点时，较小的那个的右儿子，较大的那个的左儿子要么不存在，要么是被复制的，因为在被复制的节点处，链一定会向下延申。

因此合并时可以不用新建节点。

神奇方法

佳老师有一个神奇写法，理论常数为 \(\frac{1}{2}\)，具体的，插入和删除时先找到第一个 key 小于当前点 key 的点，然后这个点一定是被插入/删除点的儿子，然后把只对这个儿子做一遍 Split，并把树分到插入点的两个儿子上面去，这个思路同样可以用于一般 FHQ-Treap，运用在普通平衡树中，实际效率改进因子在 \(0.33\) 左右。

一般来说删除就正常搞，不然容易写错。

考试的时候如果不卡常就写正常写法，减少可能的错误。

一般来说，空间得开 50 倍。

注：效率改进因子，若效率改进因子为 \(x\)，原时间 \(t\)，则改进后时间为 \(\frac{t}{1+x}\)。

Treap 实现

由于期望树高是 \(\log n\) 的，所以直接复制所有已经被修改的点的信息

某种奇怪的实现

类似 FHQ-Treap，但是 Merge 的时候按照子树大小作为权重，随机选一个做父亲，这样的复杂度是有保证的。

文艺平衡树

文艺平衡树是一类用于维护区间的平衡树，它和正常的平衡树类似，但是用树的结构来决定一个元素的大小，适合用来维护结构动态变化的序列。

一般用 Splay 和 FHQ-Treap 实现。

FHQ-Treap 实现时需要支持按 size 划分。

动态树

一般用 Splay 实现，复杂度 \(O(n\log n)\)，进行实链剖分，每条实链被一颗 Splay 维护，思想和文艺平衡树类似，用平衡树树的结构表明了原树节点中的的高度关系。

核心操作是 access 和 make_root。

access(x)

使得 \(x\) 到树根上的路径成为一条实链，断开 \(x\) 和它实儿子的连接，并让 \(x\) 成为该 Splay 的根。

make_root(x)

使得 \(x\) 成为树根，操作方式是先 accsess，然后翻转这条实链，使得 \(x\) 的深度最小。

由于虚儿子认父不认子，所以整个结构都没有问题。

实现

一般采用 Splay，FHQ-Treap 也没有问题。

但是不能用一般 Treap，因为一般 Treap 对树结构的要求决定了它无法进行旋转操作。

FHQ-Treap 的复杂度很难证明是 \(n\log n\)，但是可以保证上界为 \(O(n\log n^2)\)，Splay 的复杂度则为 \(O(n\log n)\)

似乎有 \(O(n\log n)\) 的 FHQ-Treap 实现。

考试总结

考试

发挥一般

T1

很趣味的题，考虑计算答案的过程，首先从某个点开始，遇到

T2

平衡树模板，不做评价，权当练习使用 pb_ds。

其实有平衡树之外的多种解法。

值域分块

对这个东西其实一直不熟悉，如果序列分块不容易解决或者复杂度多一个 \(\log\)，那么考虑对值域分块，记录和每块数值有关的信息。

\(O(1)\) 改可以只改对应数值块和自身的数据，\(O(1)\) 查可以对块和块内维护前缀信息或者其它预处理信息。

树状数组上二分

写过若干次，但不熟练。

以前缀和树状数组为例，它每个节点 \(x\) 维护的信息是 \((x-lowbit(x),x]\) 区间的全部信息。

更新时一直 +lowbit，保证了恰好能够维护这些信息。

所以如何二分也比较明晰了。

1
2
3
4
5
6
7
8
9

int now=0,sum=0;
for(int i=18;i>=0;i--){
    // 现在认为在 (now,now+1<<i+1]
	if(1<<i|now<=n&&sum+c[now|1<<i]<k){//在 (now|1<<i,now|1<<i+1]
        now |= 1<<i;
        sum += c[now];
    }
}
int res = now + 1;

T3

有些价值的题，"优化状压DP" 还是有一些话题可谈。

T4

李超树模板题，类似 CDQ 分治的思路或者平衡树维护凸包其实很趣味，但是没有什么启发意义。

等有时间了写一份斜率优化的总结。

20221011 考试总结

考试

T1

假的可持久化题，弄到树上做撤销就行。

其实写可持久化 FHQ-Treap 更容易

参考 关于平衡树

还可以用块状链表搞定。

T2

树套树模板题，但是有一些不同的思考方式。

我采用了线段树套值域线段树，但是需要同时二分多个主席树，不够优雅。

值域树套位置树

一般来说，位置树套值域树更加常见，但如果有些涉及到二分的操作，也许把它们反过来会更加容易，因为反过来之后就可以在数据结构上二分，减少一个 \(\log\)。

其实位置树套值域树也可以在数据结构上二分，只是实现起来相对麻烦一些。

可以采用值域线段树套平衡树。

这个时候 FHQ-Treap 的优势就体现出来了，很简单的可以查到 \([l,r]\) 区间内数的个数。

莫队和值域分块

带修莫队可以处理单点改区间查的问题，修改一共 \(O(n^{\frac{5}{3}})\) 次，查询 \(O(n)\) 次，使用 \(O(\sqrt n)-O(1)\) 的值域分块即可处理问题。

题意

• 给你一棵有根树，定义一个点合法当且仅当它到根上的点全为黑色，否则不合法。

• 最开始所有点为白色，每次选一个不合法的点涂黑，每个点可以被涂黑多次。

• 问所有点被涂黑的期望次数

思考1

这次想题引爆了某人概率论基础不扎实的炸弹。

考虑每个点被涂黑的顺序，是一个排列，取到每种排列的概率相同。

考虑使用全期望公式计算，先考虑固定一个排列时的答案。

先假设只有 \(3\) 个点，且顺序为 \(3,2,1\)，也就是赠券收集问题。

选第一个点的期望次数为 \(1\)，因为所有满足这个排列的样本点都是以 \(3\) 开头，选第二个点，期望次数是多少，或者说，选出第一个点后，下一个被选择的点，在顺序为 \(3,2,1\) 的前提下，是 \(2\) 的概率是多少？

\(\frac{1}{2}\) 的来历

选第二个点时，可以选的点有 \(3,2\)，选择每个点的概率相同，所以概率为 \(\frac{1}{2}\)

虽然原本每个点概率时相同的，但是我们求的时条件概率，条件概率的样本空间已经被改变了，所以选择每个点的概率不再相同。

\(\frac{2}{3}\) 的来历

考虑概率的定义，\(P=\frac{事件大小}{样本空间大小}\)，考虑该条件的集合和事件与条件的交集，因为此题样本空间无限大，所以考虑将一个无限长序列映射到我们的样本空间，容易发现这样的映射不会改变概率函数。

设 \(k\) 为已经选取的数的个数，\(n\) 为数的总数。 $$ \[\begin{align} P=&\lim\limits_{m\rightarrow \infty}\dfrac{n^{m-1}}{\sum\limits_{1\le i\le m} k^{i-1}\times n^{m-i}}\\ =&\dfrac{n^{m-1}}{\frac{n^{m}}{n-k}}\\ =&\frac{n-k}{n} \end{align}\] $$ 这是在正确的样本空间算出的正确结果。

从 Beyes 公式考虑： \[ \begin{align} P(下一个值为目标|满足排列限制)=&\dfrac{P(下一个值为目标\wedge满足排列限制)}{P(满足排列限制)}\\ =&\dfrac{\frac{1}{n}\times\frac{1}{(n-k-1)!}}{\frac{1}{(n-k)!}}\\ =&\dfrac{n-k}{n} \end{align} \] 神奇吧？

贝叶斯公式连接了条件概率和原问题的样本空间。

总结

样本空间无限大的时候要小心，不能轻易认为两个元素等价，因为此时 \(\infty \ne \infty\)。

用贝叶斯公式好好算算吧。

草率的断言概率为 \(\frac{1}{2}\)，很大一部分原因都是认为两个正无穷时相等的。

有了这个东西就可以愉快的推狮子 NTT 了。

思考2

其实这种题还有一种更加普遍的做法，期望线性性，考虑每个点被选的次数，相加可以得到最终答案。

期望线性性来源于期望的定义，一个随机变量是一个函数，定义域为样本空间，值域为 \(\R\)，随机变量的期望为其密度函数积分的收敛值。

因此，无论两个随机变量是否独立，它们的期望都是可加的。

感性理解的话，两个随机变量之和的期望等于这样一个随机变量的期望：每个样本点的取值为两个随机变量在该样本点的取值之和，期望可以粗略理解为随机变量在样本空间每个点的平均值，因此随机变量的期望可加。

所以可以考虑每个点被选的期望次数，如果选到了不在这个点到根路径上的点，那么我们忽略这一次选择，这样的忽略不会影响这个点被选的期望次数，然后问题变成了一条链上的最后一个点被选择的期望次数。

注意，我们只关心这个点被选择的期望次数。

考虑怎么求这玩意，因为整个过程在点到根路径上所有点被选择之后才会结束，所以像赠券收集问题一样倒序。假设有 \(k\) 个点还没选，总共 \(n\) 个点，其中 \(w\) 个点可以选，那么转移答案是 \(dp[k]=\frac{k}{w}dp[k+1]+\frac{w-k}{w}dp[k]+\frac{1}{w}\)

移项得到 \(dp[k]=dp[k+1]+\frac{1}{k}\)，实际上和 \(w\) 无关，所以就很好算了。

官方题解的说法是如果考虑可以选已经 good 的点，最终答案不变，我理解不了这个过程。

upd：其实现在也可以理解了，因为如果选了已经 good 的点，那么再选一次就行了。

有几个比较重要的地方，一是忽略和答案绝对无关的操作，二是考虑计算过程。

事件和条件

以下概率均为古典概率模型，暂时不讨论几何概型。

这两个东西是我自己定义的，算概率之前，必须搞清楚事件和条件的区别，下面提两个搞不清楚事件和条件导致的问题。

三门问题

• 有三个门，一个门后面有汽车，另外两个门后面是山羊。

• 你可以先选择一个门，之后主持人打开一个门，门后是山羊

• 问此时两个门后有汽车的概率是多少

思考方式一（错误）

每个门后有山羊的概率是相等的，打开一个门不会影响另外两个门的状态，故另外两个门后有山羊的概率是相等的，故答案为 \(50\%\)

思考方式二（不严谨）

另外两个门有山羊的概率是 \(\frac{2}{3}\)，排除一个选项，所以选择的门后有山羊的概率是 \(\frac{1}{3}\)，另一个门的概率为 \(\frac{2}{3}\)。

不知道叫什么名字的问题

有个酒鬼，每天各有 \(30\%\) 的概率去 \(A,B,C\) 三个酒吧，还有 \(10\%\) 的概率呆在家。

一个警察要找他，警察已经找了 \(A,B\) 酒吧，都没找到他，问在 \(C\) 酒吧找到酒鬼的概率。

思考方式一（错误）

在酒吧的概率是 \(90\%\)，\(A,B\) 都没找到，说明一定在 \(C\)，所以在 \(C\) 找到酒鬼的概率是 \(90\%\)。

这个思路和上一个问题思考方式二类似，但是是错误的，因此说它不严谨。

思考方式二（不严谨）

已知不在 \(A,B\) 酒吧，那么在 \(C\) 酒吧和在家的概率之比是 \(3:1\)，因此答案为 \(75\%\)。

这种方式的问题在哪里不必多说了。

解释

思考这个问题前应该回到概率定义的几个要素：样本空间，样本点，事件。

一个事件的概率被定义为事件大小除以样本空间大小。

三门问题

第一个问题中，样本空间的大小为 \(3\)，需要计算在某个不被选择的门后面是羊的情况下，选择的门后面是车的概率。

事件的大小为 \(1\)，因此概率为 \(\frac{1}{3}\)，另一个不被选择的门后面有车，其事件大小为 \(2\)，因为最初样本空间中在两个门后的样本点都属于该事件（如果是这两个事件之一，那么没被打开的另一扇门后必定是车）。

推广到 \(n\) 门问题，主持人随机打开一个未被选择且没有车的门，那么样本空间大小为 \(1\)，不改变选择的事件大小为 \(n-2\)，改变选择的事件大小为 \(n\)。

酒吧问题

事件域

通常解决一个概率问题需要明确事件域，即我们关心的所有事件，如果事件域不合法，那么

某个样本空间不正确导致的悖论

假设选的门是 \(1\) 号，已知 \(2\) 号门没有车，那么 \(3\) 号门有车的概率是 $$

我们需要明确问题中这个概率定义是在哪个样本空间下的，问题中样本空间的大小很明显是 \(3\)，而在被开的门后是山羊的事件大小为 \(2\)

样本空间无限的问题