#P19002. 均值统计

    ID: 18338 传统题 2000ms 1024MiB 尝试: 43 已通过: 5 难度: 7 上传者: 标签>难度分类提高+/省选-离线与分治分治算法动态规划记忆化搜索数据结构哈希表数值计算与优化有理数精确运算CF2300

均值统计

均值统计

时间限制:2 秒。内存限制:1024 MiB。标准输入、标准输出。

给定正整数 nn,有一个序列 ai=ia_i=i(1≤i≤n1\le i\le n)。

小猫想用线段树回答区间平均数查询。每个结点对应一个区间 [l,r][l,r],保存一个值 vl,rv_{l,r}。他认为,父结点的值可以直接取两个子结点所保存数值的平均数,不必考虑两个子区间的长度。

建树时调用 Build(1,n)。查询区间 [L,R][L,R] 时调用 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

这个算法并不总是正确,但对一些区间仍能得到真正的平均数。

请统计满足 1≤L≤R≤n1\le L\le R\le n 且

$$\operatorname{Query}(1,n,L,R)=\frac{\sum_{i=L}^{R}a_i}{R-L+1}$$

的区间 [L,R][L,R] 数量。

所有平均数均按精确的有理数计算,不进行四舍五入、舍去小数或整数截断。

输入格式

第一行一个整数 TT,表示测试数据组数。

接下来 TT 行,每行一个整数 nn。

输出格式

对每组数据输出一行一个整数,表示满足条件的区间数量。

样例

输入

3
1
5
14

输出

1
10
35

样例说明

当 n=5n=5 时,满足条件的区间为:

$$[1,1],[1,2],[2,2],[2,3],[2,5], [3,3],[3,4],[4,4],[4,5],[5,5].$$

例如,查询 [2,5][2,5] 得到 7/27/2,与这个区间真正的平均数相同;查询 [1,5][1,5] 得到 27/827/8,与真正的平均数 33 不同。

数据范围与计分

对于所有测试数据,1≤T≤1041\le T\le10^4,1≤n≤2×1061\le n\le2\times10^6,同一输入文件中所有 nn 的和不超过 5×1065\times10^6。

本次训练设置以下四个子任务,总分为 100 分。每个子任务内的测试点全部通过,才能获得该子任务的分数。

子任务 分值 每组数据的 nn 上限 同一输入文件的 ∑n\sum n 上限
1 15 30 100
2 20 2000
3 25 2×1052\times10^5 5×1055\times10^5
4 40 2×1062\times10^6 5×1065\times10^6

题目原作:电子科技大学命题组,2026 ICPC 成都区域赛。中文整理及本校评分分组已作调整;题面遵循 CC BY-SA 4.0。

下发文件

大样例输入与输出