\(O{(n\log n)}\) 做法
我在考场上只想到此做法，不难想到，可以将三段用二分预处理。
\(xs[i]\)表示从\(a_i\)开始总和为\(P\)的末尾编号，可以用二分处理。
最后 \(O(n)\) 判断即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e5+5;
const ll INF=0x3f3f3f3f;
ll n,x,y,z;
ll a,s[N];
ll xs[N],ys[N],zs[N];
int main(){scanf("%lld%lld%lld%lld",&n,&x,&y,&z);for(ll i=1;i<=n;i++){scanf("%lld",&a);s[i]=s[i-1]+a;}for(ll i=1;i<=n;i++){ll l=i,r=n;while(l<=r){ll mid=(l+r)/2;ll num=s[mid]-s[i-1];if(num>x) r=mid-1;else if(num<x) l=mid+1;else{l=mid;break;}}ll num=s[l]-s[i-1];if(num==x) xs[i]=l;else xs[i]=INF;}for(ll i=1;i<=n;i++){ll l=i,r=n;while(l<=r){ll mid=(l+r)/2;ll num=s[mid]-s[i-1];if(num>y) r=mid-1;else if(num<y) l=mid+1;else{l=mid;break;}}ll num=s[l]-s[i-1];if(num==y) ys[i]=l;else ys[i]=INF;}for(ll i=1;i<=n;i++){ll l=i,r=n;while(l<=r){ll mid=(l+r)/2;ll num=s[mid]-s[i-1];if(num>z) r=mid-1;else if(num<z) l=mid+1;else{l=mid;break;}}ll num=s[l]-s[i-1];if(num==z) zs[i]=l;else zs[i]=INF;}for(ll i=1;i<=n;i++){if(xs[i]>=n) continue;if(xs[i]==INF) continue;if(ys[xs[i]+1]>=n) continue;if(ys[xs[i]+1]==INF) continue;if(zs[ys[xs[i]+1]+1]==INF) continue;printf("Yes");return 0;}printf("No");return 0;
}
\(O{(n)}\) 做法
不难发现，以上做法是有点浪费的，每个节点需分别计算，其实可以线性\(O(n)\)一次计算出\(n\)个节点。
添加一个指针，如果区间里的值小于目标值，则指针往右移。
因为指针最多移\(n\)次，所以这个算法是线性的。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e5+5;
const ll INF=0x3f3f3f3f;
ll n,x,y,z,xp,yp,zp;
ll a,s[N];
ll xs[N],ys[N],zs[N];
int main(){scanf("%lld%lld%lld%lld",&n,&x,&y,&z);for(ll i=1;i<=n;i++){scanf("%lld",&a);s[i]=s[i-1]+a;}for(ll i=1;i<=n;i++){while(xp<n&&s[xp]-s[i-1]<x) xp++;if(s[xp]-s[i-1]==x) xs[i]=xp;else xs[i]=INF;}for(ll i=1;i<=n;i++){while(yp<n&&s[yp]-s[i-1]<y) yp++;if(s[yp]-s[i-1]==y) ys[i]=yp;else ys[i]=INF;}for(ll i=1;i<=n;i++){while(zp<n&&s[zp]-s[i-1]<z) zp++;if(s[zp]-s[i-1]==z) zs[i]=zp;else zs[i]=INF;}for(ll i=1;i<=n;i++){if(xs[i]>=n) continue;if(xs[i]==INF) continue;if(ys[xs[i]+1]>=n) continue;if(ys[xs[i]+1]==INF) continue;if(zs[ys[xs[i]+1]+1]==INF) continue;printf("Yes");return 0;}printf("No");return 0;
}
