#1992. Half
Half
Half
题目描述
标题: Half - Problem - QOJ.ac
#21431. Half
The problem was used in the following contests:
题目描述
给定一个长度为 n 的整数二元组序列 A=[(a1,0,a1,1),(a2,0,a2,1),…,(an,0,an,1)]。
定义 w(l,r) 为区间 A[l,r] 中 2(r−l+1) 个数前一半小的数之和。
换句话说,w(l,r) 等于 al,0,al,1,al+1,0,al+1,1,…,ar,0,ar,1 中前 r−l+1 小的数之和。
对于每个 l,求 minr=lnw(l,r)。
输入格式
第一行一个正整数 n。
接下来 n 行,每行两个整数 ai,0,ai,1,表示序列中第 i 个二元组包含的两个元素。
输出格式
n 行每行一个整数,第 l 行的数表示 minr=lnw(l,r)。
样例 1
输入
6
5 6
3 4
-2 0
4 4
2 2
7 7
输出
1
-2
-2
4
2
7
解释
以 l=1 为例,从 r=1 开始逐位向右扩展:
r 第 r 个二元组 前 r 个二元组中前 r 小的数 w(1,r) 1 5,6 {5} 5 2 3,4 {3,4} 7 3 −2,0 {−2,0,3} 1 4 4,4 {−2,0,3,4} 5 5 2,2 {−2,0,2,2,3} 5 6 7,7 {−2,0,2,2,3,4} 9
所以 l=1 的答案为 min(5,7,1,5,5,9)=1,在 r=3 处取得。
数据范围
- 子任务 1(3 分):n≤300;
- 子任务 2(5 分):n≤3000;
- 子任务 3(10 分):保证所有的 ai,j 均在 (−230,230) 内等概率均匀随机生成;
- 子任务 4(16 分):1≤ai,j≤1000。
- 子任务 5(32 分):n≤105。
- 子任务 6(34 分):无特殊限制。
对于 100% 的数据,1≤n≤5×105,|ai,j|<230。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6
5 6
3 4
-2 0
4 4
2 2
7 7
1
-2
-2
4
2
7