← 返回题目列表

AtCoder · abc403_g

G. 奇数位置总和查询

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一个最初为空的序列 A.

你被给予 Q 查询按顺序处理。的 i第一个查询解释如下:

给你一个整数 y_i。如果 i=1,让 z be 0;否则,让 z 是以下问题的答案 (i-1)第一个查询。定义 x_i=((y_i+z)\bmod 10^9)+1。追加 x_i 到年底 A.
然后,让 B=(B_1,B_2,\ldots,B_i) 是序列 A 按升序排序,并找到奇数索引元素的总和 B。也就是说,找到 B_1 + B_3 + B_5 + \dots + B_m,其中 m 为不超过的最大奇数 i.

约束

  • 1 \le Q \le 3\times 10^5
  • 0 \le y_i < 10^9
  • 1 \le x_i \le 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

Q
y_1
y_2
\vdots
y_Q

输出

打印 Q 行。的 i- 第行应包含以下问题的答案 i- 第一个查询。


示例输入 1

5
1
3
1
999999994
999999993

示例输出 1

2
2
8
6
1000000006
  • 对于第一个查询, y_1=1, z=0,所以 x_1=((1+0)\bmod 10^9)+1=2。将此附加到末尾 A 给出 A=(2)。排序 A 按收益率升序排列 B=(2),求得的值为 B_1=2.
  • 对于第二个查询, y_2=3, z=2,所以 x_2=((3+2)\bmod 10^9)+1=6。追加给出 A=(2,6),所以 B=(2,6) 并且寻求的值为 B_1=2.
  • 对于第三个查询, y_3=1, z=2,所以 x_3=((1+2)\bmod 10^9)+1=4。追加给出 A=(2,6,4),所以 B=(2,4,6) 并且寻求的值为 B_1+B_3=8.
  • 对于第四个查询, y_4=999999994, z=8,所以 x_4=((999999994+8)\bmod 10^9)+1=3。追加给出 A=(2,6,4,3),所以 B=(2,3,4,6) 并且寻求的值为 B_1+B_3=6.
  • 对于第 5 个查询, y_5=999999993, z=6,所以 x_5=((999999993+6)\bmod 10^9)+1=1000000000。追加给出 A=(2,6,4,3,1000000000),所以 B=(2,3,4,6,1000000000) 并且寻求的值为 B_1+B_3+B_5=1000000006.

示例输入 2

8
105282053
695234822
468007124
120710491
568831200
700753895
765188109
262666319

示例输出 2

105282054
105282054
905798931
599798602
995656103
891549225
1652393438
1652393438

以下是以下值 x_1,x_2,\dots,x_8 按顺序:

105282054
800516877
573289179
26509423
168629803
696409999
656737335
915059758