P9061 [Ynoi2002] Optimal Ordered Problem Solver

Given $n$ points $(x_i, y_i)_{i=1}^n$, you need to process $m$ operations in order. Each operation gives $o, x, y, X, Y$. - First, perform an update: - If $o = 1$, then for all points satisfying $x_i \le x,\; y_i \le y$, set their $y_i$ to $y$. - If $o = 2$, then for all points satisfying $x_i \le x,\; y_i \le y$, set their $x_i$ to $x$. - Then perform a query: ask for the number of points satisfying $x_i \le X,\; y_i \le Y$.

The first line contains two integers $n, m$. The next $n$ lines each contain two integers $x_i, y_i$. The next $m$ lines each contain five integers $o, x, y, X, Y$, representing one operation.

Output $m$ lines, each containing one integer. In order, output the answer to the query in each operation.

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078. Constraints: For all testdata, $1 \le n, m \le 10^6$, and $1 \le x_i, y_i, x, y, X, Y \le n$. Subtask 1 (20 points): $n, m \le 10^3$. Subtask 2 (20 points): $x_i, y_i, x, y, X, Y$ are independently chosen uniformly at random from $1$ to $n$. Subtask 3 (20 points): $o = 1$. Subtask 4 (20 points): $n, m \le 3 \times 10^5$, depends on Subtask 1. Subtask 5 (20 points): No special restrictions, depends on Subtasks 1, 2, 3, 4. Translated by ChatGPT 5