#P18757. [2027年国家集训队互测] Half

[2027年国家集训队互测] Half

Half

题目描述

给定一个长度为 nn 的整数二元组序列 $A=[(a_{1,0},a_{1,1}),(a_{2,0},a_{2,1}),\dots,(a_{n,0},a_{n,1})]$。

定义 w(l,r)w(l,r) 为区间 A[l,r]A[l,r] 中 2(r−l+1)2(r-l+1) 个数前一半小的数之和。

换句话说,w(l,r)w(l,r) 等于 $a_{l,0},a_{l,1},a_{l+1,0},a_{l+1,1},\dots,a_{r,0},a_{r,1}$ 中前 r−l+1r-l+1 小的数之和。

对于每个 ll,求 min⁡r=lnw(l,r)\min\limits_{r=l}^n w(l,r)。

输入格式

第一行一个正整数 nn。

接下来 nn 行,每行两个整数 ai,0,ai,1a_{i,0},a_{i,1},表示序列中第 ii 个二元组包含的两个元素。

输出格式

nn 行每行一个整数,第 ll 行的数表示 min⁡r=lnw(l,r)\min\limits_{r=l}^n w(l,r)。

样例 1

样例输入

6
5 6
3 4
-2 0
4 4
2 2
7 7

样例输出

1
-2
-2
4
2
7

解释

以 l=1l=1 为例,从 r=1r=1 开始逐位向右扩展:

rr 第 rr 个二元组 前 rr 个二元组中前 rr 小的数 w(1,r)w(1,r)
11 5,65, 6 {5}\{5\} 55
22 3,43, 4 {3,4}\{3, 4\} 77
33 −2,0-2, 0 {−2,0,3}\{-2, 0, 3\} 11
44 4,44, 4 {−2,0,3,4}\{-2, 0, 3, 4\} 55
55 2,22, 2 {−2,0,2,2,3}\{-2, 0, 2, 2, 3\}
66 7,77, 7 {−2,0,2,2,3,4}\{-2, 0, 2, 2, 3, 4\} 99

所以 l=1l=1 的答案为 min⁡(5,7,1,5,5,9)=1\min(5,7,1,5,5,9)=1,在 r=3r=3 处取得。

数据范围

  • 子任务 11(33 分):n≤300n\le 300;

  • 子任务 22(55 分):n≤3000n\le 3000;

  • 子任务 33(1010 分):保证所有的 ai,ja_{i,j} 均在 (−230,230)(-2^{30},2^{30}) 内等概率均匀随机生成;

  • 子任务 44(1616 分):1≤ai,j≤10001\le a_{i,j}\le 1000。

  • 子任务 55(3232 分):n≤105n\le 10^5。

  • 子任务 66(3434 分):无特殊限制。

对于 100%100\% 的数据,1≤n≤5×1051\le n\le 5\times 10^5,∣ai,j∣<230|a_{i,j}|<2^{30}。

样例附件