「HNOI2002」营业额统计

传送门

这题比较板子吧应该。。。

有几个需要注意的地方：

第一次插入时就要贡献答案
在每次计算贡献时，注意分裂出来的子树是否为空，并且要对两边的相邻元素之差取 \(\min\)

参考代码：

#include <algorithm>

#include <cstdlib>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T & s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 1e5 + 5;

int n, ans, rt, tot, siz[_], val[_], pri[_], ch[2][_];

inline int Newnode(int v)

{ return siz[++tot] = 1, val[tot] = v, pri[tot] = rand(), tot; }

inline void pushup(int p) { siz[p] = siz[ch[0][p]] + siz[ch[1][p]] + 1; }

inline int merge(int x, int y) {

	if (!x || !y) return x + y;

	if (pri[x] > pri[y])

		return ch[1][x] = merge(ch[1][x], y), pushup(x), x;

	else

		return ch[0][y] = merge(x, ch[0][y]), pushup(y), y;

}

inline void split(int p, int v, int& x, int& y) {

	if (!p) { x = y = 0; return ; }

	if (val[p] <= v)

		return x = p, split(ch[1][p], v, ch[1][x], y), pushup(p);

	else

		return y = p, split(ch[0][p], v, x, ch[0][y]), pushup(p);

}

inline int kth(int p, int k) {

	if (siz[ch[0][p]] + 1 > k) return kth(ch[0][p], k);

	if (siz[ch[0][p]] + 1 == k) return val[p];

	if (siz[ch[0][p]] + 1 < k) return kth(ch[1][p], k - siz[ch[0][p]] - 1);

}

int main() {

    read(n), read(ans);

	rt = merge(rt, Newnode(ans));

	for (rg int x, a, b, i = 2; i <= n; ++i) {

		read(x), split(rt, x, a, b);

		int mn = 2147483647;

		if (a != 0) mn = min(mn, x - kth(a, siz[a]));

		if (b != 0) mn = min(mn, kth(b, 1) - x);

		ans += mn, rt = merge(a, merge(Newnode(x), b));

	}

	printf("%d\n", ans);

	return 0;

}

巴特西

「HNOI2002」营业额统计

「HNOI2002」营业额统计

最新文章

热门文章