AGC013F「Two Faced Cards」別解(TLE)

Two Faced Cardsのコンテスト中に書いてた別解です。
O(N√N logN) なのでTLEして悲しいけど紹介しておきます。
(想定解も理解したけどadhocで面白かった)

下ごしらえ

とりあえずC(とA,B)を0~Nに変換しておきます。
Ai<Biのカードは裏で使うメリットがないのでBi=Aiとしておきます。
これでBi≦Aiが保証できます。
ここで、Bi>Nのカードがあるとimpossibleです。
Ai>Nのカードは後々面倒なので、Ai=Biとして後で答えから-1します。

f:id:snuke:20170417220211j:plain
入力例2の図示

クエリが1個

クエリが1個のときは以下のような貪欲法で解けます。

貪欲法

Ci=0のカードから順に相方を決めていきます。
相方は、以下のようなmultiset<int> Sを使って決めます。

  • Ci=xのカードを見ている時、Bi=xのカードがあればSにAiを追加する
  • Ci=xのカードを見ている時、Sに入っているxを全てINFに置き換える
  • Sに入ってる数のうちの最大値を、今見ているカードの相方として取り出す

表として取れるものがあればそれを取り、なければ表も取れるようになるのが最も遅いものを取るというイメージです。
途中でSが空なのに取り出そうとしたら失敗です。

クエリ複数

次に、クエリが複数ある場合に発展させます。

dp[k]=「Ci=kのカードには相方が要らないときの答え」というのをk=0~Nについて全て前計算しておけば、各クエリに高速に答えることができます。
dp[k]の値はどうなっているでしょうか。

まず、k=Nのときに上のような貪欲法を行うと、どこかの時点で(少なくともk=Nでは)失敗します。
失敗したiをtとすると、k>tは全て-1です。
k=tについてはCi=tのカードをスキップしてそのまま貪欲法を続けて答えdp[t]を求めます。

あとはk<tの場合です。
あるkについて、上の貪欲法でSから取り出した値がINFだった場合は、kをスキップしてもk+1をスキップしても答えは変わらないのでdp[k]=dp[k+1]です。(どっちにしろどうせINFを取るだけで、Sの他の部分は変わらないため)
Sから取り出した値がx(≠INF)だった場合はどうでしょうか?
xを取る代わりにスキップをして貪欲法を続けたときにxが取られるようなiをpとします。
pは必ずx以下になります。(i=xになるとxがINFに変化し、S内の最大値になるため)
このとき、kをスキップした時のSの状況はpをスキップした時とほぼ同じです。異なるのはxが取られるタイミングだけです。
したがって、p<xのときはdp[k]=dp[p]、s=xのときはdp[k]=dp[p]+1となります。

pを全てのkについて求めておけば後ろからdpテーブルを埋めていくことができます。

ーーここまでが本質ーー

データ構造パート

pはどうやって求めればいいでしょうか?
xが取られるよりも先に取られうるものというのは以下の2通りです。(kの時点ではINFはSに入っていない点に注意)

  • Sにまだ残っているもの(値をyとすると、k=yでINFに変わって取れるようになる。y<xが成り立つ点に注意)
  • aiがx以上のもの(bi以降なら取れる)

starry sky tree(区間加算と区間minができるsegtree)を用意します。このsegtreeでは「ある区間内で値がhoge以下のものが初めて現れる場所」をO(log N)で求めることもできます。
上記の2通りについて[取れるようになるi, N+1)に+1をしておきます。
さらに、i=0~Nについて[i,N+1)に-1をしておきます。
kの値をvとすると、[k,x)のうちv-1以下の値が初めて現れる場所がpです。(なければp=x)

上の2通りの+1を適切な順で追加したり消したりしながらpを全部求めていきたいのですが、残念ながらMoをするしかないです。
ただ、普通にMoをすると右端を1つずらしたときに増えるものが多かったり少なかったりして壊れるので、右端を「何番目に小さいbiであるか」を基準として√N個ずつのブロックに分けます。しかし、それだけだとbiが全くないゾーンが広過ぎになってしまうことがあるので、biの集合に0~N追加した集合での何番目かを基準にするなどしなければいけません。
左端については1つずらしたときには高々1つしか増減しないのでOKです。

まとめ

というわけで最後の方わりと雑でしたが、O(N√N logN)になりました。
こんな感じで6ケースだけTLEしましたΩ\ζ°)