search

yosupo06 / library-checker-problems

The problem data (Test case generator, judge's solution, task, ...) of Library Checker
https://judge.yosupo.jp/
Apache License 2.0
509 stars 117 forks source link

[問題案] Point Add Rectangle Sum #519

Closed windows-server-2003 closed 4 years ago

windows-server-2003 commented 4 years ago

問題ID: point_add_rectangle_sum 問題名: Point Add Rectangle Sum

想定アルゴリズム: (疎な)2次元セグ木

問題概要

Q個のクエリを処理

入力

Q
Query1
Query2
...
QueryQ

出力

...

制約

1 <= Q <= 200000 座標系は全部[0, 10^9]

点が重複しても普通に足すのが自然なんだけどそのまま問題文書いて通じるか

windows-server-2003 commented 4 years ago

まぁあと[l, r)のrが10^9以下なので点の方は[0, 10^9)にするのを検討しています(絶対にカウントされない点があるのも引っかかるところがあるので)

yosupo06 commented 4 years ago

https://judge.yosupo.jp/problem/rectangle_sum これで絶対にカウントされない点があることに今気づいたんですが、それはそうとしてもう作っちゃったんで合わせてくれると助かります(技術的負債…)

点は重複したら普通に足してください そのままでも大丈夫だと思うんですが、気になるなら問題文にその旨をちょっと書いておけば平気だと思います

初期値として点をN個与えると良さそうです(初期値をO(N)で構築するかO(N log N)で構築するかO(N logN)で構築するかO(N log^2 N)で構築するかのテストが出来るので)

windows-server-2003 commented 4 years ago

了解です～

windows-server-2003 commented 4 years ago

これ実行時間やばいのでN, Q <= 1e5にします