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

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

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

回复 @洛缪 :

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

回复 @hzoi__菜鸟 :
有问题呗

水水的DP

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

查字典卡成
2333

忘了%mod

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

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

回复 @洛缪 :
QAQ