Point Add Rectangle Sum

AC一覧

Problem Statement
問題文

You are given $N$ weighted points on two-dimensional plane. $i$-th is at ($x_i$, $y_i$) and has a weight of $w_i$. Process $Q$ queries of the following types.

  • 0 $x$ $y$ $w$ : Add a new point with weight $w$ at $(x, y)$. If there is another point at the same coordinates, add as a distinct point.
  • 1 $l$ $d$ $r$ $u$ : Find the sum of weight of points such that $l \leq x < r$, $d \leq y < u$ is satisfied.

$2$ 次元平面上に重み付きの点が $N$ 個あります。 $i$ 個目の座標は$(x_i, y_i)$で重みは$w_i$です。 以下の $2$ 種類のクエリ $Q$ 個を処理してください

  • 0 $x$ $y$ $w$ : $(x, y)$に重み$w$の点を追加する。既に同じ位置に点があっても別の点として追加する
  • 1 $l$ $d$ $r$ $u$ : $l \leq x < r$, $d \leq y < u$ を満たす点について、重みの総和を求める

Constraints
制約

  • $1 \le N \le 100{,}000$
  • $1 \le Q \le 100{,}000$
  • $0 \le x_i, y_i \le 10^{9}$
  • $0 \le w_i \le 10^{9}$
  • For queries of type 0 $x$ $y$ $w$
    • $0 \le x, y \le 10^{9}$
    • $0 \le w \le 10^{9}$
  • For queries of type 1 $l$ $d$ $r$ $u$
    • $0 \le l \lt r \le 10^{9}$
    • $0 \le d \lt u \le 10^{9}$

  • $1 \le N \le 100{,}000$
  • $1 \le Q \le 100{,}000$
  • $0 \le x_i, y_i \le 10^{9}$
  • $0 \le w_i \le 10^{9}$
  • 0 $x$ $y$ $w$形式のクエリについて
    • $0 \le x, y \le 10^{9}$
    • $0 \le w \le 10^{9}$
  • 1 $l$ $d$ $r$ $u$形式のクエリについて
    • $0 \le l \lt r \le 10^{9}$
    • $0 \le d \lt u \le 10^{9}$

Input
入力

$N$ $Q$
$x_0$ $y_0$ $w_0$
$x_1$ $y_1$ $w_1$
$x_2$ $y_2$ $w_2$
$\hspace{17pt} \vdots$
$x_{N - 1}$ $y_{N - 1}$ $w_{N - 1}$
$\mathrm{Query}_0$
$\mathrm{Query}_1$
$\mathrm{Query}_2$
$\hspace{13pt} \vdots$
$\mathrm{Query}_{Q - 1}$

# 1

4 5
0 0 1
0 2 10
2 0 100
2 2 1000
1 0 0 2 3
1 0 0 3 3
0 2 2 10000
0 1 1 100000
1 1 1 3 3
11
1111
111000

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions