初赛
打得第 \(3\) 场。link。
省流：\(6\) 题，rk 35，没过 F，输麻了。
过题顺序是 A->D->B->C->E->G->(F)。
F 没调完。
简要 sol：
- A：
过题时间：00:09:08，无罚时。
难度：大概 1500？
二分答案一下，然后没了。复杂度 \(\Theta(n\log{v})\)。
- B：
过题时间：00:25:28，一发罚时。
罚时原因：数组开小了。
难度：大概 1600？
容易转换成 \(n\) 次区间加，然后问你有多少个点最终的值膜 \(4\) 为 \(1\)。
离散化，差分，然后做完了，复杂度 \(\Theta(n\log{n})\)。
- C：
过题时间：00:32:47，无罚时。
难度：大概 2100？
由于一改就是改所有字符，而且问我们要改哪几个字符，并且不同字符间相互独立，所以我们分开了考虑，对于每个字符把原来的字符串视为关于他的 \(01\) 串，然后进行哈希。
则询问时要改这个字符当且仅当其在 \([l_1,r_1]\) 和在 \([l_2,r_2]\) 的哈希值不同。
然后就做完了，复杂度 \(\Theta((n+q)|\Sigma|)\)。
- D：
过题时间：00:14:04，无罚时。
难度：大概 1000？
最签到的题，按题意模拟即可，没什么好说的。复杂度 \(\Theta(n^2)\)。
- E：
过题时间：00:56:05，无罚时。
难度：大概 2300？
整场比赛质量上最出色的题。
事实上题目就是问把 P 或者 O 全部移到一棵子树里的代价。下面以 P 为例。
我们记录一下一共有 \(c\) 个 P，则我们要把 P 全部移到 \(u\) 的子树内（并且使得其中只有 P），那么需要满足 \(siz_u=c\)。
然后考虑计算代价，显然原本就在 \(u\) 子树内的 P 没必要再移动，我们只需要关心把 \(u\) 子树外的 P 移到 \(u\) 子树内的代价。
设 \(u\) 子树内非 P 点的集合是 \(S\)，\(u\) 子树外的 P 点集合是 \(T\)，应有 \(|S|=|T|\)。则我们应将 \(x\in S\) 和 \(y\in T\) 一一配对使得 \(\sum \text{dis}(x,y)=\sum d_x+d_y-2d_{\text{lca}(x,y)}\) 尽可能小，然而我们发现 \(\sum d_x+d_y\) 是定值，且 \(\text{lca}(x,y)=\text{lca}(u,y)\)，这说明了事实上配对是无意义的，也就是 \(\sum \text{dis}(x,y)\) 是个定值。
其中 \(\sum d_x+d_y\) 是很好计算的，我们考虑如何计算 \(\sum\limits_{y\in T} d_{\text{lca}(u,y)}\)；我们考虑枚举 \(lca\)，则 \(lca=fa_w\) 时对于答案的贡献就是 \((g_{fa_w}-g_{w})d_{fa_w}\)，其中 \(g_u\) 表示 \(u\) 子树内的 P 点个数。
而对于点 \(u\) 我们事实上就是对于上面这个东西进行点 \(u\) 到根节点的求和，我们做一个前缀和即可。
然后就做完了，复杂度 \(\Theta(n)\)。
- F：
过题时间：没调完。
难度：大概 2400？
我们考虑把 \(t\) 串中按特殊字符的间隔把不含特殊字母的连续字符串剥离出来，然后考虑把这些串丢到 \(s\) 上去匹配。
我们注意到，除了最后一个串外，其余的串都要尽可能的往前放，感性理解一下，第一往前放不会吃亏，因为我后面能放的还是能放，第二我后面原来不能放的我现在往前放了反而能放了，这样就更优了。
特殊地，对于最后一个当然时尽可能往后放。
至于一个地方能放上的条件就是距离上一个放串的地方中间隔的距离不小于他们两个在 \(t\) 串中间隔得 + 数；注意对于第一个和最后一个串我们也要考虑第二个条件。
然后我们用字符串哈希一个一个匹配过去即可，复杂度是可以摊掉的，为 \(\Theta(n)\)。
- G：
过题时间：02:04:22，一发罚时。
罚时原因：手欠交了个暴力。
难度：大概 2400？
先考虑线段树，注意到有一个 \(\Theta((n+q)m^3\log{n})\) 的矩乘做法，然而复杂度难以接受。
所以考虑分块。设块长为 \(B\)。
先考虑暴力如何写，显然时每次能攻击就攻击，这样必然不亏，又能给后面的能量槽留够空间。
对于每一个块，我们考虑记录两个数组 \(\{f_m\},\{g_m\}\) 分别表示，我最初有 \(i\) 的能量，走过这一个块后我能量会变成多少和我能产生多少攻击。
修改时，对于修改点所在的块，暴力重新计算 \(\{f_m\},\{g_m\}\) 即可，复杂度 \(\Theta(mB)\)。
询问时，整块暴力计算，散块使用上面得到两个数组可以快速计算，复杂度 \(\Theta(B+\frac{n}{B})\)。
欲令复杂度最优，由于 \(B\le mB\)，则令 \(mB=\frac{n}{B}\)，得 \(B=\sqrt{\frac{n}{m}}\)。
计算得此时复杂度为 \(\Theta(n\sqrt{nm})\)，可以接受。
决赛
省流：八题，总榜 rk 75，小星星 rk 27，Ag。
大概是过了 t1，t2，t3，t4，t5，t6，t7，t9。
唉唉，题解摆了/shui
后面看来 t8 和 t11 大抵也差不多场上都想完了，只不过因为时间/心态因素没有写出来/ll
标签：text,复杂度,过题,lca,Astar2024,Theta,sum From： https://www.cnblogs.com/lsj2009/p/18383689