問題解説
この問題では、以下の二つの点を工夫することで高速に処理することができます。
「45度回転」
マンハッタン距離での範囲検索を簡単にするため、次の座標変換を用います：
これにより、マンハッタン距離の範囲が矩形範囲（長方形）として表現可能になります。 したがって2次元平面上での矩形範囲クエリに帰着され、効率的な範囲集計が可能になります。
この変換は伝統的に「45度回転」と呼ばれます。理由は座標を45度回転して原点からのユークリッド距離を 倍する変換だからです。
矩形範囲内の点の数え上げ
残りは矩形領域内の点を数え上げるだけです。これは二次元累積和を用いて解くことができます。 変換後のx座標とy座標が 以上 以下なので、座標圧縮も不要でしょう。
このアプローチにより、クエリ数が多くても効率的に回答を得ることが可能です。