注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "maxsum.h"。

题目描述

题目译自 2025년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2 「멋진 구간」

志虎手中有两个长度为 $N$ 的整数数组 $A$ 和 $B$，且对于任意 $0 \leq i \leq N-1$，总有 $A[i] \leq B[i]$。

我们把满足以下条件的区间 $[l, r]$ 定义为精彩区间：

• $l$ 和 $r$ 是整数。
• $0 \leq l \leq r \leq N-1$。
• 存在一个长度为 $N$ 的整数数组 $C$，满足：
  • 对于所有 $0 \leq i \leq N-1$，$A[i] \leq C[i] \leq B[i]$。
  • 对于所有 $0 \leq s \leq e \leq N-1$，$\sum_{i=l}^{r} C[i] \geq \sum_{i=s}^{e} C[i]$。也就是说，$C[l \ldots r]$ 是 $C$ 的最大和子数组（即所有子数组中元素和最大的子数组）。

志虎很好奇，这样的精彩区间到底有多少个。具体来说，他的问题由 $Q$ 个编号从 $0$ 到 $Q-1$ 的提问组成，用长度为 $Q$ 的数组 $L1, R1, L2, R2$ 表示。第 $j$ $(0 \leq j \leq Q-1)$ 个问题是：满足 $L1[j] \leq l \leq R1[j]$ 且 $L2[j] \leq r \leq R2[j]$ 的精彩区间 $[l, r]$ 有多少个？

你的任务是编写程序回答志虎的这些问题。

实现细节

你需要实现以下函数：

std::vector<long long> maxsum(std::vector<int> A, std::vector<int> B,
std::vector<int> L1, std::vector<int> R1, std::vector<int> L2, std::vector<int> R2)

• A, B：长度为 $N$ 的整数数组。
• L1, R1, L2, R2：长度为 $Q$ 的整数数组。
• 函数需返回一个长度为 $Q$ 的整数数组 $S$，其中对于所有 $0 \leq j \leq Q-1$，$S[j]$ 是第 $j$ 个问题的答案。
• 该函数只会被调用一次。

样例

假设 $N=3$，$Q=3$，$A=[-1,-1,-1]$，$B=[2,-1,2]$，$L1=[0,0,1]$，$R1=[2,0,2]$，$L2=[0,0,0]$，$R2=[2,2,1]$。

评测程序调用：

maxsum([-1,-1,-1], [2,-1,2], [0,0,1], [2,0,2], [0,0,0], [2,2,1])

• $[0,0]$ 是精彩区间。例如，取 $C=[1,-1,0]$，$C[0 \ldots 0] = 1$ 是最大和子数组。
• $[0,1]$ 不是精彩区间。因为 $C[1] = -1$，无论 $C[0]$ 如何取，$C[0] > C[0] + C[1]$，$[0,1]$ 无法成为最大和子数组。
• 通过类似分析，可证明精彩区间只有 $[0,0], [0,2], [1,1], [2,2]$。
• 回答问题：
  • $j=0$：$0 \leq l \leq 2, 0 \leq r \leq 2$，有 $[0,0], [0,2], [1,1], [2,2]$，共 $4$ 个。
  • $j=1$：$0 \leq l \leq 0, 0 \leq r \leq 2$，有 $[0,0], [0,2]$，共 $2$ 个。
  • $j=2$：$1 \leq l \leq 2, 0 \leq r \leq 1$，有 $[1,1]$，共 $1$ 个。

函数应返回 $[4,2,1]$。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N, Q \leq 250000$
• 对于所有 $0 \leq i \leq N-1$，$-10^{9} \leq A[i] \leq B[i] \leq 10^{9}$。
• 对于所有 $0 \leq j \leq Q-1$，$0 \leq L1[j] \leq R1[j] \leq N-1$。
• 对于所有 $0 \leq j \leq Q-1$，$0 \leq L2[j] \leq R2[j] \leq N-1$。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$5$	$1 \leq N \leq 500$
$2$	$11$	$1 \leq N \leq 5000$
$3$	$45$	$Q = 1$；$L1[0] = L2[0] = 0$；$R1[0] = R2[0] = N-1$
$4$	$12$	对于所有 $0 \leq j \leq Q-1$，$L1[j] = R1[j], L2[j] = R2[j]$
$5$	$27$	无附加限制

示例评测程序

示例评测程序接收以下格式的输入：

• 第 $1$ 行：$N\ Q$
• 第 $2+i$ $(0 \leq i \leq N-1)$ 行：$A[i]\ B[i]$
• 第 $N+2+j$ $(0 \leq j \leq Q-1)$ 行：$L1[j]\ R1[j]\ L2[j]\ R2[j]$

输出格式如下：

• 第 $1$ 行：设 maxsum 返回值为 $S$，则输出 $S[0]\ S[1]\ \cdots\ S[Q-1]$

请注意，示例评测程序可能与实际评测程序有所不同。