[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%
- 上传者