ABC #437
\(B\) 题
模拟即可，暴力计算。
\(C\) 题
简单贪心，按照 \(w+p\)（转换花费）排序即可
\(D\) 题
题意：求 \(|A_i-B_j|\) 的和。
枚举 \(A_i\)，然后二分查找一个 \(j\)，使 \(B_j<A_i,B_{j+1}\ge A_i\)。这样消除绝对值，然后前缀和。
\(E\) 题
Trie 上 dfs。后面会搞一个文章。
ABC #438
\(B\) 题
枚举字串的起始点，然后统计答案。
\(C\) 题
显然是能删除就删除，于是开一个栈统计即可。
\(D\) 题
伪了，我说为什么D wa 了，原来 \(x<y<n\),我以为还能取等呢。
然后就 A 了 https://atcoder.jp/contests/abc438/submissions/72048791
首先蛇头很好计算，枚举 \(x\)，计算前缀和即可。
其次是蛇身和蛇尾，我们需要找到贡献最大的 \(y\)。
考虑如果 \(y\) 加上 \(1\)，那么蛇头和蛇尾之和 \(s\) 加上了 \(b_i-c_i\)。
于是可以记录 \(d_i=b_i-c_i\)，再用 \(q\) 作为 \(d\) 的前缀和。
显然要找的 \(y\) 是 \([x+1,n-1]\) 内 \(q\) 的最大值的位置。于是开一个线段树维护。
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
#define int long long
int a[maxn],b[maxn],c[maxn],d[maxn],q[maxn],qa[maxn],qb[maxn],qc[maxn];
/*
#### 问题陈述> Snuke 正在观察一条蛇，他很好奇蛇的头部、蛇身和蛇尾分别是哪个部分。他把蛇分成了 $N$ 块，并评估了每个块的头部相似度、身体相似度和尾部相似度。然后，他决定找出使相似值总和最大的分割方法。给你长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$ 、 $B = (B_1, B_2, \ldots, B_N)$ 和 $C = (C_1, C_2, \ldots, C_N)$ 。求满足 $1 \leq x < y < N$ 的一对整数 $(x, y)$ 的最大可能值 $\displaystyle\sum_{i = 1}^{x} A_i + \sum_{i = x + 1}^{y} B_i + \sum_{i = y + 1}^{N} C_i$ 。*/
struct T{#define ls id<<1#define rs id<<1|1struct node{int l,r,max,mapos;}t[maxn*4];void up(int id){if(t[ls].max>=t[rs].max){t[id].max=t[ls].max;t[id].mapos=t[ls].mapos;}else{t[id].max=t[rs].max;t[id].mapos=t[rs].mapos;}}void build(int id,int l,int r,int tt[]){t[id].l=l,t[id].r=r;if(l==r){t[id].max=tt[l];t[id].mapos=l;return;}int mid=(l+r)>>1;build(ls,l,mid,tt);build(rs,mid+1,r,tt);up(id);}pair<int,int> query(int id,int l,int r){if(t[id].l>r||t[id].r<l)return {LLONG_MIN,0};if(t[id].l>=l&&t[id].r<=r)return {t[id].max,t[id].mapos};pair<int,int> a=query(ls,l,r);pair<int,int> b=query(rs,l,r);if(a.first>=b.first)return a;return b;}
};
signed main() {int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];for(int i=1;i<=n;i++)cin>>c[i];for(int i=1;i<=n;i++){d[i]=b[i]-c[i];q[i]=q[i-1]+d[i];qa[i]=qa[i-1]+a[i];qb[i]=qb[i-1]+b[i];// qc[i]=qc[i-1]+c[i];}T t;t.build(1,1,n,q);int ans=LLONG_MIN;for(int x=1;x<n;x++){int sum1=qa[x];//y+1带来的影响：sum2+sum3加上b[i]-c[i]//需要找出一个y使得q[y]-q[x]最大ans=max(ans,sum1+qb[t.query(1,x+1,n-1).second]-qb[x]+qc[n]-qc[t.query(1,x+1,n-1).second]);}cout<<ans;return 0;
}