Codeforces Round #495 (Div. 2)

けんちょん @drken1215

@hamko_intel 一度タッチした人は半年もすれば復帰することが知られているのん！！！

有為 @uwitenpen

F, xが固定なので1でなければいけないパターンと0でなければいけないパターンがあって、1のほうはどれかの0のゾーンに含まれてたらだめかつ、0のほうですべての0のゾーンに入っていなくてはいけないを満たす領域の面積を求めれば良いとおもったんだけど、実装があまりにめんどくさかった

はむこ @hamko_intel

Cは見た瞬間Wavelet Matrixを持ってこようと思ったけどグッと思いとどまった（こういうの多い）

はむこ @hamko_intel

数列aの区間クエリがq個与えられて、それぞれの区間での種類を計算するのって殴れるんだっけ（Moより良く）

1 @komori3_

C こんな感じ pic.twitter.com/JALTTKZRCR

拡大

はむこ @hamko_intel

いやこのBは次出ても解けないよ…

1 @komori3_

システス速い？(A が通った)

1 @komori3_

速解きしたくても英語の壁がでかく厳しい

™ @tmaehara

wavelet tree じゃないですか？

はむこ @hamko_intel

@tmaehara 重複除外できましたっけ？

1 @komori3_

B みたいなパズルが解けたのかなり珍しい

けんちょん @drken1215

ぴーよたんかわいいのん(*´ｰ`*人*´ｰ`*)♪

はむこ @hamko_intel

なんか才能がなさすぎて悲しい

NATSUGIRRRRI @natsugir

CF#495Div2 C 列を前からuniqueな個数を数えて、後ろからも数える D t=h*wを全て試す。aの最大値が行列の角に来ることから0の座標の候補はmin(h, w)箇所。それぞれの値の出現回数はO(h+w)で数えてたぶん間に合う

™ @tmaehara

@hamko_intel できると思ってます（重複除去するやつには colored range counting / reporting という名前がついてます）

1 @komori3_

5 完した回の 5 億倍むずかったが

はむこ @hamko_intel

@tmaehara ありがとうございます！

™ @tmaehara

@hamko_intel 重複が想像と違っていたらア

hogeover30 @hogeover30

3完

NATSUGIRRRRI @natsugir

E 木の直径がボトルネックになるはずなので直径にパスを置いた F セグメントツリー。ノードの情報は、その区間の答え、左からORを取った時のランレングス、右からORを取った時のランレングス

1 @komori3_

B も通ってんな

kimiyuki@うさぎ🐇 @kimiyuki_u

寝れないまま4時になってしまった 睡眠調整がへたくそ

1 @komori3_

C 通って 3 完

™ @tmaehara

wavelet tree いまだに users.dcc.uchile.cl/~jperez/papers… も理解しきれてない．

はむこ @hamko_intel

@tmaehara [1, 2, 3, 10, 23, 5, 10, 23, 8]について、区間[3, 8)の重複除去した種類数は、対象となる数列は[10, 23, 5, 10, 23]で、重複を除外すると{5, 10, 23}なので答えは3、というイメージでした