Rockdu's Blog

N
A1
A2
:
AN

5
4
1
8
8
7

2

20
8
2
9
7
4
6
7
9
7
4
7
4
4
3
6
2
3
4
4
9

62

题目大意：给你一个数列，你每一次可以进行两种操作：

1. 把一个数加1
2. 交换两个数

问你最少用多少次操作能把数列变为不下降的。

这个题可以理解成维护离散的折线……

我们考虑每一次把后面的一个数a[i]加到考虑范围内，并且时刻更新答案。

这样我们每一次多考虑一个数a[i]，那么把a[i]的数值变为V并且使得数列不下降的最小花费应该是 V - a[i] + 比V大的数的个数（我们每次加完再往前换）。

正确性可以感性理解……

到这里就可以去打一颗动态开点查询最小值的权值线段树了，因为考虑每一次寻找代价最小的。如果当前方案把a[i]变成了V，那么后面要变成所有比V大的值的情况花费会增加+1。因此我们写一个区间修改，我们就可以时刻维护：把当前数a[i]变为0~1e9的所有方案的最优解。

#include<cstdio>
#include<algorithm>
#include<iostream>
#define LL long long
#define N 1e9
using namespace std;
const int maxn = 3e5 + 5;
namespace SGT {
	struct node {
		LL mn, add;
		int ch[2];
	}t[maxn * 32];
	int cnt, root;
	int Create(int l, int r) {
		return t[++cnt] = (node) {l, 0, 0, 0}, cnt;
	}
	void push_up(int rt, int l, int r) {
		int mid = l + r >> 1;
		if(!t[rt].ch[0]) t[rt].ch[0] = Create(l, mid);
		if(!t[rt].ch[1]) t[rt].ch[1] = Create(mid + 1, r);
		t[rt].mn = min(t[t[rt].ch[0]].mn, t[t[rt].ch[1]].mn);
	}
	void push_down(int rt, int l, int r) {
		if(t[rt].add) {
			int mid = l + r >> 1, *ls = &t[rt].ch[0], *rs = &t[rt].ch[1];
			if(!*ls) *ls = Create(l, mid);
			if(!*rs) *rs = Create(mid + 1, r);
			t[*ls].add += t[rt].add, t[*ls].mn += t[rt].add;
			t[*rs].add += t[rt].add, t[*rs].mn += t[rt].add;
			t[rt].add = 0;
		}
	}
	LL Q(int l, int r, int tl, int tr, int & rt = root) {
		if(!rt) rt = Create(tl, tr);
		if(l == tl && r == tr) 
			return t[rt].mn;
		int mid = tl + tr >> 1;
		push_down(rt, tl, tr);
		if(r <= mid) return Q(l, r, tl, mid, t[rt].ch[0]);
		else if(l > mid) return Q(l, r, mid + 1, tr, t[rt].ch[1]);
		else return min(Q(l, mid, tl, mid, t[rt].ch[0]), Q(mid + 1, r, mid + 1, tr, t[rt].ch[1]));
	}
	void add(int l, int r, int tl, int tr, LL dt, int & rt = root) {
		if(!rt) rt = Create(tl, tr);
		if(tl == l && tr == r) 
			return t[rt].add += dt, t[rt].mn += dt, void();
		int mid = tl + tr >> 1;
		push_down(rt, tl, tr);
		if(r <= mid) add(l, r, tl, mid, dt, t[rt].ch[0]);
		else if(l > mid) add(l, r, mid + 1, tr, dt, t[rt].ch[1]);
		else add(l, mid, tl, mid, dt, t[rt].ch[0]), add(mid + 1, r, mid + 1, tr, dt, t[rt].ch[1]);
		push_up(rt, tl, tr);
	}
}
int n, a[maxn];
LL ans;
signed main() {
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for(register int i = 1; i <= n; ++i) {
		ans += SGT :: Q(a[i], N, 0, N) - a[i];
		SGT :: add(0, a[i] - 1, 0, N, 1);
	}
	printf("%lld", ans);
	return 0;
}