[Problem proposal] Point add Point set Rectangle Affine (to points) Rectangle Sum (of points)

[robinyqc]

Problem Name Proposal: The current problem name is too lengthy and lacks precision. :( We need a more concise and descriptive name that captures the essence of the problem.

---

Problem Description

You are given an initial set of $N$ weighted points, $P = (P_0, P1, \dots, P{N - 1})$, on a two-dimensional plane. Each point $P_i$ ($0 \leq i < N$) is located at $(x_i, y_i)$ and has an associated weight $w_i$. Process $Q$ queries of the following types. For the $i$-th query:

• 0 $x$ $y$ $w$: Append a new point $P_{i + |P|}$ with weight $w$ at coordinates $(x, y)$. If a point already exists at these coordinates, add the new point as a separate instance.

• 1 $x$ $w$: Update the weight of point $P_x$ to $w$. (i.e., $w_x \gets w$)

• 2 $l$ $d$ $r$ $u$: Calculate the sum of weights modulo $998244353$ for all points where $l \leq x_i < r$ and $d \leq y_i < u$.

• 3 $l$ $d$ $r$ $u$ $a$ $b$: For each $i$ such that $l \leq x_i < r$ and $d \leq y_i < u$, apply the transformation $w_i \gets a \cdot w_i + b$.

---

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq x_i, y_i \leq 10^9$
• $0 \leq w_i < 998244353$

For each query type:

• Type 0 (Add a Point): $0 \leq x, y \leq 10^9$, $0 \leq w < 998244353$
• Type 1 (Update Weight): $0\leq x < (\text{Number of existing points})$
• Type 2 (Sum of Weights): $0 \leq l < r \leq 10^9$, $0 \leq d < u \leq 10^9$
• Type 3 (Weighted Transformation): $0 \leq l < r \leq 10^9$, $0 \leq d < u \leq 10^9$, $0 \leq a, b < 998244353$

---

Solution

Use K-D Tree to solve the problem in the complexity of $O(N^{1.5})$.

The solution involves maintaining a dynamic forest of 2-D Trees, where each tree handles a specific subset of points. Specifically:

• Each tree in the forest manages $2^k$ points. If the total number of points $n$ satisfies $\left\lfloor\dfrac n {2^i}\right\rfloor \equiv 1 \pmod 2$, then the $i$-th tree maintains $2^i$ points; otherwise, it remains empty.
• When a new point is added, it initializes a new tree in the forest. If two trees each contain $m$ points, they are merged via a brute-force approach in $O(m\log m)$ time, resulting in an overall complexity of $O(N \log^2 N)$.
• For query of rectangles processing, the solution applies the query across each tree, achieving a time complexity of $O\left(\sum_i\sqrt{\dfrac n{2^i}}\right) = O(\sqrt n)$.

---

Notes and Discussion Points

• Problem Name: A concise, relevant name is needed.
• Additional Operation: Would it be useful to add an operation to remove points?
• Performance Considerations: Given the high computational complexity, a time limit of 10 seconds is recommended.

Many thanks to ChatGPT for the assistance with this issue.

[maspypy]

In my experience, rectangle query processing using a KD Tree can result in substantial execution time, even with static point sets. I can’t imagine how long it would take if we were to target dynamic point sets.

First, considering the high demand, I propose creating the next version as follows. This generalizes the problem at https://judge.yosupo.jp/problem/range_affine_range_sum directly to a 2D point set.

Given $N$ weighted points $(x_i, y_i, a_i)$, process $Q$ queries of the following two types:

- 0 l r d u b c : Set $a_i := b \times a_i + c$ for each $i$ such that $l \leq x_i < r$ and $d \leq y_i < u$
- 1 l r d u : Find the sum of $w_i$ for each $i$ such that $l \leq x_i < r$ and $d \leq y_i < u$

[robinyqc]

As you mentioned, K-D trees indeed come with substantial constants when performing rectangle queries, and I can relate to that. However, making the point set dynamic doesn’t necessarily lead to an exponential increase in the constant factor. Theoretically, the constant approximately doubles, and in practice, it’s roughly the same, as shown by the tests on yosupo:

https://judge.yosupo.jp/submission/248590 https://judge.yosupo.jp/submission/248584

So, I believe setting the time limit to 10 seconds is reasonable. That said, reducing $Q$ to $10^5$ might be a good idea, as $Q \leq 2 \times 10^5$ could be challenging.

On a personal note, optimizing the point set to be dynamic was a memorable experience, and I agree it would be valuable to include this operation in the library checker. I’ve encountered problems requiring dynamic insertion (even though they enforced an online requirement).

Aside from the rectangle operations and adding new points, the operation that updates the weight of a specific point is perhaps not essential. I only mentioned it because it could be achieved in $O(\log n)$, which may be worth noting for those writing templates.

P.s. My practical experience with the constants involved in K-D trees is limited; I have only tested it on a few problems, such as the library checker templates.

[robinyqc]

I’ve run some preliminary performance tests on the K-D Tree implementation, with results available in max_queries_result.txt in the repository robinyqc/rectangle_add_rectangle_sum_of_points.

The tests compare the online and offline versions across different hardware setups (Intel i3, M2, and AMD EPYC processors). The results show that the offline version provides only a modest improvement over the online version, with no substantial performance gains observed.

I recommend using the contents of this repository as a basis for creating the problem. It contains almost all the work that needs to be done.

[maspypy]

Thank you very much. I would like to add both versions of the problem.

[robinyqc]

In fact, this dynamic point set version could also be solved in an offline manner, which (perhaps) could include the static point set version proposed by @maspypy . Anyway, I will proceed with generating the test data for the dynamic version.

I'm going to call it "Dynamic Point Rectangle Affine Rectangle Sum", with problem id dynamic_point_rectangle_affine_rectangle_sum.