整体二分大法好！各种打错变量名我也是醉了……

二分答案，网络流验证。话说样例都不合法，害得我以为就一组数据呢……

回复 @_Itachi :
每个班都必然有bug男和bug女的存在
这告诉我们第一问答案肯定是0啊……
手残Mike居然能把匈牙利打错了……

居然还有
0 0 0 0
这种数据！

是我写的姿势不对把。。。写的单调队列比线段树慢10倍
终于发现原因了，没有加读入优化

恩，单调队列单调队列

求证代码正确性……

先用zkw打一遍
MARK

exp和ln精度不错嘛

良心样例，真是业界良心！

呃呃呃

没事别乱改模板，真是作死……

我觉得我在把所有dp打成dfs
然而还是dfs好打
2333

mdzz
打dfs打了半天连样例都输出不出来

这一定是道数学题

小搜一下*-*

纯暴力也能过？
说好的trie树并没有出现。
纳尼考试时我连暴力都错了・゜・(PД`q｡)・゜・……

手贱1打成0 居然还能40分

O(nk)的四分树已被常数卡掉，坐等会正解神犇切题，一定要发题解啊！

听说随机化可以搞过去。shy写了下发现不随机都可以。比如暴力找每个数后面200（或4000）个or，暴力和最前面200个or之类的。
当然。。。这显然是错的。假设答案由唯一的关键对$(i,j)$贡献，那么这个算法和$|i-j|$的值有很大关系。
随便构一组数据：$1..n$全$0$，随机1个位置赋为$1$，再随机1个位置赋为$2$。答案显然是$1\ or\ 2=3$，当然榜上随机的代码（包括我自己的随机代码），这样的数据基本就会错。
理论算下的话，$ \frac{\sum_{i=1}^{n}\sum_{j=1}^{n}(|i-j|)}{n^{2}}=\frac{\sum_{i=1}^{n}(\frac{i(i-1)}{2}+\frac{(n-i)(n-i+1)}{2})}{n^{2}}=\frac{\frac{n^{3}+2n^{2}+2n+1}{3}}{n^{2}} $
代入n=200000的话，期望长度有66667左右，则这样随机化实际上正确率非常低，其实每个位置暴力找k个or的话，即使不算感觉下正确率大概应在$\frac{k}{n}$。
当然我也只是就事论事，针对性地出一组数据，用其他乱搞的随机方法就不知道了。。但是理论上不加剪枝的随机在这题中是很劣的。