简述
突然记起来 CSP 前特别喜欢的 POI 题还有一堆没写，所以就有了这个坑。
AtCoder Grand Contest 028E:High Elements – 题解
主要思路
神仙题啊，灵活运用线段树和贪心的好题。首先一个显然的性质：\(X\) 串的 \(\max\) 序列是原串 \(\max\) 序列的前缀串。知道这个之后我们可以开始构造。
后缀自动机 | SAM
概述
后缀自动机是处理字符串信息的有力工具。后缀自动机存储在 Trie 树上，配合 Link 指针就可以被认为是一张 DAG。任意一条从原点出发的路径都可以被认为是这个字符串的一个子串，且在后缀自动机上不会存在重复的子串信息（然而，我们可以进行一些扩展来维护子串位置信息）。
「杂题集」- 2019年9月19日
方格取数
看一眼复杂度，\(O(nm)\)级别的，考虑两个循环的 DP。分析整个题面之后发现，我们穿过边界时，当且仅当另一个连通块的权值比当前的大，否则便不会为了穿过边界而损失当前金块。所以，我们做一个 DP 一样的东西：因为发现每个格子只能走一遍，那么在每一列你只能选择一直向上走和一直向下走，所以这个 DP 便没了后效性，然后再处理连通块之间的连接判断就做完了。
「Fortuna OJ」4605 – 排序 sort 题解
主要思路
这道题好有意思啊，提醒我在任何时候都要想到这种阈值+\(0/1\)转化的方式。
我们可以先二分出\(c\)位置的值，然后令所有大于等于\(c\)的值变成\(1\)，小于的则变成\(0\)。然后排序的时候发现，其实就是重新组织零一的位置，所以用线段树区间修改就可以搞定了。最后判断\(c\)位是否为\(0/1\)决定要不要继续二分。
「2018泉州国庆集训#3」 – 解题报告
A – 人类基因组
这套题全都是暴力出奇迹系列。
我们枚举一个端点，然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\)，然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。
然后用 sb 线段树搞下就行了，太特么傻逼了。