P6783 [Ynoi2008] rrusq

Given a 2D plane, there are $n$ key points, $m$ rectangles, and $q$ queries. Each key point has a weight $a_i$. A rectangle with bottom-left corner $(x_i,y_i)$ and top-right corner $(x'_i,y'_i)$ contains a point $(a,b)$ if and only if $x_i\le a\le x'_i$ and $y_i\le b\le y'_i$. In each query, you are given $[l,r]$. For a key point $i$, if point $i$ lies in any rectangle whose index is within $[l,r]$, then we say that point $i$ is jointly contained by the rectangles in interval $[l,r]$. Output the sum of weights of all key points jointly contained by the rectangles in interval $[l,r]$.

The first line contains an integer $n$. Then follow $n$ lines, each containing two elements $p_i,a_i$, meaning the $i$-th key point is $(i,p_i)$ with weight $a_i$. It is guaranteed that $p$ is a permutation of $1$ to $n$. Then one line contains an integer $m$. Then follow $m$ lines, each containing four elements $x_i,x'_i,y_i,y'_i$, meaning the bottom-left corner of the $i$-th rectangle is $(x_i,y_i)$ and the top-right corner is $(x'_i,y'_i)$. Then one line contains an integer $q$. Then follow $q$ lines, each containing two elements $l,r$, meaning a query on interval $[l,r]$.

For each query, output one line with one integer representing the answer.

Idea: nzhtl1477&ccz181078, Solution: zx2003, Code: ccz181078, Data: nzhtl1477. Note: This problem uses **bundled testdata**. You can only get the score for a subtask after you pass all test points in that subtask. For $5\%$ of the testdata, it is Sample 1. For another $14\%$ of the testdata, $q=1$. For another $19\%$ of the testdata, $n,m,q\leq 500$. For another $19\%$ of the testdata, $n,m\leq 500$. For another $19\%$ of the testdata, $n,m,q\leq 2000$. For $100\%$ of the testdata, $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$。 Translated by ChatGPT 5