题解 CF631E 【Product Sum】
吹雪吹雪吹
2019-04-17 20:34:58
[${\large \color{#ff7daf}{\text{CF631E Product Sum}}}$](http://xc.fubuki.cn/2019/%E6%96%9C%E7%8E%87%E4%BC%98%E5%8C%96/)
题意：整个序列的分数为 $\sum\limits_{i=1}^{n}a_i·i$ ，你可以将某个元素向任意方向移动任意位，求一次该操作后可获得的最大分数。
设 $sum_i = \sum\limits_{j=1}^{i}a_i$
接下来以将第 $i$ 个元素向前移动**到**第 $j$ 个位置为例：
将 $a_i$ 移到 $j$ 增加的分数： $(j-i)·a_i-(sum_j-sum_i)$
尝试斜率优化，设 $k > j$ 且选择 $k$ 要优于选择 $j$：
$(j-i)·a_i-(sum_j-sum_i)<(k-i)·a_i-(sum_k-sum_i)$
移项后合并同类项：
$j·a_i-sum_j<k·a_i-sum_k$
再移项：
$sum_k-sum_j<(k-j)·a_i$
$\frac{sum_j-sum_k}{j-k}<a_i$
维护上凸壳，二分进行决策即可。
将某一元素向后移动类似，此处不做赘述。
代码（不可AC，但是正确(^_^)）：
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 200005
#define K(x, y) ((1.0 * w[x] - w[y]) / (1.0 * (x) - (y)))
#define Calc1(x, y) (sum[(x) - 1] - sum[(y) - 1] - a[x] * ((x) - (y)))
#define Calc2(x, y) (a[x] * ((y) - (x)) - (sum[(y)] - sum[(x)]))
using namespace std;
typedef int LL;
int n, stk[maxn], top = 0;
LL a[maxn], sum[maxn], ans = 0, w[maxn], res = 0;
inline int read()
{
char ch = getchar();
int ret = 0, f = 1;
while (ch > '9' || ch < '0')
{
if (ch == '-')
f = -f;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
ret = ret * 10 + ch - '0', ch = getchar();
return ret * f;
}
int main()
{
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
n = read();
for (int i = 1; i <= n; ++i)
{
a[i] = read();
sum[i] = sum[i - 1] + a[i];
ans += 1ll * i * a[i];
}
stk[1] = 1, stk[2] = 2, top = 2;
w[1] = sum[0], w[2] = sum[1];
res = max(0ll, Calc1(2, 1));
for (int i = 3; i <= n; ++i)
{
int l = 1, r = top - 1, j = stk[top];
while (l <= r)
{
int mid = (r - l >> 1) + l;
if (K(stk[mid + 1], stk[mid]) > a[i])
r = mid - 1, j = stk[mid];
else
l = mid + 1;
}
res = max(res, Calc1(i, j));
w[i] = sum[i - 1];
while (top > 1)
{
if (K(i, stk[top]) > K(stk[top], stk[top - 1]))
break;
--top;
}
stk[++top] = i;
}
stk[1] = n, stk[2] = n - 1, top = 2;
w[n] = sum[n], w[n - 1] = sum[n - 1];
res = max(res, Calc2(n - 1, n));
for (int i = n - 3; i > 0; --i)
{
int l = 1, r = top - 1, j = stk[top];
while (l <= r)
{
int mid = (r - l >> 1) + l;
if (K(stk[mid + 1], stk[mid]) < a[i])
r = mid - 1, j = stk[mid];
else
l = mid + 1;
}
res = max(res, Calc2(i, j));
w[i] = sum[i];
while (top > 1)
{
if (K(i, stk[top]) < K(stk[top], stk[top - 1]))
break;
--top;
}
stk[++top] = i;
}
printf("%I64d\n", ans + res);
return 0;
}
```
多一句嘴，网上三分什么的显然是错的，有兴趣的可以去叉一下。$\color{white}{\text{上面的代码开下 long long 就能过了}}$