序列修改
题目链接：ybtoj高效进阶 21253
题目大意
给你一个序列，然后一个序列的费用是每个前缀的大小乘里面的数字种类的和。
然后你可以至多修改一个数，费用是原来到现在的绝对值，要你最小化序列费用和修改费用的和。
思路
首先我们可以简单算出一开始不修改的费用，然后考虑修改之后会优多少。
然后考虑枚举每一个点 i i i 修改。
然后首先看出，变成一个没有出现过的数肯定是不优的， 1 ∼ i − 1 1\sim i-1 1∼i−1 的种类不变， i ∼ n i\sim n i∼n 的变大。
然后考虑对剩下的情况分类讨论：
那首先我们设
z
z
z 是
a
i
a_i
ai 下一次出现的位置（如果是最后一个就是
n
+
1
n+1
n+1）
然后变成了
a
j
a_j
aj。
然后首先我们可以搞 S i ∼ j = ∑ k = i j k S_{i\sim j}=\sum_{k=i}^jk Si∼j=∑k=ijk，可以用前缀和得到。
如果 j < i j<i j<i，那从 i ∼ z − 1 i\sim z-1 i∼z−1 种类都会减一，变更费用是 ∣ a i − a j ∣ − S i + 1 ∼ z |a_i-a_j|-S_{i+1\sim z} ∣ai−aj∣−Si+1∼z，然后你发现只有 a j a_j aj 是跟 j j j 有关，那你可以用 set 维护最优的 j j j，进行转移。
接下来就是
j
>
i
j>i
j>i，然后就开
j
,
z
j,z
j,z 的位置关系：
如果
j
<
z
j<z
j<z，那变更代价就是
∣
a
i
−
a
j
∣
−
S
j
+
1
∼
z
|a_i-a_j|-S_{j+1\sim z}
∣ai−aj∣−Sj+1∼z。
如果
j
>
z
j>z
j>z，那你会发现这是没有意义的，变更代价是
0
0
0。
然后发现有一个绝对值，考虑把它弄开：
a
i
<
a
j
a_i<a_j
ai<aj：
a
j
−
a
i
−
S
j
+
1
∼
z
a_j-a_i-S_{j+1\sim z}
aj−ai−Sj+1∼z
a
i
>
a
j
a_i>a_j
ai>aj：
a
i
−
a
j
−
S
j
+
1
∼
z
a_i-a_j-S_{j+1\sim z}
ai−aj−Sj+1∼z
然后你让
s
i
=
∑
j
=
1
i
j
s_{i}=\sum_{j=1}^ij
si=∑j=1ij，那就可以分别表示成：
(
s
z
−
a
i
)
−
(
s
j
−
a
j
)
(s_z-a_i)-(s_j-a_j)
(sz−ai)−(sj−aj)
(
s
z
+
a
i
)
−
(
s
j
+
a
j
)
(s_z+a_i)-(s_j+a_j)
(sz+ai)−(sj+aj)
然后你可以用两个树状数组来维护，就可以啦。
代码
#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
int n, nm[500001], nxt[500001];
ll a[500001], sum[500001], answer, ans;
map <int, int> lst;
bool fir[500001];
set <int> v;
struct SZSJ {//树状数组
ll a[500001];
void start() {
memset(a, -0x7f, sizeof(a));
}
void add(int x, ll y) {
for (; x <= n; x += x & (-x))
a[x] = max(a[x], y);
}
ll query(int x) {
ll re = a[0];
for (; x; x -= x & (-x))
re = max(re, a[x]);
return re;
}
}T1, T2;
int main() {
// freopen("sequence.in", "r", stdin);
// freopen("sequence.out", "w", stdout);
scanf("%d", &n);
for (int i = n; i >= 1; i--) sum[i] = sum[i + 1] + 1ll * i;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
if (!lst[a[i]]) {
ans += sum[i];
fir[i] = 1;
nm[++nm[0]] = a[i];
}
else nxt[lst[a[i]]] = i;
lst[a[i]] = i;
nxt[i] = n + 1;
}
answer = ans;
sort(nm + 1, nm + nm[0] + 1);
v.insert(-INF); v.insert(INF);
T1.start(); T2.start();//前面部分
for (int i = 1; i <= n; i++)
if (fir[i]) {
set <int> :: iterator pl = v.lower_bound(a[i]);
answer = min(answer, ans - (sum[i] - sum[nxt[i]]) + abs(*pl - a[i]));
answer = min(answer, ans - (sum[i] - sum[nxt[i]]) + abs(*(--pl) - a[i]));
}
for (int i = n; i >= 1; i--) {//后面部分
int pla = lower_bound(nm + 1, nm + nm[0] + 1, a[i]) - nm;
answer = min(answer, ans + sum[nxt[i]] + a[i] - T1.query(pla));//两种情况，前缀后缀
answer = min(answer, ans + sum[nxt[i]] - a[i] - T2.query(n - pla + 1));
T1.add(pla, sum[i] + a[i]);
T2.add(n - pla + 1, sum[i] - a[i]);
}
printf("%lld", answer);
return 0;
}