#P12498. Range | Sum | Maximum

Range | Sum | Maximum

题目描述

给出一个长度为 nn 的序列 aa,定义一个区间 [l,r][l,r] 的权值为 maxlLRri=LRai\max_{l\le L\le R\le r}|\sum_{i=L}^Ra_i|

对于 k=1,2,3,,nk=1,2,3,\dots,n,求所有长度为 kk 的区间权值和。

输入格式

本题有多组测试数据,第一行输入一个正整数 TT,代表数据组数。

对于每组数据,第一行输入一个正整数 nn

第二行输入 nn 个整数,代表序列 aa

输出格式

为了避免输出量过大,设长度为 kk 的区间权值和为 anskans_k,对于每组测试数据,你只需要输出:

i=1nansimodi2\bigoplus_{i=1}^nans_i\bmod i^2

(其中 \oplus 表示按位异或运算)

正解做法不依赖于该输出方式。

5
3
1 -1 2
7
1 -2 -3 4 5 -6 -7
7
-1 2 3 -4 -5 6 7
4
1 1 2 3
5
1 4 -5 -2 6
1
31
31
4
11

提示

【样例解释】

样例中五组数据的 ansans 分别为:

  • {4,3,2}\{4,3,2\}
  • {28,39,41,36,31,22,13}\{28,39,41,36,31,22,13\}
  • {28,39,41,36,31,22,13}\{28,39,41,36,31,22,13\}
  • {7,10,10,7}\{7,10,10,7\}
  • {18,23,19,14,7}\{18,23,19,14,7\}

其中,对于第一组数据,各个区间的权值分别如下:

  • [1,1]:1[1,1]:1
  • [2,2]:1[2,2]:1
  • [3,3]:2[3,3]:2
  • [1,2]:1[1,2]:1
  • [2,3]:2[2,3]:2
  • [1,3]:2[1,3]:2

其中,长度为 11 的区间有 [1,1],[2,2],[3,3][1,1],[2,2],[3,3],权值和为 44;长度为 22 的区间有 [1,2],[2,3][1,2],[2,3],权值和为 33;长度为 33 的区间有 [1,3][1,3],权值和为 22

【数据范围】

对于所有数据,保证:

  • 1T1041\le T\le10^4
  • 1n,n1061\le n,\sum n\le10^6
  • 106ai106-10^6\le a_i\le10^6

本题采用打包测试,各测试包描述如下:

Subtask n\sum n\le 特殊性质 分值
11 500500 55
22 50005000 2020
33 10610^6 ai0a_i\ge 0 2525
44 3×1053\times10^5
55 10610^6