[Spe]融入

[Spe]融入

【题目背景】
新环境。
【题目描述】
对于给定一个长度为 \(n\) 的无序序列 \(A\)(其中每个子集以二元组的形式存入 <\(a_i,b_i\)>)和一个同样长度的无序序列 \(A'\)(同样以二元组的形式存入),将 \(A\) 中所有元素按序存入序列 \(A'\),且在每次存入后进行一次询问。
对于每次询问,给定两个数 \(L_i,R_i\),求 \(sum_i=\sum b_i(a_i∈[L_i,R_i])\) 的值。
【输入格式】
第一行一个数 \(n\)。
接下来 \(n\) 行,每行两个数,为序列 \(A\) 的元素 \(a_i,b_i\)。
接下来 \(n\) 行,每行两个数,为序列 \(A'\) 的元素 \(a'_i,b'_i\)。
最后 \(n\) 行,每行两个数,为 \(L_i,R_i\)。
【输出格式】
共 \(n\) 行,每行一个数,为 \(sum_i\)。
【样例输入1】

1
1 1
2 2
1 2

【样例输出1】

3

【样例输入2】

2
2 1
3 1
1 1
4 1
3 4
1 3

【样例输出2】

1
3

【提示/说明】
时空限制:\(2s\),\(256MiB\)。

测试点序号 \(n\) \(L_i,R_i,a_i,a'_i,b_i,b'_i\) 特殊性质
\(1\sim 2\) \(\leq 5\) \(\leq 10\) \(N\)
\(3\sim 4\) \(\leq 10^3\) \(\leq 10^5\) \(N\)
\(5\sim 7\) \(\leq 10^5\) \(\leq 10^8\) \(Y\)
\(8\sim 10\) \(\leq 10^5\) \(\leq 10^8\) \(N\)

特殊性质:
\(N\):没有任何特殊性质。
\(Y\):\(0\leq a_i\leq 10^5\leq a'_i\leq 10^8\)。

对于 \(100\%\) 的数据,\(1\leq n\leq 10^5\),\(0\leq L_i,R_i,a_i,a'_i,b_i,b'_i\leq 10^8\)。

信息

ID
1002
难度
9
分类
(无)
标签
(无)
递交数
9
已通过
1
通过率
11%
上传者