AT_dp_t Permutation

只关注相对排名不关注具体的值，所以可以状态里记最后一个数在已经填的数里的相对排名。

如果直接记录已经填了哪些数，会发现其实多记录了太多信息。因为具体值是没有必要的，6相对于7和相对于9的大小关系是一样的。

AT_dp_o Matching

直接记录女生的状态的话，其实是不用枚举现在匹配到哪个男生了的，因为男女是一对一的，你知道匹配了几个女生就知道到哪个男生了，而几个女生在状态里就有。

这个是直接把男生那一维压掉了，不是滚动数组，因为女生的状态一定是从匹配的少向匹配的多的转移，不会有影响。男生那一维属于冗余。

AT_dp_w Intervals

你以后遇到：

大量区间 [l,r]，每个区间对某种选择产生贡献。

可以产生一个非常值得尝试的思路：

按右端点扫描
↓
当前区间什么时候“结算”？
↓
维护一个描述未来的状态
↓
区间贡献可能变成对一段状态的加法

然后才考虑：

线段树
BIT
单调队列

这种区间题在从左往右扫时可以在右端点结算一个区间，因为往后面扫再也不会和这个区间有关系