才学了FWT就看到这个题。。。
大概真的是一道FWT水题。。。

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

= =随机化太玄学了，60 -> 90 -> 100。莫名其妙rk1

回复 @AntiLeaf :
思路是这样的。设全集为U，我们把每个集合的子集都看作是一个可取的集合，这样可取集合的求法可以参照集合卷积的逆运算。之后我们进行一次集合卷积，求出子集于每个集合S的最大集合Max[S]（即化为二进制数最大），最后我们枚举可取的集合S，则如果取了S，则答案最大为S|Max[U^S]。

回复 @Mike is Fool :
然而没看懂标程......

大家都是随机化而没有利用那个ai<=2^20的条件吗？我的标程是O(n+20*2^20)的

随机化肛过去了= =
把区间随机打乱之后只统计每个位置和后面4582个位置的或值,
时间复杂度是$O(n*log^3n)$的
因为常数极小所以可以过去
(对Mike深表歉意,毕竟好好做了数据)

%拜神犇Mike