2023NOIP A层联测26 总结
题目
T1 origen
大意
\(n,a_i\leq 2\times10^5\)
赛时思路
一开始想固定一个端点递推去求贡献，发现异或加上平方维护不了递推式，痛失 40 min。后面多的时间分给 T1 后接着想做法，考虑拆平方化代数式，然后平方项的因式分解忘了，导致后面一直认为平方项会被加多次，而正确做法只会加一次，平方项维护不了以后决定写暴力。
赛后思路
设 \(s_i=\bigoplus\limits_{j=1}^i a_j\)，考虑 \(s_i\) 的第 \(k\) 位带来的贡献，那么比 \(i\) 小的 \(s\) 的第 \(k\) 位如果和 \(s_{i,k}\) 相反，则可以给第 \(k\) 位带来一次平方的贡献。
对于后面的两项的积的两倍，枚举一下 \(j<i\) 的 \(s\) 中第 \(k\) 项和某一项的
T2 competition
大意
团队中第 \(i\) 位选手可以做出 \([l_i,r_i]\) 的题目，现在随机的选连续的若干个人参加比赛，求做出来题数的期望。
\(n \leq 10^6,m\leq 10^{18}\)
赛时思路
像期望题，但实际上是计数题，一直在想怎么样利用双指针或者其它 \(O(1)\) 到 \(O(\log n)\) 的数据结构维护某一点的计数，再转移到其它点。后来发现没思路，于是写了 \(20pts\) 的暴力。
赛后思路
题解链接：2023NOIP A层联测26 T2 competition - 彬彬冰激凌 - 博客园 (cnblogs.com)
考虑每道题被做过多少次肯定不现实，那么考虑每一道题有多少次没有做出来。
假设某一次可以做出来题 \(x\) 的人是 \(i\)，而 \(i\) 下一个人可以做出这道题的人是 \(j\)，于是题 \(x\) 有 \(C_{j-i}^2\) 次不会被做出来（区间可以是 \([k,k]\)）。
这样的 \(i,j\) 有多个，设 \(f_{x,i}\) 为第 \(i\) 个可以做出题 \(x\) 的人的编号（显然 \(f_x\) 具有单调性），于是 \(x\) 做不出来的次数 \(cnt_x\) 有：
\[cnt_i=\sum_{i=1}^{t_x-1} f_{x,i+1}-f_{x,i} \]\(t_x\) 为可以做出题 \(x\) 的人数。
于是最终答案为：
\[ans=m\times C_{n+1}^2-\sum_{i=1}^n cnt_i \]但这样做会 \(O(nm)\)，于是 tjm 有更好的做法。
可以建一个坐标系，\(x\) 轴是题目，\(y\) 轴是第 \(i\) 个人。
那么每个人的做题情况都可以用一条水平的线段来表示。
回到答案式，实际上我们不需要求出 \(cnt_i\) 我们只需要知道 \(\sum_{i=1}^n cnt_i\) 的值就好了。
那么我们可以把每次加入一个人的操作看做是在坐标系上加入一条线段。
对于每一道题目肯定都被一条线段覆盖，那么对于连续的一段题目，我们记录覆盖他们最后的线段的左右端点，然后将新加入的线段与有交集的旧线段求贡献（求在这之间会减小多少）。注意，首尾处的旧线段可能无法完全覆盖，需要拆成两条。
T3 tour
大意
有若干个节点，每个节点一开始没有边相连，每个点有一个值 \(val_i\)。
有两个操作：
0 x y 表示在 \(x\) 与 \(y\) 之间加一条边，保证加边后，图形成森林或者树。
1 x y 表示有一个人在 \(x\) 到 \(y\) 之间行走，每到一个点 \(i\)，将他的值 \(k\) 与 \(val_i\) 比较，如果 \(val_i\leq k\) 那么交流成功，在这之后，\(k\) 会加上 \(val_i\)，初始时 \(k=0\)，求交流成功次数。
部分测试点强制在线。
\(n\leq 10^5,q\leq 5\times10^5,|val_i|\leq 5\times 10^3\)
赛时思路
发现是一棵树以后，可以大致分为在 \(lca\) 两侧考虑，又有可以以点 \(x\) 为根，求前缀和与 \(val_i\) 比较。
后面一直在想可不可以考虑主席树动态维护前缀和，没往答案式变形去想，也没往换根去想。后来还是去写了暴力，然后一直没调出来，后来发现 \(q\) 的数组开小了……
赛后思路
应该有一个 \(60pts\) 的做法可以用换根线段树动态维护前缀和，不过正解的主席树更巧妙。
题解链接：2023NOIP A层联测26 T3 tour - 彬彬冰激凌 - 博客园 (cnblogs.com)
首先考虑一个点 \(p\) 能计入答案的情况，就是 \(dis(x,p)-a_p \ge a_p\)。 我们把 \(x \to y\) 的路径拆成 \(x \to lca,lca \to y\) 两条。
记录一个点 \(x\) 到根路径上的前缀和为 \(s_x\)，对于两条路径，我们分类讨论：
第一条，合法条件为 \(s_x-s_p \ge a_p\)，也就是 \(s_p+a_p \le s_x\)。左边的是一个关于 \(p\) 的式子，我们把它放到某个数据结构里面，查询一条链上小于等于给定值的值的个数，如果树给定，这显然是可以通过主席树来做的。
具体来说，每个点继承它父亲的版本，最后把两个版本一减就好了。
第二条，我们记录 lca 的父亲为 \(z\)，那么合法条件为 \(s_x-s_z+s_p-s_{lca}-a_p \ge a_p\)，也就是 \(2 \times a_p-s_p \le s_x-s_z-s_{lca}\)。
左边是一个关于 \(p\) 的式子，右边是一个定值，也可以用类似的方法通过主席树求出。
那么允许离线的方法就很明显了，先建出树，然后对于每个点维护两棵主席树，分别表示第一种和第二种情况，然后查询的时候拆成两条路径分别查询即可（注意不要重复算 lca）。
现在考虑在线。一个经典的方法是启发式合并，由于答案和树的形态无关，可以每次把 size 小的连通块合并到 size 大的连通块上，对于 size 小的那个连通块，我们暴力重构需要维护的信息，包括倍增数组、前缀和数组和主席树。然后正常查询就好了。
启发式合并的复杂度是 \(O(n \log n)\)，再加上重构倍增数组和主席树，复杂度就是 \(O(n \log n \log V)\)。
T4 abstract
大意
\(n\leq 10^5,a_i\leq 10^9,叶子个数 \leq 100\)
主要还是一个抽象。
赛时思路
由于前面套了两个 \(\sum\)，很不友好，赛时想了大概 10 分钟，发现了路径越远 \(g\) 越小 \(f\) 越大，其实对于一条路径 \(f,g\) 不会超过 \(\log V\) 个，然后后面不知道要怎么处理这个性质，后面 T3 调不出来，T4 也没写暴力。
赛后思路
题解链接：2023NOIP A层联测26 T4 abstract - 彬彬冰激凌 - 博客园 (cnblogs.com)
和赛时差不了多少。
对于每一个节点，到该节点的子树内的叶子节点的路径中（包括路径上的点），出现的值只有 \(k\times(\log V+\log V)\) 个。
那么在以该点为终点，以子树内节点为起点的路径中，取值只有 \(k\times(\log V+\log V)\)。
这是因为，如果以某个非叶节点为起点到该点的路径中，取值严格包含在：到该节点的子树内的叶子节点的路径中出现的值。
我们可以叶子开始向父亲传值，如果父亲有多个枝丫，那么将枝丫的结果合并，由于这样的枝丫不超过 \(k\) 个，此处为 \(O(k^2\log^2 V)\)。
那么最终时间复杂度为 \(O(k^2\log^2 V \log A+nk\log V \log A)\)。
此处 \(\log A\) 为快速幂时间复杂度。
为了消去这个 \(\log A\)，可以使用光速幂，\(O(1)\) 查询。
不过快速幂可以卡过（乐：D
赛时
开始划分时间：T1:50；T2:50；T3:40；T4:30。
\(T1\) 一开始的思路是前缀和计数，有点钻牛角尖，想了将近 \(30\) 分钟多没想出来，接着去做 T3。
T3 想冲一冲离线的 50 分，想到前缀和与主席树缺一直没有发现可以用主席树动态维护前缀和的换根，后面不行了去想 T4。
T4 不是很有思路，探究完 \(\log\) 的性质就不知道怎么做了，只好先放下。
回去接着攻 T1。
T1 想了 10 分钟左右觉得可以分位计贡献，然后就记错了平方项的因式分解，发现思路无法维护，于是 T1 多给了 10 分钟写暴力。
T2 后来困在了固定一点求值，递推传递值。一直没有想其他的角度，没时间了就先写了暴力。
T3 的话后面直接上暴力了，然后大样例一直过不去，检查数组时只看到了范围里的 \(n\)，忘记看 \(q\) 了，后面一直在调，然后考试快结束了，心态调崩了，后面暴力也没时间写，题也没调出来。
反思
T1 T2 T3 的失误集中在，在一个条路上走到死，没有学会变通，考试时思维要发散一点，不要老是把时间压在一条思路上。
T3 的问题首先在心态上，不可以因为一题的暴力就心态爆炸，后面还有暴力要写，如果不是 T3 或者考试还剩较长时间，后果不堪设想。
后面的检查也有问题，竟然没有看出来不同变量的取值不同，下次检查数组应该对着数组和数据规模一条一条对。
关于心态调整，一方面是比赛确实快结束了，调整来不及；但更多的是因为一点小的问题就误了大局，在训练赛中应该要注重培养避免这种小问题带来心态较大的变化。
标签：10,26,log,T3,T1,leq,联测,思路,2023NOIP From： https://www.cnblogs.com/binbinbjl/p/17819062.html