[bzoj 3600] 没有人的算术

定义:

是一个数; 如果是数, 那么也是数

给一个长度为的全序列 , 个操作:

赋值给出参数 , 执行
询问给出参数 , 求最大值的下标; 多个最大值, 输出最小下标.

如果能快速比较两个数的大小, 上个线段树就能解决问题了. 可不可以把这些数映射到我们熟悉的对象? 自然数? 实数? 字符串? 能不能在暴力比较的过程中加个记忆化? 并查集? 从图论的角度考虑? 构造一个新数总是用两个已经存在的对象. 离线之后拓扑排序?

思路一度很靠近正解......正是要把它们映射到整数/实数. 我否定了这一想法, 似乎是因为, 不知如何赋一个满足所有大小关系的值.

我们定义出来的是一个全序集. 每产生一个新的数, 就把它扔进平衡树. 新数总是由两个已经存在的数构造而来, 而已经存在的数, 两两之间的大小关系是已知的 (比较它们的rank即可). 得到了一个插入和比较均为的算法.

能不能把思路拓宽一点呢? 把每个对象映射到一个实数, 这样, 比较就是的了. 为了保证精度, 我们不能简单地取前驱和后继之间的一个数, 而采取这样的做法: 把每个节点对应到一个开区间 , 根对应 . 该节点表示的数映射到 , 左儿子对应到 , 右儿子对应到 . 树高为 , 则最深的一层对精度的要求为 . 如果我们用平衡树, , 可以接受.

但是, 又引入了一个新的问题. 平衡树为了保持平衡, 会调整形态, 从而引起一系列重新赋值. 我们使用重量平衡树: 每次操作影响的最大子树的大小是最坏或者均摊或者期望的. 以下代码是替罪羊树, 通过取 , 保证深度不超过28, 用int代替了double.

总结一下......由某个集合上的一个偏序得到该集合上的一个全序, 可以用拓扑排序. 如果我们已经有一个全序集了, 可以用一棵重量平衡树把每个对象映射到一个实数, 实现比较.

这个思路对我来说还是挺新颖的......没有往二分查找这个方向想.

// do not `using namespacae std`

#define ALL 1, 1, n
#define LEFT o*2, l, m
#define RIGHT o*2+1, m+1, r

typedef std::pair<int, int> P;

const int N = 1e5 + 1, V = 3e5;

int val[V] = {-1}, left[V], right[V];

struct Scopegoat
{
	static const double alpha = 0.65, base = 0.43078291609245417;

	bool flag;
	int ptr, top, root, seq[V], lc[V], rc[V], sz[V];

	int insert(int lv, int rv)
	{
		int t = insert(root, P(lv, rv), 0, 1<<30, 0);
		return t;
	}
	
	int insert(int& o, const P& v, int l, int r, int h)
	{
		int m = l + (r-l)/2;
		if (o)
		{
			P x(val[left[o]], val[right[o]]);
			if (x == v) return o;
			int t = v < x ? insert(lc[o], v, l, m, h+1) : insert(rc[o], v, m, r, h+1);
			sz[o] = 1 + sz[lc[o]] + sz[rc[o]];
			if (flag && std::max(sz[lc[o]], sz[rc[o]]) > sz[o] * alpha)
				flag = false, rebuild(o, l, r);
			return t;
		}
		else
		{
			o = ++ptr;
			sz[o] = 1;
			val[o] = m;
			flag = h*base > log(ptr);
			return o;
		}
	}

	void dfs(int o)
	{
		if (!o) return;
		dfs(lc[o]);
		seq[top++] = o;
		dfs(rc[o]);
	}

	void build(int& o, int* s, int n, int l, int r)
	{
		if (!n) return o = 0, void();
		int t = n/2, m = l + (r-l)/2;
		val[o = s[t]] = m;
		sz[o] = n;
		build(lc[o], s, t, l, m);
		build(rc[o], s+t+1, n-1-t, m, r);
	}

	void rebuild(int& o, int l, int r)
	{
		top = 0;
		dfs(o);
		build(o, seq, top, l, r);
	}
} S;

int num[N];

struct Seg
{
	int mx[N*4];

	int Max(int i, int j)
	{
		int vi = val[num[i]], vj = val[num[j]];
		return vi > vj || (vi == vj && i < j) ? i : j;
	}
	
	void modify(int x, int o, int l, int r)
	{
		if (l == r) return;
		int m = (l+r)/2;
		if (x <= m) modify(x, LEFT);
		else modify(x, RIGHT);
		mx[o] = Max(mx[o*2], mx[o*2+1]);
	}

	int query(int L, int R, int o, int l, int r)
	{
		if (L <= l && r <= R) return mx[o];
		int m = (l+r)/2;
		if (R <= m) return query(L, R, LEFT);
		if (L > m) return query(L, R, RIGHT);
		return Max(query(L, R, LEFT), query(L, R, RIGHT));
	}

	void build(int o, int l, int r)
	{
		mx[o] = l;
		if (l == r) return;
		int m = (l+r)/2;
		build(LEFT);
		build(RIGHT);
	}
} T;

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	int t = S.insert(-1, -1);
	rep (i, 1, n+1) num[i] = t;
	T.build(ALL);
	while (m--)
	{
		char o;
		int l, r, k;
		scanf(" %c%d%d", &o, &l, &r);
		if (o == 'C')
		{
			scanf("%d", &k);
			l = num[l], r = num[r];
			num[k] = S.insert(val[l], val[r]);
			left[num[k]] = l, right[num[k]] = r;
			T.modify(k, ALL);
		}
		else
		{
			printf("%d\n", T.query(l, r, ALL));
		}
	}
	return 0;
}