Atcoder Code Festival 2017 Exhibition B - Increment and Swap
? 解题记录 ? ? Atcoder ? ? 线段树 ?    2018-07-13 22:38:40    815    0    0

### Problem Statement

We have a sequence A of length N.

On this sequence, we can perform the following two kinds of operations:

• Select one element, and increment it by 1.

We will repeatedly perform these operations so that A will be a non-decreasing sequence. Find the minimum required number of operations.

### Constraints

• 1≤N≤200000
• 1≤Ai≤109
• Ai is an integer.

### Input

Input is given from Standard Input in the following format:

```N
A1
A2
:
AN```

### Output

Print the minimum number of operations required to turn A into a non-decreasing sequence.

Copy
```5
4
1
8
8
7```

### Sample Output 1

Copy
`2`

We can turn A into a non-decreasing sequence in two operations:

• Initially, A={4,1,8,8,7}.
• Swap the first two elements. Now, A={1,4,8,8,7}.
• Increment the last element by 1. Now, A={1,4,8,8,8}.

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

Copy
`62`

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

## 到这里就可以去打一颗动态开点查询最小值的权值线段树了，因为考虑每一次寻找代价最小的。如果当前方案把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 {
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) {
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);
}
}
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;
}```

815 人读过

0 条评论