前置知识
解法
由 [ABC351F] Double Sum 的套路，尝试展开绝对值及 \(\min,\max\)。
将式子拆开有 \(\begin{aligned} & \min\limits_{k=0}^{n-1}\{ \sum\limits_{i=1}^{n-k}|a_{i}-(i+k)|+ \sum\limits_{i=n-k+1}^{n}|a_{i}-(i-(n-k))| \} \\ &=\min\limits_{k=0}^{n-1}\{ \sum\limits_{i=1}^{n-k}( \max(a_{i},i+k)- \min(a_{i},i+k))+ \sum\limits_{i=n-k+1}^{n}( \max(a_{i},i+k-n)- \min(a_{i},i+k-n)) \} \\ &=\min\limits_{k=0}^{n-1}\{ \sum\limits_{i=1}^{n-k}(a_{i}+i+k-2 \min(a_{i},i+k))+ \sum\limits_{i=n-k+1}^{n}(a_{i}+i+k-n-2 \min(a_{i},i+k-n)) \} \\ &=\sum\limits_{i=1}^{n}(a_{i}+i)+\min\limits_{k=0}^{n-1}\{- \sum\limits_{i=1}^{n-k}2 \min(a_{i},i+k)- \sum\limits_{i=n-k+1}^{n}2 \min(a_{i},i+k-n) \} \\ &=\sum\limits_{i=1}^{n}(a_{i}+i)-2 \max\limits_{k=0}^{n-1}\{\sum\limits_{i=1}^{n-k} \min(a_{i},i+k)+\sum\limits_{i=n-k+1}^{n} \min(a_{i},i+k-n) \} \end{aligned}\)。
- 好像式子推多了，懒得改了，只是常数大点。
现在问题来到了怎么求 \(\max\limits_{k=0}^{n-1}\{\sum\limits_{i=1}^{n-k} \min(a_{i},i+k)+\sum\limits_{i=n-k+1}^{n} \min(a_{i},i+k-n) \}\)。
令 \(\begin{cases} x_{i}=a_{i}-i \\ y_{i}=a_{i}+n-i \end{cases}\)，由于是排列所以 \(\{ x \},\{ y \}\) 均满足内部两两不同，则转化为求 \(\max\limits_{k=0}^{n-1}\{\sum\limits_{i=1}^{n-k}([k \ge x_{i}] \times a_{i}+[k<x_{i}] \times (i+k))+\sum\limits_{i=n-k+1}^{n}([k \ge y_{i}] \times a_{i}+ [k<y_{i}] \times (i+k-n)) \}\)，前半部分将其拆成 \(\begin{cases} [k \ge x_{i}] \times a_{i} \\ [k<x_{i}] \times i \\ [k<x_{i}] \times k \end{cases}\) 三部分，后半部分同理。
将 \(\{ x \},\{ y \}\) 分别插入到权值树状数组里，分别维护 \(\begin{cases} [k \ge x_{i}] \times a_{i}/[k \ge y_{i}] \times a_{i} \\ [k<x_{i}] \times i/[k<y_{i}] \times (i-n) \\ [k<x_{i}]/[k<y_{i}] \end{cases}\) 即可，注意及时消除影响。
对于负数整体向右移来处理。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
ll a[3000010],x[3000010],y[3000010],c[6][3000010];
ll lowbit(ll x)
{
return (x&(-x));
}
void add(ll n,ll x,ll val,ll c[])
{
x+=1000001;
n+=1000001;
for(ll i=x;i<=n;i+=lowbit(i))
{
c[i]+=val;
}
}
ll ask(ll x,ll c[])
{
ll ans=0;
x+=1000001;
for(ll i=x;i>=1;i-=lowbit(i))
{
ans+=c[i];
}
return ans;
}
int main()
{
ll n,ans=0,pos=0,sum=0,i,k;
scanf("%lld",&n);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
x[i]=a[i]-i;
y[i]=a[i]+n-i;
add(2*n,x[i],a[i],c[0]);
add(2*n,x[i],i,c[2]);
add(2*n,x[i],1,c[4]);
}
for(k=0;k<=n-1;k++)
{
sum=0;
sum+=ask(k,c[0]);
sum+=ask(2*n,c[2])-ask(k,c[2]);
sum+=(ask(2*n,c[4])-ask(k,c[4]))*k;
sum+=ask(k,c[1]);
sum+=ask(2*n,c[3])-ask(k,c[3]);
sum+=(ask(2*n,c[5])-ask(k,c[5]))*k;
if(sum>ans)
{
ans=sum;
pos=k;
}
add(2*n,x[n-k],-a[n-k],c[0]);
add(2*n,x[n-k],-(n-k),c[2]);
add(2*n,x[n-k],-1,c[4]);
add(2*n,y[n-k],a[n-k],c[1]);
add(2*n,y[n-k],n-k-n,c[3]);
add(2*n,y[n-k],1,c[5]);
}
ans*=-2;
for(i=1;i<=n;i++)
{
ans+=a[i]+i;
}
printf("%lld %lld\n",ans,pos);
return 0;
}