背景

版权信息：译自 2025年度 国际情报 올림피아드 (Olympiad) 代表学生 选拔考试 R2T2。[CC 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 函数。

你应当实现以下的函数：

vector<long long> maxsum(vector<int> A, vector<int> B, 
                         vector<int> L1, vector<int> R1,  
                         vector<int> L2, vector<int> 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]。

3 3
-1 2
-1 -1
-1 2
0 2 0 2
0 0 0 2
1 2 0 1

4 2 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]$。

交互库调用

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)}$：无额外限制。