JOI计划

大概是。。发现自己太颓了。。每天稳定$\ge 5h$~~遗迹暖暖~~dota2没啥救了。。所以给自己开个坑来让自己不那么自爆。。。

感觉JOI的题还不错，所以就切点JOI来压压惊。

发现没有地方评测。所以做一题之前就先上传到uoj上。

因为是在~~打dota2，看番，水知乎~~中抽出时间来做JOI。所以可能要慢慢做。。切得慢了请各位观众老爷轻喷。

我比较懒，所以val.cpp~~懒得写了~~暂时先坑着。等有空了或者有好心人再填上。

因为是我一个人在加题（而且只有我和fsf在翻译）所以可能题面数据啥的会出锅。大家发现问题可以和我直接联系。

首先易知和顺序无关，只要确定上下左右的天数就可以了。

先考虑下一维的情况。大概就是$\max(x[i]-x[i-1],x[1]+w-x[n])$之类的。

考虑如果把向左和向右的确定了，那么向上和向下的你一列一列去确定就算完了。

考虑一下这样一个事情，如果一个$l,r,u,d$是合法的，且$l$不等于某个$x_i-1$，那么$l-1,r+1,u,d$一定也是合法的，所以可能的$l$只有$O(n)$种。

考虑完$l$后，考虑一下$r$，可能的$r$显然也只有$O(n^2)$中，就是$x_i-x_j-l-1$之类的。然后从小到大枚举一下$r$维护一下每一段大概能做到$O(n^3logn)$

但是感觉不太能过。。然后又注意$u,d$本质不同的答案只有$O(n^2)$个，且随着$r$的增大$u,d$只会变小，所以大概把答案预处理下然后用数组来维护。应该能做到$O(n^3)$..(只是嘴巴bb没写过。。

有个更好些的写法是先枚举$r$，然后$l$可以用单调队列扫一遍。。这样也是$O(n^3)$的。。。

显然是把图建出来之后判断是否是二分图。如果是二分图答案就是$2^{联通块个数}$。

考虑一下先把三元环给判掉。判完之后考虑一下，令$fa_i$为最短的包含第$i$个的线段，并建树后发现那么连边就是一个点向树上的一条链连边。

然后就用并查集维护下把树上相同颜色的点缩一起然后BFS染色一下就可以了。。

Scape的博客