P8530 [Ynoi2003] Reimu Hakurei

Counting colors in rectangles, with weights. You are given a 2D plane with $n$ points. The $i$-th point has coordinates $(i, p_i)$ and a weight $a_i$. You are given an array $b$ of length $n$, indexed from $1$ to $n$. There are $m$ queries. Each query gives a rectangle $l_1, r_1, l_2, r_2$. Define the set $S = \{ a_i \mid l_1 \le i \le r_1 \land l_2 \le p_i \le r_2 \}$. For all elements $j$ in the set $S$, compute the sum of $b_j$.

The first line contains an integer $n$. The next line contains $n$ numbers, where the $i$-th number denotes $p_i$. The next line contains $n$ numbers, where the $i$-th number denotes $a_i$. The next line contains $n$ numbers, where the $i$-th number denotes $b_i$. The next line contains an integer $m$. The next $m$ lines each contain $4$ numbers $l_1, r_1, l_2, r_2$, describing one query.

For each query, output one line containing an integer, which is the answer. Output the answer modulo $2^{32}$.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078. ### Sample Explanation For the query whose answer is $27$, $S = \{1,4,5,9\}$, the corresponding $b_j = 9,4,5,9$, and the sum is $27$. For the query whose answer is $22$, $S = \{1,4,9\}$, the corresponding $b_j = 9,4,9$, and the sum is $22$. For the query whose answer is $4$, $S = \{4\}$, the corresponding $b_j = 4$, and the sum is $4$. For the query whose answer is $0$, $S = \emptyset$, and the sum is $0$. ### Constraints The specific limits for each test point are shown in the table below: | Test Point ID | $n \le$ | $m \le$ | Special Constraint | | :-----------: | :--------------: | :--------------: | :----------------: | | $1$ | $10$ | $10$ | None | | $2$ | $5\times 10^3$ | $5\times 10^3$ | None | | $3$ | $2.5\times 10^4$ | $5\times 10^4$ | $\text{A}$ | | $4$ | $5\times 10^4$ | $10^5$ | $\text{A}$ | | $5$ | $7.5\times 10^4$ | $1.5\times 10^5$ | $\text{A}$ | | $6$ | $10^5$ | $2\times 10^5$ | $\text{A}$ | | $7$ | $2\times 10^4$ | $2\times 10^4$ | None | | $8$ | $3\times 10^4$ | $6\times 10^4$ | None | | $9$ | $4\times 10^4$ | $8\times 10^4$ | None | | $10$ | $5\times 10^4$ | $10^5$ | None | | $11$ | $6\times 10^4$ | $1.2\times 10^5$ | None | | $12$ | $7\times 10^4$ | $1.4\times 10^5$ | None | | $13\sim 15$ | $10^5$ | $2\times 10^5$ | $\text{C}$ | | $16\sim 18$ | $10^5$ | $2\times 10^5$ | None | | $19$ | $10^5$ | $3\times 10^5$ | None | | $20$ | $10^5$ | $4\times 10^5$ | None | | $21$ | $10^5$ | $5\times 10^5$ | None | | $22$ | $10^5$ | $6\times 10^5$ | None | | $23$ | $10^5$ | $8\times 10^5$ | None | | $24$ | $10^5$ | $10^6$ | None | | $25$ | $10^5$ | $10^6$ | None | For convenience, we write $(a, b) \leq (c, d)$ to mean that two points $(a, b)$ and $(c, d)$ on the plane satisfy $a \leq c$ and $b \leq d$. Special constraint A: For all queries, $l_2 = 1$ and $r_2 = n$. Special constraint B: This special constraint is too easy to exploit for weak testdata, so it is removed. Special constraint C: At most $50$ pairs $(i, j)$ $(1 \leq i < j \leq n)$ do not satisfy $(i, p_i) \leq (j, p_j)$. For all test points: $2 \leq n \leq 10^5$, $1 \leq m \leq 10^6$, $1 \leq l_1 \le r_1 \leq n$, $1 \leq l_2 \le r_2 \leq n$. It is guaranteed that $p_i$ is a permutation, and $1 \le p_i, a_i, b_i \le n$. Translated by ChatGPT 5