题目背景

你需要来研究一个城市的贫富差距问题

题目描述

分析方法如下：你需要把所有人分成穷人和富人两个部分，满足每个富人的收入不低于每个穷人的收入。目标是最小化富人总收入和穷人总收入的差的绝对值。

如果有多组最优解，我们最小化富人的人数。

由于人口是动态变化的，你需要在每一次变化后求出答案

30%的评测用例满足：$1 \le m \le 1000$。

100%的评测用例满足：$1 \le m \le 10^6,1 \le m\le 10^9$。

输入格式

第一行包含一个整数 $m$，表示接下来人口变化的次数

第二行包含 $m$ 个非 0 的整数 $w$。如果 $w$ 为正，表示增加一个收入为 $w$ 的市民，如果 $w$ 为负，表示减少一个收入为 $-w$ 的公民。

假设最开始没有公民。

输出格式

输出一行，包含 $m$ 个整数，对应着每个时刻的最优解中，有多少个富人，相邻的两个整数之间用一个空格分隔

样例 #1

样例输入 #1

8
3 4 5 3 3 -3 -3 4

样例输出 #1

0 1 1 2 2 2 1 2

想法是，用一颗平衡树维护，点上额外记录子树和。然后在这棵树上不断逼近答案。具体看代码。

现在的问题主要是，treap写炸了？？不知道为什么，如果不加37行的清零，size的维护就会炸。所以应该是某个地方修改了 t[0]，求解。

第二个更重要的问题是，加了这一句还是全WA（只能过样例）。请问是我结论炸了还是代码炸了？

代码楼下