序列修改
题目链接:ybtoj高效进阶 21253
题目大意
给你一个序列,然后一个序列的费用是每个前缀的大小乘里面的数字种类的和。
然后你可以至多修改一个数,费用是原来到现在的绝对值,要你最小化序列费用和修改费用的和。
思路
首先我们可以简单算出一开始不修改的费用,然后考虑修改之后会优多少。
然后考虑枚举每一个点 \(i\) 修改。
然后首先看出,变成一个没有出现过的数肯定是不优的,\(1\sim i-1\) 的种类不变,\(i\sim n\) 的变大。
然后考虑对剩下的情况分类讨论:
那首先我们设 \(z\) 是 \(a_i\) 下一次出现的位置(如果是最后一个就是 \(n+1\))
然后变成了 \(a_j\)。
然后首先我们可以搞 \(S_{i\sim j}=\sum_{k=i}^jk\),可以用前缀和得到。
如果 \(j<i\),那从 \(i\sim z-1\) 种类都会减一,变更费用是 \(|a_i-a_j|-S_{i+1\sim z}\),然后你发现只有 \(a_j\) 是跟 \(j\) 有关,那你可以用 set 维护最优的 \(j\),进行转移。
接下来就是 \(j>i\),然后就开 \(j,z\) 的位置关系:
如果 \(j<z\),那变更代价就是 \(|a_i-a_j|-S_{j+1\sim z}\)。
如果 \(j>z\),那你会发现这是没有意义的,变更代价是 \(0\)。
然后发现有一个绝对值,考虑把它弄开:
\(a_i<a_j\):\(a_j-a_i-S_{j+1\sim z}\)
\(a_i>a_j\):\(a_i-a_j-S_{j+1\sim z}\)
然后你让 \(s_{i}=\sum_{j=1}^ij\),那就可以分别表示成:
\((s_z-a_i)-(s_j-a_j)\)
\((s_z+a_i)-(s_j+a_j)\)
然后你可以用两个树状数组来维护,就可以啦。
代码
#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;
}