https://aajisaka.hatenablog.com/entry/2019/05/01/223749

各 $A_i$ から右側に区間を伸ばしていくと、ビットを新たに立て続けたものが黒板に書かれていくことになる。ここで、新たに立ったビットが0に戻ることはないため、 $A_i$ の立っているビット数を $B_i$ とすると、黒板に書かれる整数の候補は高々 $\sum (61-B_{i})$ しかない。そのため、黒板に書かれる整数を全てmapに入れても計算量は $O(N \log N)$ となる。
区間の左から順番に見て、現在見ている値 $A_i$ を含む全区間 $A_j | A_{j+1} | \ldots | A_i \ (1 \le j \le i)$ をmapに入れながら処理し続けていくことを考える。ここで、mapに入る整数の種類も上記と同様に考えると高々61種類しかないことがわかる。このことから、途中経過をmapに突っ込みながら探索しても間に合う。

map<ll, ll, greater<ll>> mp1;
unordered_map<ll, ll> mp2, mp3;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n, k; cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  rep(i, n) {
    mp2[0]++;
    for(auto& e: mp2) {
      ll p = e.first|a[i];
      mp3[p] += e.second;
      mp1[p] += e.second;
    }
    swap(mp2, mp3);
    mp3.clear();
  }

  for(auto& e: mp1) {
    k -= e.second;
    if (k <= 0) {
      cout << e.first << endl;
      return 0;
    }
  }
}

提出コード (715ms)

Submission #5220782 - いろはちゃんコンテスト Day1
他の $O(N \log N)$ 解法に比べると定数倍が重く、 $N \le 10^{5}$ 程度だと $O(N \log ^2 N)$ 解法と同じくらい時間がかかる。
swap(mp2, mp3) を mp2 = mp3 にすると毎回mapをコピーするので200msほど遅くなる

効率のよい全探索を書くと自然とこんなコードになる気がするが、計算量が $O(N \log N)$ になっていることは非自明ではないだろうか。この記事でも最初は $O(N^{2})$ と書いていた。