复建记录
真实的复建记录。真实的啥也不会。
[NOI2009] 二叉查找树
题意：给你一个treap，你可以花 \(k\) 任意改变一个点的堆权值。让你最小化 代价+深度*出现次数。
题解
先不考虑出现次数。给你一颗树，怎么计算最少花费的代价。 发现因为任意改变（实数），那肯定能改的数只有 \(O(n)\)。 所以从底到顶dp即可。 原问题发现可以类似做，总复杂度 \(n^4\)[AGC020E] Encoding Subsets
题意：一次加密形如将 \(aaaaa\to(a\times
b)\)。 001001001 ->
001001001、00(1(0x2)x2)1、(001x3)。
问一个0,1字符串的所有子集可能加密方案和。
题解
很奇妙，实际上考虑对于单串和子集，实际上是差不多的。 我们设 \(f_i\) 表示做到了 \(i\)。每次往后加入一个最简的串，进行更新。最简的串就是有括号的或者单字符。 子集和单串的差距就在这里。 然后直接dp就好了，但是状态数可能很多。状态数分析
考虑长度小的 \(<=12\) 只可能有 \(2^i\)。 同时长度长的也一定是有限的原本的串按位与得到的。 我们考虑对于长度 \(l\) 位于 \([x,y]\) 的串，任何一个按顺序分解的 \(d,d\times l\le N\) 的都对应一个可能的情况。 这并不多，总共只有 \(O(n^2)\) 个串。题意多次询问 \([l,r]\) 求出 \(i,j\in[l,r]\) 最小的 \(\mid a_i-a_j\mid\).
题解ds
很有趣的一道Ds题。 尝试直接进行扫描线，不劣，这一点我们必须要注意到。 如果当前 \(a_i-a_j,a_i>a_j\) 为最小值，那么发现，事实上如果 \(a_j < a_k <(a_i+a_j)/2\) 的是没有贡献的。 这启示了我们，事实上每次有用的更新会使值域折半，这样我们就可以暴力的去更新了。 总复杂度 \(n\log^2n\)
题解sqrt
很是震撼这种莫队。 首先直接回滚，确实我们很好删除，但是我们计算不了答案。 这时，竟然可以我们先删光，此时知道加入的顺序，我们在加入是算答案。 这个真的好鈟，我超。 具体来讲，我们回滚两次分别计算贡献。或者说，我们先计算 \([b,r]\) 移动右端点这段的贡献，然后计算块内贡献，与块内和 \([b,r]\) 产生的贡献。 （这样做似乎和分块神似了）同时不要忘记了分块，很经典的，我们统计大块到小块，小快到小块，小块到大块这些贡献。题意，我们记区间 \([l,r]\) 的权值为 \(i\in[l,r]\) 的并。问前 \(k\) 个区间的权值和是什么。
题解
我真的想过二分，可是真的不知道二分有啥用/kk 二分真的有用。 但二分前，我们还是要考虑如何解决一次区间查询。 考虑从左向右进行扫描线。当然，这时候我们优先让后来的覆盖之前的。（这里仍然体现的是不劣思想，因为我们是向右扫描线，所以要保留的尽量靠右。） 考虑我们将数轴上每个位置标上现在最靠右的好处是什么。显然能发现，如果现在左端点达到了这个点，才会产生贡献，否则不会。 此时贡献变成若干二维数点形状的东西。 事实上，总共上我们只会有 \(O(n)\) 种不同的区间。 这样便可以较为容易的 \(O(n\logn)\) 的求一个区间的答案了。 考虑由于并是由单调性的，所以合法的区间一定是一个前缀之类的。此时二分即可。 这样的复杂度是 \(n\log^2n\) 有点差，考虑修改都是形如前缀加，我们可以直接转化为全局加，后缀加，考虑我们移动方向都是向右，所以可以直接维护后缀和数组。又是一道猜重心的题呢。这次我们需要在 \(n=7.5\times 10^4\) 个点中，问 \(m=2\times 10^5\) 次两点间距离，猜到重心。
500组数据。
题解
互测那个题如果我们知道一条覆盖了重心的链的话，这时候猜重心是很简单的。 那这个题呢？分析一下，确实如果我们确定重心所在的一条链上的话，可以用 \(2n\) 次询问问出来重心。 我当时没有去想如何找到这条链，而是去想如何优化这 \(2n\) 次，所以一点都没想到。 我们要去找到这条链。 考虑我们维护一条链，随机选若干个点，计算出他们到链两端的距离。 我们选取这条链上最重的点那个集合，把链的一段改为这个集合中 任意 一个点。 我们改的一端是较轻的一端。 考虑如果我们现在重心在链上，却被我们抛弃的概率是什么？这当且仅当重心落在了较轻的一端，发现较轻的一段最多有 \(s/4\) 个点，概率为 \(\frac{\binom{n/2}{s/4}\binom{n/2}{s-s/4}}{\binom{n}{s}}\) 这个离中心太远了，带入数据算一算可以发现这个概率极低。 所以我们就可以大概可以理解成我们每次有一定的概率把重心放入链中，有一个很小的概率把重心扔掉。 最重的集合包含重心的概率为 \(\frac{\sum_{i=s/2}^s\binom{n/2}{i}\binom{n/2}{s-i}}{\binom{n}{s}}\) 然后包含重心的概率为 \(1/2\)。我们相信迭代次数够多的情况下，几乎一定能得到重心。（看起来这个概率不会低于 \(1/4\)，那么期望四次）每次交换 \(a_i,a_j\) 并且交换后变成 \(-a_i,-a_j\)，给你一个排列，构造一组 \(\le n+1\) 次的。
题解
首先假如有负的那很开心呀，我们直接一次就可以让他归位，但是实际上没有负的。 考虑每一个环的答案。通过打表我们很震撼的发现，我能找到一种构造的规律，但是最少也要 \(n+1\) 次，很伤心。 所以我们考虑最简单的情况，两个环最少次数是多少，继续打表又发现竟然能做到 \(n\) 次。这就启示我们，把环两两配对，然后每一对 \(n\) 次，剩下的一个就可以直接暴力 \(n+1\) 次。构造也可以通过表看出来！！（因为我们大概上要每一次swap都有意义，这使得答案方案很可以推下去。）把一个有向完全图删边，删一次问一次 \(1\leadsto n\) 最短路。
题解
感觉std的做法很有道理，想不到真的菜的真实。（动态加点的spfa应该就是没有卡） 当时其实也去想折半了，但人傻呀，单纯的以为我要枚举4个点，怎么看都不像好做的。 还是考虑这个转移是分层的，直接考虑长度为 \(4\) 不好做，但是考虑长度为 \(4\) 的一定是从 \(1,2,3\) 转移过来的。 这样长度是 \(3\) 的新增转移一共只有 \(n^3\) 个（如果连着 \(1\) 的话，只有 \(n\) 条 \(n^2\) 转移即可，否则只需要枚举一个点。） 但是长度是 \(4\) 的话，有一段是一条二元链，这样还是 \(n^4\) 的。我们就考虑直接维护所有的 二元链 即 \(A^2\)。发现单点修改，一次影响量是 \(n\) 的。（事实上静态若使用类似的做法，如果不预处理二元的情况，也不得不四次方。）奶牛从 \(1,n\) 编号，有 \(m\) 对朋友，奶牛从 \(1,n\) 顺序离开，离开后他所有的朋友互相成为朋友，问新增的朋友对数。
题解
考虑我们一次修改，产生影响一定是他所有连的边的最小值出出现。 这样考虑下去，我们每次向这个最小的点连边，最终一定产生一棵树。 现在相当于合并集合了，在树上自然可以启发式/线段树合并。做到 \(m\mathrm{polylog(n)}\)。题意，定义一个01串一个区间的权值 \(w(l,r)\) 是把他变成回文串最少需要的 swap 次数。问这个串所有区间权值和。
题解
一个区间权值怎么算？考虑我们依旧是需要保证相对顺序的。同时 \(l,r\) 对称（回文）也必须保证 \(l+r=k\) 这样的限制，所以每一对\(1,1\) 的答案就形如 \(|a_i+a_j-k|\) 这样的。 我的做法是从最中间的一对 \(1,1\) 向外每次扩展两个 \(1\) 算贡献的。 考虑上次那对位置是 \((b,c)\) 这次这对是 \((a,d)\)，那么所有可能的区间左右端点和为 \([a+c,b+d]\) 不难发现总共枚举两为 \(d-c+b-a\) 这恰好可以均摊程长度。 如图所示
我们上次的答案是橙黄色的，我们先将他移动到红色，再把它移动到蓝色位置，发现两次移动都是均摊的，所以总复杂度是
\(n^2\) 的。
（我当时询问查询搞反了，我把多次询问搞成了算贡献一次询问。真的蠢，最后变成了等差数列和，\(n^2log\) 还没跑过去。痛失AK）。
定义合法的序列为：Alice先手必胜，每次将一个棋子移动到他左面任意一个位置（棋子不能重叠，同时也不能跨过别的棋子。），问长 \(n\) ,\(m\) 个棋子的序列有多少个。
题解
真实的菜，只能打表发现结论。 就很朴素，我打了个表发现规律和棋子的奇偶性有关（奇数就是在最左边随便填一个，偶数就比较复杂，感觉像是异或了一个数）。 然后我发现规律就是从右向左，奇数位xor=0的都是合法的，偶数位不用管。 哇很神奇呀，写个dp就过了！！ 当然dp不是很困难，我们可以 \(nm\log n\) 来做他也可以 \(m^2\log n\) 做。考虑单点查询，所以二进制拆分必须恰好符合，每次枚举这一位 \(1\) 的个数在维护进位即可。 但这个结论为啥对呢？ 考虑变成这样的一个放石子游戏，我们把序列差分-1，然后移动就相当于把棋子扔到下一个（右）堆里。 考虑在偶数位置的移动，先手不管怎么移动后手都可以重复移动相应数量转换先后手。同样的如果后手不按照这个方式移动，若他移动了奇数位我们就认为他仅仅在进行普通的nim，接着跟他玩就好，否则他移动偶数位我们就把他移动的给继续向下移动。1-2
题面不长，大概就是满足 \(\sum a_i=x,a_1\mid a_2\cdots \mid a_n=y\) 的所有长度为 \(n\) 数组 \(a\) 的异或和。
首先赛事的想法是，枚举 \(x\) 这个数出现次数，接下来组合数结果必须是奇数说明出现次数是 \(n\) 的子集，拆位算贡献，然后暴力记录进位情况，这只有 \(\log n\) 种，然后转移即可。
这是个 \(\mathrm{polylog(n)},\log^3(n)\)? 的dp。
可是我忽略了一件事，就是说我们计算的只不过是或起来是 \(y\) 的子集的答案。这是说明容斥是至关重要的，很可惜我在考试结束后才想到这一点。
这样做是个 \(2^n\log^3(n)\)
的，似乎好像gyh老师写的类似？（我不确定）。没啥前途。
正解很强大。既然容斥不可避免我们提前容斥，看接下来的做法会不会有变化。现在的限制形如 \(a_i\subset y'\)。
最神仙的一步是反用lucas \([a_i\subset y']=\binom{y'}{a_i}\bmod 2\)。这一步，太厉害了。然后考虑此时答案变成了：
\[ \begin{aligned} \sum_{\sum_{a_i}=x}\binom{y'}{a_i}=[z^x]((1+z)^{y'})^n=[z^x](1+z)^{y'n}=\binom{y'n}{x} \bmod 2=[x\subset y'n] \end{aligned} \]
结束了。 我们现在，已经得到了一个 \(O(1)\) 计算出现次数的方法。这样总的复杂度就是 \(O(y\log y)\) 我不清楚是否可以做到 \(O(y)\) （因为考场时候我的dp是可以和计算出现次数复杂度一样的计算xor）。