CF631E Product Sum
传送门
闲话
模拟赛 D 题。感觉是个斜优的比较板的题。
开始写了一发错误的贪心，Wa on 9，后来改成 DP 才过。
场上过了 $5$ 个，拜谢 AK 爷 @Helloworld_wuyuze @RailgunZzzz @秦屎皇。
题意
给定一个长度为 $n$ 的序列，序列的价值定义为 $\sum_{i=1}^na_i\times i$。允许至多一次操作，把一个元素移动到任意一个序列中的位置，求最大的序列价值。
$2\le n\le 2\times 10^5，|a_i|\le 10^6$。
解析
先考虑 naive 做法。对于每个 $a_i$，枚举其移动到的位置位置 $j$，每次计算贡献的变化，时间复杂度 $O(n^2)$。
具体地，分两种情况讨论。对于向前移动，即 $j<i$，从 $i$ 移到 $j$ 后面，会使位于 $[j+1,i-1]$ 的元素贡献多一次，然后 $i$ 的贡献转化到了 $j+1$。
也就是 $s_{i-1}-s_{j}-(i-(j+1))\times a_i$。这里的 $s_i$ 表示 $a_i$ 的前缀和。
对于向后移动，移动到位置 $j$，会使 $[i+1,j]$ 的元素贡献少一次，再算上 $i$ 到 $j$ 的贡献。
$-(s_j-s_i)+(j-i)\times a_i$，即 $s_i-s_j+(j-i)\times a_i$。
尝试化简一下第一个式子。
$$
\begin{aligned}
&s_{i-1}-s_{j}-(i-(j+1))\times a_i\\
=&s_{i-1}-s_j-(i-j-1)\times a_i\\
=&s_{i-1}-s_j+a_i-(i-j)\times a_i\\
=&s_i-s_j-(i-j)\times a_i\\
=&s_i-s_j+(j-i)\times a_i
\end{aligned}
$$
我们推导可以发现，向前移动与向后移动的式子等价。这样的话，两个转移被合并成了一个转移，方便很多。
我们还需要优化。把括号拆开，变成 $s_i-s_j+a_i\times j-a_i\times i$。发现此时的方程中只有一个与 $i,j$ 都有关的项 $a_i\times j$ 和几个只与 $i$ 或 $j$ 有关的项。是斜率优化的经典形式，此处不赘述斜优过程。
数据没有单调性，所以可以用二分凸包或者李超树维护。
代码实现
考场上没想到可以变一个式子，正反做了两遍，二分+栈。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define endl '\n'
#define pii pair<int,int>
#define eb emplace_back
#define F(i,x,y) for(int i=(x);i<=(y);++i)
#define fo(i,x,y) for(int i=(x);i>=(y);--i)
constexpr int N=2e5+10;
constexpr int M=5e5+10;
constexpr int mod=1e9+7;
constexpr int inf=0x3f3f3f3f;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
constexpr db eps=1e-8;
#define int long long
int a[N],f[N];
struct line{
int k,b;
line(){}
line(int _k,int _b){
k=_k,b=_b;
}
int calc(int x){
return k*x+b;
}
};
struct tree{
#define t1 s.size()-1
#define t2 s.size()-2
vector<line> s;
bool cmp(line x,line p1,line p2){
return (p2.b-x.b)*(p1.k-p2.k)<=(p2.b-p1.b)*(x.k-p2.k);
}
void insert(line x){
while(s.size()>=2&&cmp(x,s[t1],s[t2])) s.pop_back();
s.eb(x);
}
int query(int x){
int l=0,r=t1;
while(l<r){
int mid=(l+r)>>1;
if(s[mid].calc(x)>=s[mid+1].calc(x)) r=mid;
else l=mid+1;
}
return s[r].calc(x);
}
#undef t1
#undef t2
}t1,t2;
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,res=0,ans=0;
cin>>n;
F(i,1,n){
cin>>a[i];
f[i]=f[i-1]+a[i];
res+=i*a[i];
}
t1.insert(line(1,-f[0]));
F(i,2,n){
ans=max(ans,-a[i]*i+f[i-1]+t1.query(a[i]));
t1.insert(line(i,-f[i-1]));
}
t2.insert(line(-n,-f[n]));
fo(i,n-1,1){
ans=max(ans,-a[i]*i+f[i]+t2.query(-a[i]));
t2.insert(line(-i,-f[i]));
}
cout<<ans+res<<endl;
return 0;
}
|
赛后用李超树写了第二种实现，$k=j,b=-s_j$，查询 $x=a_i$ 处的最值。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define endl '\n'
#define pii pair<int,int>
#define eb emplace_back
#define F(i,x,y) for(int i=(x);i<=(y);++i)
#define fo(i,x,y) for(int i=(x);i>=(y);--i)
constexpr int N=2e5+10;
constexpr int M=1e6;
constexpr int mod=1e9+7;
constexpr int inf=0x3f3f3f3f;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
constexpr db eps=1e-8;
#define int long long
int k[N],b[N],s[N],a[N];
int calc(int i,int x){return k[i]*x+b[i];}
int t[M<<4];
void update(int p,int l,int r,int x){
if(l==r){
if(calc(x,l)>calc(t[p],l)) t[p]=x;
return ;
}
int mid=(l+r)>>1;
if(calc(x,mid)>calc(t[p],mid)) swap(t[p],x);
if(calc(x,l)>calc(t[p],l)) update(p<<1,l,mid,x);
else if(calc(x,r)>calc(t[p],r)) update(p<<1|1,mid+1,r,x);
}
int query(int p,int l,int r,int x){
if(l==r) return calc(t[p],x);
int mid=(l+r)>>1;
int res=calc(t[p],x);
if(x<=mid) return max(res,query(p<<1,l,mid,x));
else return max(res,query(p<<1|1,mid+1,r,x));
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,res=0,ans=0;
cin>>n;
F(i,1,n){
cin>>a[i];
res+=i*a[i];
s[i]=a[i]+s[i-1];
k[i]=i;
b[i]=-s[i];
update(1,-M,M,i);
}
F(i,1,n){
int tmp=query(1,-M,M,a[i]);
ans=max(ans,s[i]-a[i]*i+tmp);
}
cout<<ans+res<<endl;
return 0;
}
|
完结撒花！
