一天一道慢慢写着。因为菜所以一开始只有 easy round。
TEST_68
简化一下限制。注意到很多点都能取到最大值，具体的，若最大值为 \(x,y\) 处取到，那么只有 \(1\rightsquigarrow x,1\rightsquigarrow y\) 路径上的点取不到。而一条链是非常好做的，直接 dfs 下来就行。时间复杂度 \(\mathcal O(n\log w)\)。
- 这种简化限制的思路非常好用。另一个经典的例题是树上路径 mex 的 \(\mathcal O(n)-\mathcal O(1)\) 求法。好像是叉姐给 hdu 2014 多校出的题来着。
TEST_152
区间 assign 肯定是想 ODT 啊啊啊，为啥有人想不到啊啊。
考虑对操作扫描线，用一个树状数组维护后缀和即可 \(\mathcal O(m\log m+n\log n)\)。这么简单。这么不会。
- 区间 assign 考虑颜色段均摊。
- 树状数组维护操作贡献后缀和。