3803. [JZOI 2022 day2]最大子段和

【题目描述】

鲍勃是一个顽强的少年，继排序研究和数学研究遭遇困难之后，他意识到算法的研究不能停留在理论层面，必须也有扎实的编程技巧作为基础。于是他决定学习编程的知识。

鲍勃了解到，在编程中动态规划是非常重要的一个知识点。在他研究动态规划的时候遇到了这样一个问题：” 最大子段和问题”，这个问题是：给你一个序列，你需要找出其中的一个子段 (不一定非空) 使这一段的和是序列的所有段中最大的。

鲍勃突发奇想：这个题能不能改成：多次询问每次给一个区间，找出来这个区间内的最大子段和?

可惜的是，这似乎不是一个容易的问题，鲍勃又来寻求你的帮助了。

【输入格式】

第一行一个 $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]);
}

【输出格式】

为了避免输出数据过多影响算法速度，你只需要输出一行一个整数代表每次询问的答案的异或和。

【样例1输入】

5
1 -2 3 -1 5
2
998244353 1000000007

【样例1输出】

7

【样例2输入输出】

点击下载样例2

【提示】

样例中，$998244353$ $1000000007$ 作为 $k1,k2$, 当 $n$ 等于 $5$ 时产生的前两个区间为 $[2,2],[3,5]$。这两个区间的最大子段和分别为 $0$ 和 $7$，所以异或和是 $7$。

【数据规模与约定】

测试点 $1 ∼ 3$： $n \leq 1000，q \leq 1000$;

测试点 $4 ∼ 7$： $n \leq 2 × 10^5，q \leq 2 × 10^5$;

测试点 $8 ∼ 10$： $n \leq 2 × 10^6，q \leq 10^7$;

【来源】

焦作一中 NOIP 2022 模拟赛2022.11.23 pro3