P6760: 最大子段和
传统题
3.000s
时间限制
512MB
内存限制
4 提交
0 解决
【题目描述】
【题目描述】
鲍勃是一个顽强的少年，继排序研究和数学研究遭遇困难之后，他意识到算法的研究不能停留在理论层面，必须要
有扎实的编程技巧作为基础。于是他决定学习编程的知识。
鲍勃了解到，在编程中动态规划是非常重要的一个知识点。在他研究动态规划的时候遇到了这样一个问题：”
最大子段和问题”
，这个问题是：给你一个序列，你需要找出其中的一个子段 (
不一定非空)
使
这一段的和是序列的所有段中最大的。
鲍勃突发奇想：这个题能不能改成：多次询问每次给一个区间，找出来这个区间内的最大子段和?
可惜的是，这似乎不是一个容易的问题，鲍勃又来寻求你的帮助了。
【输入格式】
第一行一个 n(1 ≤ n ≤ 2 × 10
^6 )
，代表序列的长度
其后一行 n
个数字，代表原序列 A
，下标从 1 ∼ n
，|Ai | <= 10
^3
其后一行一个 q(1 ≤ q ≤ 10
^7 ),
代表询问的个数
其后输入一行两个整数 k1,k2(0 ≤ k1, k2 ≤ 2
^32 − 1)
，其作用下方会说明
由于本题的询问次数过多，为了避免 IO
时间影响算法效率，本题采用特殊的方法来读入询问。
将下方代码中的 k1,k2
设为输入的 k1,k2
unsigned k1,k2;
unsigned long long xorShift128Plus() {
unsigned long long k3 = k1, k4 = k2;
k1 = k4;
k3 ^= k3 << 23;
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
请你用下方的方式生成询问的区间
for(int i=1;i<=m;i++){
l[i]=xorShift128Plus()%n+1;
r[i]=xorShift128Plus()%n+1;
if(l[i]>r[i]) swap(l[i],r[i]);
}
【输出格式】
为了避免输出数据过多影响算法速度，你只需要输出一行一个整数代表每次询问的答案的异或和。
【样例】
subarray.in
|
subarray.out
|
5
1 -2 3 -1 5
2
998244353 1000000007
|
7
|
【提示】
样例中，998244353 1000000007
作为 k1,k2,
当 n
等于 5
时产生的前两个区间为 [2,2],[3,5]
。这两个区间的最大子段和分别为 0
和 7
，所以异或和是 7
【数据范围与约束】
测试点编号
|
n ≤
|
q ≤
|
1~3
|
1000
|
1000
|
4~7
|
2 × 10^5
|
2 × 10^5
|
8~10
|
2 × 10^5
|
10^7
|