Solution Set 2

\(\text{「CF1037H」Security}\)

有关字典序可以依次考虑 \(T\) 的每一位转化为询问 \(\mathcal O(|\Sigma||T|)\) 个字符串在区间 \([l,r]\) 的存在性判断。因为可以用线段树合并维护 \(\text{SAM}\) 上每个等价类的 \(\text{endpos}\) 集合，所以将存在性判断离线放在 \(\text{SAM}\) 的每个节点上在通过一次线段树合并依次回答即可，复杂度为 \(\mathcal O(|S|\log |S|+|\Sigma||T|\log|S|)\).

\(\text{「CF1017G」The Tree}\)

直接暴力，发现修改涉及到规模为 \(\mathcal O(n)\)，而查询却只有 \(\mathcal O(1)\)，所以考虑将修改复杂度摊到查询上。发现一条链上 \(1\) 操作的顺序并不影响最终染黑的节点，所以定义 \(w_u\) 为 \(u\) 向下扩展的层数，如果 \(w_u=-1\) 表示不扩展，初始时 \(w\) 全为 \(-1\)。这样 一段链的和表示从链头扩展到链尾的层数，如果 \(\sum w_u\ge0\) 则表示链尾被染黑。所以修改只需单点加，而查询只需查询 \((\text{root},u)\) 的最大后缀和是否大于等于 \(0\) 即可。而 \(2\) 我们只需将子树全清空为 \(-1\)，再将 \(w_u\) 赋为到根链最大后缀和值减 \(1\)，复杂度为 \(\mathcal O(n\log^2 n)\).

\(\text{「AGC018C」Coins}\)

先钦定所有人对选择金币，我们令 \(u_i=b_i-a_i,v_i=c_i-a_i\)，若是 \(v_i+u_j<u_i+v_j\) 则 \(j\) 选择银币时 \(i\) 必定选择银币，所以我们可以按 \(u_i-v_i\) 排序，则序列分为两段，前一段选择铜币，后一段选择银币，直接优先队列维护即可，复杂度为 \(\mathcal O(n\log n)\).

\(\text{「AGC093F」Dark Horse}\)

发现 \(1\) 无论在哪个位置方案数都是一样的，不妨将其放在 \(1\) 号位统计答案在乘上 \((2^n)!\)，答案符合即是 \([2,2],[3,4],[5,8],...,[2^{n-2}+1,2^n]\) 这 \(n\) 个区间最小

\(\text{「雅礼集训 2018 Day10」} 贪玩蓝月\)

考虑如果物品槽是一个栈，可以用 \(\mathcal O(mp)\) 的 \(\text{dp}\) 做，删除时直接回到上个状态即可，考虑如何扩展到双端队列。

有个经典 \(\text{trick}\) 就是双栈维护双端插入删除元素。该 \(\text{trick}\) 可以双端插入删除，维护半群运算，做到均摊 \(\mathcal O(n)\) 次运算。

用两个栈分别维护前后端的插入删除。

如果一个栈空了，考虑将另一个栈的元素按中点划分开，分别装入两个栈。

复杂度考虑势能函数 \(\Phi(t)=|\text{size}_1-\text{size}_2|\)，即两个栈的大小之差。每次 \(\Phi(t)\) 最多增加 \(1\)，重构时 \(\Phi(t)\leftarrow 0\)，所以复杂度是均摊 \(\mathcal O(1)\)。

用这个 \(\text{trick}\) 即可做到 \(\mathcal O(mp)\).

\(\text{「SDOI2017」} 苹果树\)

首先转换题意，发现 \(t-h\le k\) 可以看成原树上免费选一条从根出发的任意路径，再在此基础上选择 \(k\) 个苹果。

观察到每个节点必须先选一个苹果才能再选苹果是类似一种树形依赖关系，可以将 \(a_i>1\) 的节点 \(i\) 拆为两个点，分别有 \(1\) 和 \(a_i-1\) 个苹果且后一个节点依赖前一个节点。

然后这题可以