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]$ 的矩形并包含的所有关键点的权值和。

第一行一个数 $n$。 之后 $n$ 行每行两个元素 $p_i,a_i$，表示第 $i$ 个关键点 $(i,p_i)$，权值为 $a_i$，保证 $p$ 为一个 $1$ 到 $n$ 的排列。 之后一行一个数 $m$。 之后 $m$ 行每行四个元素 $x_i,x'_i,y_i,y'_i$，表示第 $i$ 个矩形左下角为 $(x_i,y_i)$，右上角为 $(x'_i,y'_i)$。 之后一行一个数 $q$。 之后 $q$ 行每行两个元素 $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$。