d1t1
树 https://www.luogu.com.cn/problem/P4092
我一眼看过去打了一个倍增 + 树链剖分 + 线段树 \(3log\) 大力写过
然后静静思考一下, 发现 \(dfs\) 序上线段树一个 \(log\) 完美解决
每次修改子树, 把每个位置上赋成深度最深的值
d1t2
排序 https://www.luogu.com.cn/problem/P2824
二分 + 线段树
二分答案, 每次假设答案是 \(1-mid\) 中的数字
然后我们把这些数字在线段树中全部变为 \(1\), 其他数字变为 \(0\)
那么排序只要根据升序降序把区间中所有 \(1\) 放到最前面或最后面
然后检查 \(q\) 位置是否是 \(1\)
d1t3
序列 https://www.luogu.com.cn/problem/P4093
只能更改一个数字, 我们先想一个 \(n^2\) 的大力 \(dp\)
设 \(f[i]\) 表示 \(1-i\) 中最长不下降子序列的长度
\(f[i]=f[j](i<j,a[i]\ge mx[j],mn[i]\ge a[j])\)
我们发现后这是个三维偏序.. 考虑一下 \(cdq\) 分治
每次右边的位置用左边位置的最大值来更新
d2t1
游戏 https://www.luogu.com.cn/problem/P2825
我们把横着的能影响的连通块和竖着的能影响到的联通块都标上号
每个能放炸弹的点对应着两个编号, 在他们之间连边
然后跑二分图最大匹配, 答案是最大匹配数
数据范围明示
d2t2
求和 https://www.luogu.com.cn/problem/P4091
斯特林数不会, 鸽子了
d2t3
字符串 https://www.luogu.com.cn/problem/P4094
先搞一波 \(SA\) 出来
我们容易发现答案有单调性, 二分一波答案
然后根据 \(height\) 数组的定义, 我们发现对于某个长度 \(len\), 以 \(c\) 开头的符合条件的子串的排名是一段连续的区间
这段区间我们可以用二分 +\(st\) 表 \(O(logn)\) 找出来
那么问题变成: 排名在某段连续区间内, 且下标在某段连续区间内有没有符合要求的子串
二维偏序问题, 可以拿主席树草掉
ddy 提供了 SAM 做法
我们还可以二分之后把问题看作 \(s[c......c+mid-1]\) 有没有在 \(s[a......b]\) 中出现过
那么我们找到前缀 \(s[c+mid-1]\) 对应的那个节点, 倍增跳到 \(parent\ tree\) 上第一个 \(len\ge mid\) 的节点
然后康康这个节点的 \(endpos\) 集合中有没有 \([a+mid-1,b]\) 中的数字
\(endpos\) 集合用线段树合并维护
来源: http://www.bubuko.com/infodetail-3500171.html