P16575 Ancient God Segment Tree · Modified

The Ancient God Segment Tree is too hard, and the problem setter could not solve it, so they modified it.

- A line is represented as $(sx, sy, tx, ty)$, and it is guaranteed that $sx \not= tx$. - When a line appears, it lights up all integer points $(x, y)$ that satisfy: $$ y \cdot (tx-sx) \cdot \big( (ty-sy)\cdot(x-sx) - (tx-sx)\cdot(y-sy) \big) \ge 0 $$ - A point that has already been lit will not be turned off, and will not be lit a second time. There are $n$ operations. An operation can be: 1. Add a line. 2. Query the number of lit points in a rectangular region. Each test point contains multiple groups of testdata.

The first line contains two positive integers $c, T$, representing the test point ID and the number of testdata groups. In the sample, $c$ is the smallest test point ID that satisfies the corresponding property. For each group of testdata: - The first line contains one positive integer $n$, representing the number of operations. - The next $n$ lines each contain $5$ integers, describing an operation as follows: - `1 sx sy tx ty`: add a line. - `2 lx ly rx ry`: query the number of lit points satisfying $lx{\le}x{\le}rx$ and $ly{\le}y{\le}ry$.

For each operation $2$, output one number per line as the answer.

The input size of this problem is large. A fast input template is provided in the downloadable files. For all data: - $1 \le n \le 1\times 10^6$. - $1 \le \sum n \le 2\times 10^6$. - $-10^9 \le sx, sy, tx, ty \le 10^9$, and $sx \not= tx$. - $-10^9 \le lx \le rx \le 10^9$, $-10^9 \le ly \le ry \le 10^9$. ::cute-table{tuack} | Test Point ID | $n \leq$ | $ \sum n \leq$ | Special Property | | :-----------: | :------------: | :------------: | :--------------: | | $1$ | $100$ | $500$ | A | | $2$ | $1\times 10^6$ | $2\times 10^6$ | B | | $3$ | ^ | ^ | C | | $4$ | ^ | ^ | D | | $5$ | $1\times 10^5$ | $3\times 10^5$ | None | | $6\sim 10$ | $1\times 10^6$ | $2\times 10^6$ | ^ | - **Special Property A**: It is guaranteed that $\lvert lx \rvert, \lvert rx \rvert, \lvert ly \rvert, \lvert ry \rvert \le 500$. - **Special Property B**: It is guaranteed that $lx = rx$. - **Special Property C**: It is guaranteed that $sx = 0, sy = 0$. - **Special Property D**: It is guaranteed that $ly = -1e9, ry = 1e9$. Translated by ChatGPT 5