#P19002. 均值统计
均值统计
均值统计
时间限制:2 秒。内存限制:1024 MiB。标准输入、标准输出。
给定正整数 ,有一个序列 ()。
小猫想用线段树回答区间平均数查询。每个结点对应一个区间 ,保存一个值 。他认为,父结点的值可以直接取两个子结点所保存数值的平均数,不必考虑两个子区间的长度。
建树时调用 Build(1,n)。查询区间 时调用 Query(1,n,L,R)。两个过程完整定义如下,其中 / 2 表示精确的有理数除法,floor 表示向下取整。
过程 Build(l, r):
如果 l = r:
v[l,r] = a[l]
返回
m = floor((l + r) / 2)
Build(l, m)
Build(m + 1, r)
v[l,r] = (v[l,m] + v[m+1,r]) / 2
函数 Query(l, r, L, R):
如果 L <= l 且 r <= R:
返回 v[l,r]
m = floor((l + r) / 2)
如果 R <= m:
返回 Query(l, m, L, R)
否则如果 L > m:
返回 Query(m + 1, r, L, R)
x = Query(l, m, L, R)
y = Query(m + 1, r, L, R)
返回 (x + y) / 2
这个算法并不总是正确,但对一些区间仍能得到真正的平均数。
请统计满足 且
$$\operatorname{Query}(1,n,L,R)=\frac{\sum_{i=L}^{R}a_i}{R-L+1}$$的区间 数量。
所有平均数均按精确的有理数计算,不进行四舍五入、舍去小数或整数截断。
输入格式
第一行一个整数 ,表示测试数据组数。
接下来 行,每行一个整数 。
输出格式
对每组数据输出一行一个整数,表示满足条件的区间数量。
样例
输入
3
1
5
14
输出
1
10
35
样例说明
当 时,满足条件的区间为:
$$[1,1],[1,2],[2,2],[2,3],[2,5], [3,3],[3,4],[4,4],[4,5],[5,5].$$例如,查询 得到 ,与这个区间真正的平均数相同;查询 得到 ,与真正的平均数 不同。
数据范围与计分
对于所有测试数据,,,同一输入文件中所有 的和不超过 。
本次训练设置以下四个子任务,总分为 100 分。每个子任务内的测试点全部通过,才能获得该子任务的分数。
| 子任务 | 分值 | 每组数据的 上限 | 同一输入文件的 上限 |
|---|---|---|---|
| 1 | 15 | 30 | 100 |
| 2 | 20 | 2000 | |
| 3 | 25 | ||
| 4 | 40 | ||
题目原作:电子科技大学命题组,2026 ICPC 成都区域赛。中文整理及本校评分分组已作调整;题面遵循 CC BY-SA 4.0。
下发文件
相关
在下列比赛中: