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

Problem Statement

We have a sequence A of length N.

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

  • Swap two adjacent elements.

  • 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.


Sample Input 1

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}.

Sample Input 2

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

Sample Output 2

Copy
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;
}


上一篇: AGC024 E - Sequence Growing Hard

下一篇: 洛谷P3454 [POI2007]OSI-Axes of Symmetry

805 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航