P8530 [Ynoi2003] 博丽灵梦

矩形颜色数，带权。 给定一个有 $n$ 个点的二维平面，每个点坐标为 $(i,p_i)$ ，其有权值 $a$。 给定一个长为 $n$ 的数组 $b$，其下标从 $1$ 到 $n$。 有 $m$ 次查询，每次查询给定一个矩形 $l_1,r_1,l_2,r_2$，定义集合 $S=\{a_i|l_1\le i\le r_1 \land l_2\le p_i\le r_2\}$，求对于集合 $S$ 中所有元素 $j$，$b_j$ 的和。

无

无

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078 ### 样例解释 对于答案为 $27$ 的询问，$S=\{1,4,5,9\}$，对应 $b_j=9,4,5,9$，和为 $27$。 对于答案为 $22$ 的询问，$S=\{1,4,9\}$，对应 $b_j=9,4,9$，和为 $22$。 对于答案为 $4$ 的询问， $S=\{4\}$，对应 $b_j=4$，和为 $4$。 对于答案为 $0$ 的询问， $S=\emptyset$，和为 $0$。 ### 数据范围 每个测试点的具体限制见下表： | 测试点编号 | $n\le $ | $m\le $ | 特殊限制 | | :---------: | :--------------: | :--------------: | :--------: | | $1$ | $10$ | $10$ | 无 | | $2$ | $5\times 10^3$ | $5\times 10^3$ | 无 | | $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$ | 无 | | $8$ | $3\times 10^4$ | $6\times 10^4$ | 无 | | $9$ | $4\times 10^4$ | $8\times 10^4$ | 无 | | $10$ | $5\times 10^4$ | $10^5$ | 无 | | $11$ | $6\times 10^4$ | $1.2\times 10^5$ | 无 | | $12$ | $7\times 10^4$ | $1.4\times 10^5$ | 无 | | $13\sim 15$ | $10^5$ | $2\times 10^5$ | $\text{C}$ | | $16\sim 18$ | $10^5$ | $2\times 10^5$ | 无 | | $19$ | $10^5$ | $3\times 10^5$ | 无 | | $20$ | $10^5$ | $4\times 10^5$ | 无 | | $21$ | $10^5$ | $5\times 10^5$ | 无 | | $22$ | $10^5$ | $6\times 10^5$ | 无 | | $23$ | $10^5$ | $8\times 10^5$ | 无 | | $24$ | $10^5$ | $10^6$ | 无 | | $25$ | $10^5$ | $10^6$ | 无 | 为了方便，下面记 $(a, b) \leq (c, d)$ 表示平面上两个点 $(a, b),(c, d)$ 满足 $a \leq c, b \leq d$。 特殊限制 A：对于所有询问有 $l_2 = 1, r_2 = n$。 特殊限制 B：这个特殊限制太容易造水了，不要了。 特殊限制 C：最多有 $50$ 对二元组 $(i, j)(1 \leq i < j \leq n)$ 不满足 $(i, p_i) \leq (j, p_j)$。 对于所有测试点：$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$，保证 $p_i$ 为一个排列，保证 $1\le p_i,a_i,b_i\le n$。