发现快省选了，而我啥也没干过，转肯竞预定。                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    

2.20

3道题（2.11）

T1

数据分块

T2

数位dp+容斥

T3

发现这张图的重要性质是i最多一步走到i+2，某种程度上说i-1前的与i+3后的不相干，都要从i到i+2决策。

考虑分支，对于分治区间[l,r]，拿出mid-1，mid，mid+1，O(n)dp求出每个点到这三个点的最短路，接下来考虑怎么求解left对right产生的影响。

先考虑拿出两个点的情况，即对min(dis[i][1]+dis[j][1],dis[i][2]+dis[j][2])求和，这个东西分别计算取前者和后者的情况，用线段树维护个数和dis和即可计算。

那么对三个点的情况也是一样，用二维线段树维护，再套上分治即可得到O(nlg3n)的优秀算法。此时离线一维，用主席树维护即可。

2.21

3道题（2.12）

T1

线段树，每个节点维护子树内每种数位的权值和及每种数位被全部修改成了什么，便可以进行push_down

T2

应该是费用流，类似修车？

T3

发现每次一定是走1*y或x*1的形式，那么似乎对每个格子维护转移区间，重载pair加法就可以做了？

看了下后面一套题，十分神仙，T1忘了回文自动机怎么写T2计几肯定不会T3看起来是生成函数+多项式理论，完全不会。

2.25

转角遇到czf祭。。

鸽了三天非常舒服，主要是题目不会做了。

13号的T1，SA+PA数组构造原始字符串。这个我一直以为有道题是 用SA构造字符串，但是好像很不可做。事实上是用PA数组的性质，即O(n)个本质不同的信息告诉你哪些字母是相同的，然后用SA数组就可以判出两个字母的大小，然后把一样的并在一起，不一样的跑个拓扑就好了。实际上还是用了PA的性质，SA数组并没有什么好深究的。

先学习了一下多项式的exp和ln运算，还有看了下WC生成函数的课件，预计几天内会补到WC总结里去，然而还是不是做这道题，太神仙了。

2.26

来更一下上午想到的两道题。

14号T3大概是f[i][j]表示点i选j的方案数，用莫比乌斯反演+预处理，大概可以在nmlgm的时间内暴力搞过。