公式
Ex - Manhattan Christmas Tree 解説 by sugarrr
まず全体を \(45\) 度回転させます。
以後座標は全て回転後の座標とします。
並列二分探索で解くことを考えると、次の問題が解ければ良いです。
\((a_i,b_i)\) からチェビシェフ距離で \(K_i\) 番目に近いクリスマスツリーまでの距離 は \(\text{mid}_i\) 以下か? \(\cdots (*)\)
\((*)\) に答えるために、
\((a_i,b_i)\) からチェビシェフ距離で \(\text{mid}_i\) 以下の場所にあるクリスマスツリーの数
を求めます。
これは、\(x\) 座標の昇順に見ていきながら、各 \(y\) 座標のクリスマスツリーの数を BIT で管理すれば良いです。
(おおむね \(x=a_i - \text{mid}_i\) と \(x=a_i + \text{mid}_i\) のタイミングで区間和を求めることになります。)
座標の最大値を \(X\) として、以上で \((*)\) を \(O((N+Q)\log X)\) で解くことができます。
よって、元の問題は \(O((N+Q)(\log X)^2)\) で解くことができました。
投稿日時:
最終更新: