JOI Open 偷学记录

只偷了一题，被z宝吊打 /ll

把 a 排序，考虑 (a_{i+1}-a_i) 对于 (sum) 的贡献，显然取决于一个 (le a_i)，另一个 (ge a_{i+1}) 的 ((f_i,f_{i+1})) 的数量，也就是把前 (i) 小的数字插入数列，左/右尚未确定的数目，对这个 dp 就行了

但具体情况比较复杂，左/右是否确定的情况不同，而且端点（即在 (n) 个数插完之后位于 (1) 或 (n) 的数）的某一边无论如何都无法计入贡献。我们只需要把左边未确定的看成左端点，右边未确定的看成右端点，对连续段进行 dp 即可。至于端点的特殊情况，我们再开一维来记录端点个数。

(f_{i,j,k,d}) 表示前 (i) 个点中，有 (j) 个连续段，和为 (k)，端点数为 (d) 的方案数。答案即为 (sum f_{n,1,j,2})，转移比较复杂，具体看代码

由于 (n=1) 的时候端点数只会有 (1)，所以需要特判。

考虑只有前缀怎么做，就是直接在 trie 树上搞，如果只有后缀的话就翻转当前缀做。由于 trie 树上的点的编号是连续的（排序后），于是这题就变成了一个二维数点问题。

具体一点的话就是，对于前缀的限制我们直接把字符串排序，并求出询问时前缀对应的区间，而后缀的限制就直接离线+trie查询即可

代码比较简短，冲上了 loj 次短解，而且常数巨小

考虑给定平行线的斜率怎么做。可以画一条垂直于平行线的直线，通过点与直线做垂线的方式，把点一一对应到直线上。这样问题就转化成了求最大子段和。

可以证明最优解的平行线的斜率等于两点间的斜率，于是我们可以通过枚举两个点来枚举平行线。主要问题在于点在直线上的顺序会发生变化。

由于两个点之间的顺序只会变化一次，所以总变化次数是 (mathcal{O}(n^2)) 的

考虑两个点之间的顺序什么时候会发生变化，当平行线的斜率和两点间斜率的大小关系产生变化时，两个点之间的顺序才会发生变化。

因此把平行线按极角排序即可。

代码，因为不会写所以只能贺z宝

考虑 (S_A=S_B=S_C) 怎么做，也就是区间覆盖全局询问两个字符串是否相同，只能用一个数据结构去维护。

因此猜想，能杂交出的本质不同字符串的数量必然是有限的，而且是极少的，只要把这些杂交出的字符串一一用上述做法去做即可。

注意到本题杂交的运算方式，如果把 J 看成 0，把 O 看成 1，把 I 看成 2 的话，那么 (A oplus B = -(A+B) mod 3)

于是所有能求出的本质不同字符串都能用 (aS_A+bS_b+cS_c) 来表示，总共只有 27 种，打表发现字符串数量只有 9 种，直接暴力即可。具体看代码

如果 (D=n) 显然是求 LIS，如果 (D<n) 就是一个有 (l) 限制的 LIS，我们只需求出每个 (l_i) 即可。

这题的限制换种说法就是，一个点 (j) 可以往点 (i) 转移，当且仅当 ([j+1,i-1]) 中 (ge a_i) 的数组成的最长连续段长度 (<D)

我们维护的时候只需要搞出长为 (D) 的区间对后面点的 (l_i) 的贡献即可。只需一个线段树加单调队列。

求出 (l_i) 之后就可以直接一个树套树求 LIS ，时间复杂度 (mathcal{O}(n log^2 n))

代码，喜提内存最大解。

然后发现按 (a_i) 排序就可以直接线段树，树套树是来白给的。

「JOI Open 2016」摩天大楼