2022-10-22
cqnk供的题，不知是不是上次给的难度太高，然后被喷了，这次难度直接下了一档
》
T1 比较
==noip T1，又或者是我刚睡醒脑袋不太好使，反正瞎搞了一会儿才发现其实暴力就行了。具体的就是每次保证至少消掉一辆坦克即可，然后就是模拟
》
T2 不好评价，就是暴力是一眼就会，考虑优化暴力，其实就是发现暴力里头是有两个操作，一个是 \(O(1)\) 的，另一个是 \(O(b\cdot 2^b)\) 的，然后就是直接做是 \(O(n+n\cdot 2^b)\) ，直接考虑均摊两个操作的复杂度，我的做法是分块，块内暴力转移，做完一块后再对整个块高维前缀和算贡献，大概是 \(O(\frac{n\cdot b\cdot 2^b}{B}+n\cdot B)\) 的，调一下块长过了，实际上还有更优的优化方法，就是我对前 \(\frac{b}{2}\) 做高维前缀和，后面的暴力枚举，实际上更优一点
》
T3
<<noip T2，就是发现一个点无法被消除的条件是不存在某个颜色出现在两个或以上的子树中，直接线段树合并
》
T4
==noip T3，乍一眼发现不太会做，然后仔细思考发现就是有点像P3426 [POI2005]SZA-Template，然后就是直接往border上想，然后就是可以把kmp的fail树建出来之后就把题目转换为统计哪些祖先能对后代产生贡献，转化成了一个序列问题，然后需要支持一下操作
<1>对于当前在线段树上的节点，区间加上某个值
<2>给线段树插入某个节点
<3>单点求值
<4>询问某一个前缀，使得前缀的最大值不超过k
然后直接魔改一下动态开点线段树然后加一个启发式合并即可，可惜想完之后距离比赛结束还有不到20min，我肯定打不出来，就打了部分分滚粗咯