P11947 [KTSC 2025] 可爱区间 / maxsum

版权信息：译自 [2025年度 国际情报 올림피아드 (Olympiad) 代表学生 选拔考试](https://www.ioikorea.or.kr/archives/ioitst/2025/) R2T2。[[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/)]

给定长度为 $n$ 的整数数列 $A_0\sim A_{n-1}$，$B_0\sim B_{n-1}$。保证 $A_i\le B_i$。 定义区间 $[l,r]$ 是**可爱的**，当且仅当： - $l,r\in \mathbb{Z}$，且 $0\le l\le r\lt n$； - 存在一个长度为 $n$ 的整数数列 $C_0\sim C_{n-1}$，使得： 1. $\forall 0\le i\lt n$，都有 $C_i\in [A_i,B_i]$； 2. $\forall 0\le L\le R\lt n$，都有 $\displaystyle \sum_{L\le i\le R} C_i\le \sum_{l\le i\le r} C_i$。 - 换言之，$[l,r]$ 取到 $C$ 的最大子段和。 $q$ 次询问，第 $i$ 次询问给定四个非负整数 $L_{1,i},R_{1,i},L_{2,i},R_{2,i}$，求出满足以下条件的区间 $[l,r]$ 的数量： - $l\in [L_{1,i},R_{1,i}]$； - $r\in [L_{2,i},R_{2,i}]$； - $[l,r]$ 是可爱的。 ### 实现细节 你不需要，也不应该实现 `main` 函数。 你应当实现以下的函数： ```cpp vector maxsum(vector A, vector B, vector L1, vector R1, vector L2, vector R2); ``` - `A`，`B`：长度为 $n$ 的整数数组； - `L1`，`R1`，`L2`，`R2`：长度为 $q$ 的非负整数数组。 - $\forall 0\le i\lt q$，`L1[i]`,`R1[i]`,`L2[i]`,`R2[i]` 描述一次询问。 - 返回一个长度为 $q$ 的非负整数数组 `S`，其中 `S[i]` 表示第 $i$ 个询问的答案。

Sample Grader 输入格式如下： 第一行，两个正整数 $n,q$。 接下来 $n$ 行，每行两个整数 $A_i,B_i$。 接下来 $q$ 行，第 $i$ 行四个非负整数 $L_{1,i},R_{1,i},L_{2,i},R_{2,i}$。

Sample Grader 输出一行 $q$ 个整数 `S[0], S[1], ..., S[Q−1]`。

### 样例交互 #### 样例交互 $1$ - $N=3$, $Q=3$，$A = [-1, -1, -1]$, $B = [2, -1, 2]$； - $L_1 = [0, 0, 1]$，$R_1 = [2, 0, 2]$，$L_2 = [0, 0, 0]$，$R_2 = [2, 2, 1]$。 交互库调用 ```cpp 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]$ 满足条件。 - $[0,1]$ 不是可爱的。由于 $C_1=-1$，无论其他位置填什么，都有 $C_0\gt C_0+C_1$。 类似地，可以证明：只有 $[0, 0],[0, 2],[1, 1],[2, 2]$ 是可爱的区间。 返回 $[4, 2, 1]$。 ### 数据范围 - $1 \leq n, q \leq 250\,000$； - $-10^9 \leq A_i \leq B_i \leq 10^9$； - $0 \leq L_{1,j} \leq R_{1,j} \leq N−1$； - $0 \leq L_{2,j} \leq R_{2,j} \leq N−1$。 ### 子任务 - $\text{Subtask 1 (5 pts)}$：$n\le 500$。 - $\text{Subtask 2 (11 pts)}$：$n\le 5\, 000$。 - $\text{Subtask 3 (45 pts)}$：$q=1$，$L_{1,0}=L_{2,0}=0$，$R_{1,0}=R_{2,0}=n-1$。 - $\text{Subtask 4 (12 pts)}$：$L_{1,i}=R_{1,i}$，$L_{2,i}=R_{2,i}$。 - $\text{Subtask 5 (27 pts)}$：无额外限制。