「BZOJ3600」没有人的算术替罪羊树+线段树

题目描述

过长……不想发图也不想发文字，所以就发链接吧……

没有人的算术

题解

\(orz\)神题一枚

我们考虑如果插入的数不是数对，而是普通的数，这就是一道傻题了——直接线段树一顿乱上就可以了。

于是我们现在只需要解决一个问题——维护这些数的大小关系。

由于这些数具有有序性，我们可以将这些数的值重记为一个数，这样就可以无脑地比较了。并且，由于这些值的大小可能会随着插入而更改，所以要用一棵平衡树来维护。

那么问题来了，这个数取什么值比较好呢？

首先当然可以是排名，不过如果使用排名，每次访问值的时候都要重新在平衡树中查一次，复杂度肯定是\(O(nlog^2n)\)的，基本不现实。

换一个角度可以发现，我们只需要知道大小关系，不需要排名，于是我们可以用实数维护一个数的大小，虽然相邻的数差值大小不同，只要相对大小是正确的就不必担心了……

那么我们可以这样看，在平衡树中每个节点维护一个区间\((l,r)\)，表示这棵子树中所有数值都在\((l,r)\)之中，而这棵子树的根的值为\(mid=\frac{(l+r)}{2}\)递归左右子树的时候，将区间分成\((l,mid)\)和\((mid,r)\)，完全满足二叉搜索树的性质，并且可以随时在任何位置新增一个数而不影响已有的数的数值。

那么问题就得到了解决，我们用一棵平衡树维护出现过的所有数对，节点上保存这个数对的两个父亲和\((l,r)\)，并用\(mid=\frac{(l+r)}{2}\)表示这个节点的数值，然后无脑做插入和询问即可。

但是我们忽略了一个问题，我们应该使用什么样的平衡树？发现那些基于旋转的平衡树在旋转后都会出现一个致命的问题，\((l,r)\)无法维护！因为一次旋转会使得它以及它的子树全部的\((l,r)\)都被改变，复杂度难以承受。于是我们想到了替罪羊树，基于重构的它反正都要全部拍扁了重来，重新为区间赋值不就可以在重构时顺便一起做了吗？

于是，这道题就这么被切掉了……

（内心：哪有说的这么简单）

总结：

替罪羊树的维护方式与\(AVL\)、\(SBT\)、\(Splay\)都不一样，后几种算法都是通过旋转维护平衡，然而替罪羊树却是用重构维护平衡，重构的时候可以重新计算值，不需要通过原来的值进行改变。所以替罪羊树可以维护的信息更加灵活，并且拍扁重建很欢乐常数小。于是替罪羊树非常适合套其他的数据结构……树套树时也要想一想能不能用替罪羊树……

吐槽：植树节到了我们一起来欢乐种树写替罪羊树模板吧！

\(Code:\)

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define N 100005

#define M 800005

#define eps 1e-10

#define inf 1e20

#define equal(a, b) (fabs((a) - (b)) < eps)

#define val(a) (a == -1 ? -inf :(ls[a] + rs[a])/ 2)

#define lim 0.77

char opt[10];

int n, m;

void Insert(int q, int l, int r, int k, int a);

int getint()

{

	int p=0;

	char c=getchar();

	while(c<'0'||c>'9')c=getchar();

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

	return p;

}

struct SCT

{

	int root, cnt, sz[M];

	int num, arr[M];

	int lc[M], rc[M];

	int lf[M], rf[M];

	double ls[M], rs[M];

	bool Equal(int u, int l, int r)

	{

		return equal(val(lf[u]), val(l)) && equal(val(rf[u]), val(r));

	}

	bool Less(int u, int l, int r)

	{

		return equal(val(lf[u]), val(l)) ? val(rf[u]) < val(r) : val(lf[u]) < val(l);

	}

	void Pushup(int q)

	{

		sz[q] = sz[lc[q]] + sz[rc[q]] + 1;

	}

	void Getarray(int q)

	{

		if (lc[q])

			Getarray(lc[q]);

		arr[++num] = q;

		if (rc[q])

			Getarray(rc[q]);

	}

	void Rebuild(int &q, int l, int r, double L, double R)

