rickytheta's blog

競プロ

ARC068 E Snuke Line O((N+M)√M + NlogN)解

みんなFenwick Tree使ってて泣いたので。

問題概要

arc068.contest.atcoder.jp

N個の区間[l,r]でお土産が売っている。全ての1<=d<=Mに対して、dの倍数の地点を全て訪れることで入手できるお土産の種類を答えよ。

 1 \le N \le 3\times10^5, 1 \le M \le 10^5, 1 \le l_i \le r_i \le M

解法

dの値に関して平方分割をします。

 d \le \sqrt M の時、全ての区間に対してdの倍数が含まれているかをチェックします。具体的には  \lceil \frac{l_i} d \rceil\times d \le r ならば含まれています。よって計算量は O( N \sqrt M )です。

 d > \sqrt M の時、訪れる地点はたかだか  \sqrt M です。この訪れる地点を各dに対して更新するという方針を取ります。訪れる地点を指し示す構造体を便宜上ポインタと呼びます。

0番地側から1-basedでx番目のポインタは d \times xの地点を指していることになります。dを1増やすとポインタの位置はxだけ動きます。

ポインタが動くと区間に入ったり出たりするイベントが発生するので、ポインタには「区間左側ソート順でどこまでの区間に入ったか」「区間右側ソート順でどこまでの区間から出たか」という情報を持たせておきます。

区間の出入りで情報が更新される度に、区間を指すポインタの数を配列で管理し、インクリメント・デクリメントします。また、区間を指すポインタの数が0から1になったら答えを1増やし、1から0になったら答えを1減らします。

このようにポインタを動かすと、1つのポインタについては全体でたかだかMしか動かず、区間イベントもたかだかNで、そのポインタが \sqrt M個なので、合計して計算量は O( (N+M) \sqrt M )で、区間のソートがあるのでここに O( N \log N ) が加わります。

以上を合算して O( (N+M) \sqrt M + N \log N ) の計算量を達成します。

提出

arc068.contest.atcoder.jp

1276ms。TLEが2secなので厳しい。

感想

はてなmarkdown+TeXってありえんつらい