题目描述
给出一个长度为 n 的序列 a,定义一个区间 [l,r] 的权值为 maxl≤L≤R≤r∣∑i=LRai∣。
对于 k=1,2,3,…,n,求所有长度为 k 的区间权值和。
输入格式
本题有多组测试数据,第一行输入一个正整数 T,代表数据组数。
对于每组数据,第一行输入一个正整数 n。
第二行输入 n 个整数,代表序列 a。
输出格式
为了避免输出量过大,设长度为 k 的区间权值和为 ansk,对于每组测试数据,你只需要输出:
i=1⨁nansimodi2
(其中 ⊕ 表示按位异或运算)
正解做法不依赖于该输出方式。
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
提示
【样例解释】
样例中五组数据的 ans 分别为:
- {4,3,2}
- {28,39,41,36,31,22,13}
- {28,39,41,36,31,22,13}
- {7,10,10,7}
- {18,23,19,14,7}
其中,对于第一组数据,各个区间的权值分别如下:
- [1,1]:1
- [2,2]:1
- [3,3]:2
- [1,2]:1
- [2,3]:2
- [1,3]:2
其中,长度为 1 的区间有 [1,1],[2,2],[3,3],权值和为 4;长度为 2 的区间有 [1,2],[2,3],权值和为 3;长度为 3 的区间有 [1,3],权值和为 2。
【数据范围】
对于所有数据,保证:
- 1≤T≤104
- 1≤n,∑n≤106
- −106≤ai≤106
本题采用打包测试,各测试包描述如下:
Subtask |
∑n≤ |
特殊性质 |
分值 |
1 |
500 |
无 |
5 |
2 |
5000 |
20 |
3 |
106 |
ai≥0 |
25 |
4 |
3×105 |
无 |
5 |
106 |