	{

		if (l > r)

		{

			q = 0;

			return;

		}

		int mid = (l + r) >> 1;

		double Mid = (L + R) / 2;

		q = arr[mid];

		ls[q] = L;

		rs[q] = R;

		Rebuild(lc[q], l, mid - 1, L, Mid);

		Rebuild(rc[q], mid + 1, r, Mid, R);

		Pushup(q);

	}

	void Maintain(int &q)

	{

		num = 0;

		Getarray(q);

		Rebuild(q, 1, num, ls[q], rs[q]);

	}

	void Add(int &q, int l, int r, double L, double R, int k)

	{

		if (!q)

		{

			q = ++cnt;

			lf[q] = l, rf[q] = r;

			ls[q] = L, rs[q] = R;

			sz[q] = 1;

			Insert(1, 1, n, k, cnt);

			return;

		}

		if (Equal(q, l, r))

		{

			Insert(1, 1, n, k, q);

			return;

		}

		if (Less(q, l, r))

			Add(rc[q], l, r, (L + R) / 2, R, k);

		else

			Add(lc[q], l, r, L, (L + R) / 2, k);

		Pushup(q);

	}

	void Check(int &q, int l, int r)

	{

		if (sz[q] * lim < sz[lc[q]] || sz[q] * lim < sz[rc[q]])

		{

			Maintain(q);

			return;

		}

		if (Equal(q, l, r))

			return;

		if (Less(q, l, r))

			Check(rc[q], l, r);

		else

			Check(lc[q], l, r);

	}

}T;

struct data

{

	int plc, num;

	data(){}

	data(int a, int b){plc = a, num = b;}

	double Val(){return (T.ls[num] + T.rs[num])/ 2;}

	data operator + (data b)

	{

		if (num == 1 && b.num == 1)

			return plc < b.plc ? *this : b;

		if (num == 1)

			return b;

		if (b.num == 1)

			return *this;

		if (equal(Val(), b.Val()))

			return plc < b.plc ? *this : b;

		if (Val() > b.Val())

			return *this;

		return b;

	}

};

struct SGT

{

	data a[N << 2];

}S;

void Insert(int q, int l, int r, int k, int a)

{

	if (l == k && r == k)

	{

		S.a[q] = data(k, a);

		return;

	}

	int mid = (l + r) >> 1;

	if (k <= mid)

		Insert(q << 1, l, mid, k, a);

	else

		Insert(q << 1 | 1, mid + 1, r, k, a);

	S.a[q] = S.a[q << 1] + S.a[q << 1 | 1];

}

data Query(int q, int l, int r, int L, int R)

{

	if (l == L && r == R)

		return S.a[q];

	int mid = (l + r) >> 1;

	if (R <= mid)

		return Query(q << 1, l, mid, L, R);

	if (L > mid)

		return Query(q << 1 | 1, mid + 1, r, L, R);

	return Query(q << 1, l, mid, L, mid) + Query(q << 1 | 1, mid + 1, r, mid + 1, R);

}

int main()

{

	n = getint(), m = getint();

	T.root = T.cnt = 1;

	T.lf[1] = T.rf[1] = -1;

	T.ls[1] = 0, T.rs[1] = 1;

	for (int i = 1; i <= n; i++)

		Insert(1, 1, n, i, 1);

	for (int i = 1; i <= m; i++)

	{

		scanf("%s", opt);

		if (opt[0] == 'Q')

		{

			int l = getint(), r = getint();

			printf("%d\n", Query(1, 1, n, l, r).plc);

		}

		else

		{

			int l = getint(), r = getint(), k = getint();

			l = Query(1, 1, n, l, l).num;

			r = Query(1, 1, n, r, r).num;

			T.Add(T.root, l, r, 0, 1, k);

			T.Check(T.root, l, r);

		}

	}

}

巴特西

「BZOJ3600」没有人的算术替罪羊树+线段树

题目描述

题解

最新文章

热门文章

巴特西

「BZOJ3600」没有人的算术 替罪羊树+线段树

题目描述

题解

最新文章

热门文章

「BZOJ3600」没有人的算术替罪羊树+线段树