Preface
我真服了，T3 没判枚举范围然后 RE 了？？？好在 lemon 神机放我过去了。好一个 24 年 S T2 的区间覆盖运用（）
嘟嘟嘟。
T1
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(100\) | \(100\) | \(0\) |
水题。按照题目所述模拟一下就可以了喵喵喵！
T2
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(100\) | \(100\) | \(0\) |
考虑前后缀和分别统计一下进攻和防守的人的战斗力总和，然后枚举 \(pos\) 算一下取个绝对值的 \(\min\)。
T3
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(100\) | \(100\) | \(0\) |
某巨佬：怎么暴力匹配字符串来着？算了写 KMP 吧，保险一些。
考虑先暴力找出 \(s\) 中所有什么嘤嘤串的区间，由于至多只有 \(n \le 10\) 种嘤嘤串，所以至多不会超过 \(n|s| \le 5 \times 10^6\) 个区间是能容纳下的。
于是题目就转化为找到尽可能少的一些位置，使得对于任意一个区间都包含至少一个选定的位置。显然是一个区间选点（？）或者叫区间覆盖（？）的典题。
怎么做呢，非常简单，先把这一堆区间按照优先右端点升序、其次左端点升序的顺序排序，每当枚举到一个区间，就用这个区间的右端点选定为位置，然后不断找到最后一个包含这个右端点的区间，这一系列区间就都可以用上这个右端点。剩下的继续匹配即可，不难证明这一定是最优方案。
时间复杂度是 \(O(len \log len)\)（\(len \le n |s|\)）的，瓶颈在于排序，说实在确实不太优，但是 lemon 神机肯定会放我过去的好吧！！111
T4
| 估分 | 得分 | 挂分 |
|---|---|---|
| \(100\) | \(100\) | \(0\) |
乱搞题嘟嘟嘟。
考虑把两种操作分开讨论，建两张图——都是有向图，但是一张是从深度小的点连向深度大的点，还有一张是从深度大的点连向深度小的点。根据树的结构和这什么深度的性质，显然两张图都无环（DAG）。
于是每次操作的时候，就在其对应图上的对应节点累加权值。对我们是离线做，所有询问都标记好权值之后，跑两次拓扑排序（图是 DAG，肯定能把每个节点都遍历到），这样就能找出两种操作分别对每个点的贡献，最后加上每个节点原先的权值之后输出即可。
时间复杂度是线性的吧……好像是的嗯。复杂度还是很优秀的喵。
Summary
呜呜呜终于 AK 了一场了，上次 AK 还是在几个世纪以前（哭
嗯！但是这次的 AK 也是用运气捡来的！本来 T3 很可能会挂的……以后一定一定要注意判边界啊！！！111
继续加油喵喵喵喵喵 /fendou