Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[問題案] Rectangle Sum(rectangle_sum) #118

Closed
yosupo06 opened this issue Oct 3, 2019 · 4 comments
Closed

[問題案] Rectangle Sum(rectangle_sum) #118

yosupo06 opened this issue Oct 3, 2019 · 4 comments
Assignees

Comments

@yosupo06
Copy link
Owner

@yosupo06 yosupo06 commented Oct 3, 2019

No description provided.

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Oct 3, 2019

問題概要

  • 問題ID: Rectangle Sum
  • 問題名: rectangle_sum

2次元平面上に重み付きの点がN個ある。クエリがQ個くる

  • l, r, d, u : l <= x < r, d <= y < uの点の重みの総和を求める

クエリ先読み / wavelet matrix

入力

N Q
x_0 y_0 w_0
x_1 y_1 w_1
:
x_{N-1} y_{N-1} w_{N-1}
l_0 r_0 d_0 u_0
l_1 r_1 d_1 u_1
:
l_{Q-1} r_{Q-1} d_{Q-1} u_{Q-1}

出力

z_0
z_1
z_{Q - 1}

制約

  • N <= 200,000
  • 0 <= 重み <= 1e9
  • 0 <= 座標 <= 1e9
@yosupo06 yosupo06 added this to 精査待ち in 問題リスト Oct 3, 2019
@yosupo06 yosupo06 changed the title [問題案] Weighted Sum of 2D points [問題案] Rectangle Sum(rectangle_sum) Oct 4, 2019
@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Oct 4, 2019

問題ID意見募集(point_add_range_sumに合わせた)

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Oct 15, 2019

rectangle_sumでええか

@yosupo06 yosupo06 moved this from 精査待ち to 作業待ち in 問題リスト Oct 15, 2019
@yosupo06 yosupo06 self-assigned this Oct 15, 2019
@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Oct 15, 2019

点列に合わせ、x0, y0, x1, y1の順に

yosupo06 added a commit that referenced this issue Oct 15, 2019
yosupo06 added a commit that referenced this issue Oct 16, 2019
add rectangle_sum #118
@yosupo06 yosupo06 closed this Oct 16, 2019
問題リスト automation moved this from 作業待ち to 作成済み Oct 16, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
問題リスト
  
作成済み
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
1 participant
You can’t perform that action at this time.