NOIP 2023 游记
Day 0
打了一场模拟赛，分数中规中矩。原定计划是在 NOIP 前一天把 11 月做的题目写一下题解，做一个整理，但是下午还是摆了。晚上回家简单看了几道之前做过的题目，然后看了两集番，11 点钟睡觉。
dfs 序优化树上依赖性背包学习笔记
我们知道对于树上背包，若每个结点上只有总大小为 $O(1)$ 的物品，则总复杂度为 $O(n^2)$；若再限制背包大小为 $m$，则总复杂度为 $O(nm)$。
Solution. LG3863 序列
Description
给定长度为 $n$ 的序列，$q$ 次操作，操作有两种：
- 区间加减；
- 查询某个位置上的数在多少个历史版本中 $\ge k$。
$2\le n,q\le 10^5$