听说随机化可以搞过去。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}$。
当然我也只是就事论事，针对性地出一组数据，用其他乱搞的随机方法就不知道了。。但是理论上不加剪枝的随机在这题中是很劣的。

2^k分治树复杂度似乎和KD树在k较小的情况下是相同的，而且2^k分治树常数上比KD树要优秀
原来高一YY出来的这玩意儿真的是能用的！

回复 @洛缪 :

啦啦啦~朴素DP加个剪枝给撸过去了

回复 @hzoi__菜鸟 :
有问题呗

水水的DP

终于把主席树查询第k小的方法自己脑补出来了2333

查字典卡成
2333

忘了%mod

for（0~tim-1），不知道为什么不能从1~tim，无语，cogs不卡格式？？？？？

我是真的不适合DP= =
打个这个卡死我= =

回复 @洛缪 :
QAQ

[b]每个城市都有通讯交换机，直接或间接与其它城市连接。 。 。。。。。 那为什么还有不同的联通块？？？？？？？？

我通过COGS上，上着网啥嘞，有很多同学就，就不诚实，从网上粘个代码pa一交，交给我了，我今天四道题，我得两百多分儿。呀我一想两百多分可以呀，我这里边有好几个同学能得两百多分嘞，没问题。可其实呢？

这和血帆海盗一模一样啊……
http://cogs.pro/cogs/problem/problem.php?pid=426

本题本机1s就能过的，但这里死活2.5s~3.0s所以开了5s时限，希望写部分分的童鞋不要卡评测鸡。

在windows环境下写代码的童鞋们，vector的resize操作是不管清零的，所以可能需要我们手动pushback一大堆零……

竟然把字打错了。。提交了好几次。无颜面对江东父老。。

std

回复 @洛缪 :
哦