1からkまでのiに対して、
・「i回目に働くのは一番早くて何日目？」
・「i回目に働くのは一番遅くて何日目？」
というのを格納した配列A,Bを考える。いずれも、oxの列を前から、後ろから見ていくことで可能。
結論から言うと、A,Bについて、A[i] == B[k-i-1]となる日付が「働くべき日」に該当する。
例えば、ooxoxoxoという配列で、「必ず1日以上開けて働かなくてはいけない」という制約をつけたらどうだろうか。
働く日数が二日であれば、上の配列はそれぞれ、
[0,3]
[5,7]
となることだろう。1回目に働くのは、遅くとも5日目に働けばいい。そう考えると、0,1,3日目に働く必要はない。同様に、0日目に働いてもいい。そうすれば、5日目を待たずとも二回仕事を終えることもできる。
以上より、「必ず働く日」というのは存在しない。
働く日数が三日であれば？ 配列はそれぞれ、
[0,3,5]
[7,5,3]
となる。この場合も、実は働くべき日は存在しない。2回目に働く日は3,5日目のいずれかから選ぶことができるし、選んだ日付によって、例えば2回目に働く日を3日目にすれば、1回目、3回目に働く日はそれぞれ0と(5,7)日目になるし、5日目を選べば、1回目、3回目に働く日はそれぞれ(0,1,3)と7日目になるからだ。
最後に、働く日が四日であれば、配列は
[0,3,5,7]
[7,5,3,1]
になる。この時、最初に働く日付のみが問題になり、後の3,5,7日目については必ず働かなくてはならない。（A[i] == B[k-i-1]なので）
ということで、この場合は3,5,7日目となる。
累積GCDまでは思いついたが......という感じ。前から累積GCD取って、各クエリごとに「初めてGCDが1になるところはどこか？」を二分探索すればO(QlogN)で求まる。GCDが1にならないなら配列の最後とのGCDを求めてあげればいい。
部分列の和を求めるのはわかる。bitがk個以上立っている桁を大きい方から取ればいいのもわかる。しかし大きなbitがk個以上立っているものをまたかき集めて、その中から次の桁のbitが立っているものを選んで......とやっていると日が暮れるので、視点を「n(n+1)/2個部分和」ではなく、「k個選んできた後の論理積の最大値」に移す。これをxとすれば、二進法で表した時にたかだか40通りなので、各bitについて立てるか立てないかを、bitの大きい方から検討していけば良い。
具体的に言えば、ans = 0として、
ans = 0 for i in range(40, -1, -1): temp = ans+2**i cur = 0 for j in range(len(list_sum)): if temp&list_sum[j] == temp: cur += 1 if cur >= k: ans += 2**i
（擬似的なコードなので粗はあるけどこんな感じ）
上のような実装をしてあげればいい。ansについては過去の結果を持ち越すことになるので、「上からbitがk個以上立っている集合を選んできて、その中でまたk個以上立っているような下のbitを選んでくる」のようなことができていることになる。
めっちゃ賢い......
「ペア」なので、必ず二つの要素の組で考える。
大きい方から貪欲に、「ペア」を作れる相手を取ることを考える。（降順で固定する）
大小関係をつけることでわかることがある。例えば、今見ている要素pに対して、相手となる要素q（p>qとする）を取ってきた時、p+q=2^kとなるような2^kは、確実に2^(k-1) <= p < 2^kを満たしている。
ペアの和が2^kよりも大きい2のべき乗になることはない。例えばp<2^kとして、q = 2^(k+1)-pとすれば、p>qよりp > 2^(k+1)-pとなるので2p > 2^(k+1)となり、p>2^kから矛盾が生じる。よって、p+qでできる二のべき乗は、pより大きくて、そのなかで最も小さいような2^kに限られる（ここに気付けるかが肝心）
ここまでくれば大体OKだが、相手となる要素の個数を管理するのにpythonではCounterという便利なデータ構造がある。
例えば
from collections import Counter L = [3, 11, 14, 5, 13, 3] C = Counter(L) #Counter({3: 2, 5: 1, 11: 1, 13: 1, 14: 1}) #C[3] = 2 #C[14] = 1
となる。これを使うことで、delete()などを使わなくても要素数を減らす操作が簡単にできる。
