[DS记录]P7482 不条理狂诗曲
command_block
2021-07-18 20:03:20
为什么我的大脑在读标题的时候自动多塞进去一个“序”字啊……
**题意** ： 给出一个长度为 $n$ 的非负整数序列 $A$ ，记 $f(l,r)$ 为 $A[l,r]$ 中选出若干不相邻元素的和的最大值。
求下列式子的值。
$$\sum\limits_{1\leq l\leq r\leq n}f(l,r)$$
答案可能较大，对 $10^9+7$ 取模。
$n\leq 10^5$ ，时限$\texttt{1s}$。
------------
考虑分治，每次计算跨越分界线 $(m,m+1)$ 的所有区间的贡献。
记 $s_{0,l}$ 表示 $A[l,m-1]$ 中出若干不相邻元素的最大和。
记 $s_{1,l}$ 表示 $A[l,m]$ 中出若干不相邻元素的最大和。
记 $s_{0,r}$ 表示 $A[m+2,r]$ 中出若干不相邻元素的最大和。
记 $s_{1,r}$ 表示 $A[m+1,r]$ 中出若干不相邻元素的最大和。
都容易用 DP 线性求出。
此时可以求单个 $f(l,r)$ ：
$$f(l,r)=\max\big(s_{0,l}+s_{1,r},s_{1,l}+s_{0,r}\big)$$
写出跨越分界线 $(m,m+1)$ 的所有区间的贡献 ：
$$\sum_{1\leq l\leq m}\sum_{m+1\leq r\leq n}\max\big(s_{0,l}+s_{1,r},s_{1,l}+s_{0,r}\big)$$
对每个 $l$ 分别计算。对 $\max$ 的决策进行分类讨论。
$s_{0,l}+s_{1,r}>s_{1,l}+s_{0,r}\quad \Leftrightarrow \quad s_{0,l}-s_{1,l}>s_{0,r}-s_{1,r}$
于是，将 $r$ 按照 $s_{0,r}-s_{1,r}$ 排序，满足 $s_{0,l}+s_{1,r}>s_{1,l}+s_{0,r}$ 的就是一个前缀，可以二分得出。
贡献用前缀和计算。
复杂度 $O(n\log^2n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 100500
using namespace std;
const int mod=1000000007;
int a[MaxN],ans,sl1[MaxN],sr0[MaxN],p[MaxN];
ll s0[MaxN],s1[MaxN];
bool cmp(int A,int B)
{return s0[A]-s1[A]<s0[B]-s1[B];}
void solve(int l,int r)
{
if (l==r){ans=(ans+a[l])%mod;return ;}
int m=(l+r)>>1;
solve(l,m);solve(m+1,r);
s0[m]=0;s0[m-1]=a[m-1];
s1[m]=a[m];s1[m-1]=max(a[m-1],a[m]);
for (int i=m-2;i>=l;i--){
s0[i]=max(s0[i+1],s0[i+2]+a[i]);
s1[i]=max(s1[i+1],s1[i+2]+a[i]);
}
s0[m+1]=0;s0[m+2]=a[m+2];
s1[m+1]=a[m+1];s1[m+2]=max(a[m+2],a[m+1]);
for (int i=m+3;i<=r;i++){
s0[i]=max(s0[i-1],s0[i-2]+a[i]);
s1[i]=max(s1[i-1],s1[i-2]+a[i]);
}
int tn=0;
for (int i=m+1;i<=r;i++)p[++tn]=i;
sort(p+1,p+tn+1,cmp);
for (int i=1;i<=tn;i++)sl1[i]=(sl1[i-1]+s1[p[i]])%mod;
sr0[tn+1]=0;for (int i=tn;i;i--)sr0[i]=(sr0[i+1]+s0[p[i]])%mod;
for (int i=l;i<=m;i++){
int tl=0,tr=tn,mid;
ll lim=s0[i]-s1[i];
while(tl<tr){
int mid=(tl+tr+1)>>1;
if (s0[p[mid]]-s1[p[mid]]<lim)tl=mid;
else tr=mid-1;
}ans=(ans+s0[i]%mod*tl+s1[i]%mod*(tn-tl)+sl1[tl]+sr0[tl+1])%mod;
}
}
int n;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
solve(1,n);
printf("%d",ans);
return 0;
}
```