2020.07.18 2020牛客暑期多校训练营（第三场）

2020.07.20 2020牛客暑期多校训练营（第四场）

2020牛客暑期多校训练营（第三场）cjy J/K xx H zrx I

Codeforces Round #657 xx F zrx E

2020牛客暑期多校训练营（第四场）cjy E/J xx A zrx I

Codeforces Round #658 xx C zrx D cjy E

编辑了AC自动机初稿

编辑了后缀数组初稿

编辑了笛卡尔树初稿

2020.07.19 Codeforces Round #657 (Div. 2)

2020牛客暑期多校第3场E题

题意：

给一个数组a，求排列p、q，满足p、q各位均不相等，p、q中均是二元环。(n为偶数) 求$\frac{1}{2}$$\sum_{i=1}^{n}a~i~-a~pi~$与$\frac{1}{2}$$\sum_{i=1}^{n}a~i~-a~qi~$的和的最小值。 题解：

n=4时，最小值为max-min；

n=6时，最小值为max-min；

n $\ge$ 8时，整块不会比切成4、6小块考虑更优。

然后动态规划就可以了。

题目

代码

笛卡尔树

笛卡尔树的查询操作时O(logn)的，如果是用来在线查找区间最值的话并不占优势，所以以前一直觉得它没什么用。这不就真香了……