You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个长度为 $N$ 的数列 $A=(A_0,\ldots,A_{N-1})$，判断满足以下所有条件的整数四元组 $(x,y,z,w)$ 是否存在：

• $0\leq x < y < z < w \leq N$
• $A_x+A_{x+1}+\cdots+A_{y-1} = P$
• $A_y+A_{y+1}+\cdots+A_{z-1}= Q$
• $A_z+A_{z+1}+\cdots+A_{w-1}=R$

名词解释：

$N$ 元组：$N$ 个有关联的元素，按照一定顺序组成的一个序列。

数据范围

• $3\le N \le 2 \times10^5$
• $1\le A_i \le 10^9$
• $1 \le P,Q,R \le 10^{15}$

输入格式

两行，第一行分别是 $N,P,Q,R$ 四个整数，第二行是 $N$ 个数 $A_i$：

$N$ $P$ $Q$ $R$

$A_0$ $A_1$ $\ldots$ $A_{N-1}$

输出格式

如果满足条件的四元组存在，输出 Yes，否则输出 No。

所以本题的测试数据捆绑了 subtask（必然的）。

样例 #1

样例输入 #1

10 5 7 5
1 3 2 2 2 3 1 4 3 2

样例输出 #1

Yes

样例 #2

样例输入 #2

9 100 101 100
31 41 59 26 53 58 97 93 23

样例输出 #2

No

样例 #3

样例输入 #3

7 1 1 1
1 1 1 1 1 1 1

样例输出 #3

Yes

提示

看数据范围：$3 \le N \le 2\times 10^5$

暴力肯定会 TLE，所以肯定要优化。

优化思路1

本题要多次求区间和，因此肯定可以用 前缀和 优化。

• 前缀和数组 s[i]=a[0]+a[1]+...+a[i-1]
• 求出前缀和数组后，原数组的区间和 a[L]+a[L+1]+...+a[R] 就等于 s[R]-s[L-1]

优化思路2

把题中的条件改写成前缀和形式。以第一个条件为例：

$A_x+A_{x+1}+\cdots+A_{y-1} = P$

为了描述方便，规定 $S_0=0$, $S_1=A_0$，以此类推，那么上面的式子就可以改写成

$S_y-S_x=P \rightarrow S_y=S_x+P$

注意到 $A_i$ 都是正整数，所以 $S_i$ 是单调递增的，那么后续就可以采用 二分查找 来求解本题了。

其他几个条件如法炮制。

参考

• 二分查找可以使用 STL 里的函数 binary_search。例：

int a[5]={11,22,33,44,55};
if(binary_search(a, a+5, 33))
    cout<<"存在33";

• 也可以把所有的前缀和存入 set 中，使用 set 的 find 方法查找。例：

set<int> s;
s.insert(11); s.insert(22); s.insert(33);
if(s.find(22) != s.end())
    cout<<"存在22";

两种做法花费的时间都是 $O(\log n)$。