P6783 [Ynoi2008] rrusq

给定一个二维平面，有 $n$ 个关键点，$m$ 个矩形，以及 $q$ 个询问，每个关键点有一个权值 $a_i$。 定义一个左下角为 $(x_i,y_i)$，右上角为 $(x'_i,y'_i)$ 的矩形包含一个点 $a,b$，当且仅当 $x_i\le a\le x'_i$ 且 $y_i\le b\le y'_i$。 每次询问给定 $[l,r]$，对于一个关键点 $i$ ，如果点 $i$ 在编号在 $[l,r]$ 内的任意一个矩形中，则认为 $i$ 被区间 $[l,r]$ 的矩形并包含，输出区间 $[l,r]$ 的矩形并包含的所有关键点的权值和。

无

无

Idea：nzhtl1477&ccz181078，Solution：zx2003，Code：ccz181078，Data：nzhtl1477 注意：本题采用**捆绑测试**，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。 对于其中 $5\%$ 的数据，为样例 1。 对于另外 $14\%$ 的数据，$q=1$。 对于另外 $19\%$ 的数据，$n,m,q\leq 500$。 对于另外 $19\%$ 的数据，$n,m\leq 500$。 对于另外 $19\%$ 的数据，$n,m,q\leq 2000$。 对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$1\leq q \leq 10^6$。 $1\leq a_i \leq 10000$，$1\leq x_i\leq x_i'\leq n$，$1\leq y_i\leq y_i'\leq n$，$1\leq l\leq r\leq m$。