「bzoj3600」没有人的算术 - 替罪羊树+实数区间+线段树

题目大意

    定义$0$是最小的数，定义一个二元组$(a,b)$为一个数，定义两个数的大小关系是先按照第一关键字比较，后按照第二关键字比较。
    数可以进行复合，即可以将$(a,b)$，$(c,d)$复合为一个数$((a,b),(c,d))$，大小关系同样进行嵌套。
    修改一个数为已有两个数的复合，询问一段区间的最大值。

---

题目分析

我们要快速比较两个数的大小关系。
因为数进行了嵌套，故比较这两个数需要先比较内部的数大小，这样的复杂度是不能接受的。

不妨使用陈立杰论文中的方法，将每个数对应一个映射插入到平衡树中，每次插入到平衡树中就对它添加一个映射。

这样我们每次的插入，其内部嵌套的两个数和其他数的大小关系已经知道，我们就可以插入到平衡树中。同样的，我们有了表示大小关系的映射值，就可以建立线段树维护最大值了。

这个映射称为实数区间，每个结点对应一个实数区间，如图：

每个点的数（实数区间中点的值）即为我们使用的映射的值，平衡树的中序遍历有序，故映射的值就可以表示其大小关系。

一个节点的左儿子实数区间为$[l,mid]$，右儿子为$[mid,r]$，故我们可以在插入后维护实数区间。

下面来说明一些东西：

为何替罪羊树重构后不需要更新线段树

因为我们插入一个数才会引起重构，因此无论重构与否，原来的值的大小关系不变，而只有原来的数和现在的数大小关系不同。
而我们在线段树上插入新点的时候，更新了路径上最大值与它的关系，故无需更新线段树，因为更新不会影响任何值的大小关系。

为何不能用Splay维护

替罪羊树显然可以维护，treap也可以维护（因为重量平衡，每次旋转后暴力更新子树的实数区间）。
Splay不能维护的原因不仅仅是深度过大精度不够的问题：

如图，因为旋转后实数区间变了，和原来的映射不再对应，因此新插入的点不满足平衡树性质，故不能使用Splay维护。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=500005;

int n,m,pos[maxn],_pos;
double Val[maxn],posl,posr;

struct Data {
	int l,r;
	bool operator < (const Data& y) const {
		return Val[l]<Val[y.l]||(Val[l]==Val[y.l]&&Val[r]<Val[y.r]);
	}
	bool operator == (const Data& y) const {
		return Val[l]==Val[y.l]&&Val[r]==Val[y.r];
	}
};

struct Tree {
	int child[2],father;
	int size;
	Data val;
};
 
struct ScapeGoat_Tree {
	Tree tree[maxn];
	int root,size;
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define fa(x) tree[x].father
#define val(x) tree[x].val
#define size(x) tree[x].size
	bool balance(int index) {
		return size(index)*0.7>=max(size(ls(index)),size(rs(index)));
	}
	bool checkson(int index) {
		return rs(fa(index))==index;
	}
	void push_up(int index) {
		size(index)=size(ls(index))+1+size(rs(index));
	}
	int cnt,a[maxn];
	void dfs(int index) {
		if(ls(index))dfs(ls(index));
		a[++cnt]=index;
		if(rs(index))dfs(rs(index));
	}
	int build(int Left,int Right,double left,double right) {
		if(Left>Right)return 0;
		int mid=(Left+Right)>>1,pos=a[mid];
		double midv=(left+right)/2;
		Val[pos]=midv;
		ls(pos)=build(Left,mid-1,left,midv);
		rs(pos)=build(mid+1,Right,midv,right);
		fa(ls(pos))=fa(rs(pos))=pos;
		push_up(pos);
		return pos;
	}
	void rebuild(int index,double left,double right) {
		cnt=0;
		dfs(index);
		int father=fa(index),side=checkson(index);
		int pos=build(1,cnt,left,right);
		tree[father].child[side]=pos;
		fa(pos)=father;
		if(index==root)root=pos;
	}
	int insert(int &index,double left,double right,Data val) {
		double midv=(left+right)/2;
		if(!index) {
			index=++size;
			val(index)=val;
			Val[index]=midv;
			size(index)=1;
			return index;
		}
		int tmp;
		if(val==val(index))return index;
		else {
			size(index)++;
			if(val<val(index))tmp=insert(ls(index),left,midv,val);
			else tmp=insert(rs(index),midv,right,val);
			fa(ls(index))=fa(rs(index))=index;
		}
		if(!balance(index)) {
			_pos=index;
			posl=left;
			posr=right;
		}
		return tmp;
	}
} sgt;

struct Tree2 {
	int left,right,max;
};

struct Segment_Tree {
	Tree2 tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
	void push_up(int index) {
		int x=tree[ls].max,y=tree[rs].max;
		if(Val[pos[x]]<Val[pos[y]])tree[index].max=y;
		else tree[index].max=x;
	}
	void build(int index,int Left,int Right) {
		tree[index].left=Left,tree[index].right=Right;
		if(Left==Right) {
			tree[index].max=Left;
			return;
		}
		int mid=(Left+Right)>>1;
		build(ls,Left,mid);
		build(rs,mid+1,Right);
		push_up(index);
	}
	void update(int index,int target) {
		if(target<tree[index].left||target>tree[index].right)return;
		if(tree[index].left==tree[index].right) {
			tree[index].max=tree[index].left;
			return;
		}
		update(ls,target);
		update(rs,target);
		push_up(index);
	}
	int query(int index,int Left,int Right) {
		if(Right<tree[index].left||Left>tree[index].right)return 0;
		if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].max;
		int x=query(ls,Left,Right),y=query(rs,Left,Right);
		if(Val[pos[x]]<Val[pos[y]])return y;
		return x;
	}
} st;

int main() {
	n=Get_Int();
	m=Get_Int();
	Val[0]=-1;
	sgt.insert(sgt.root,0,1,(Data) {0,0});
	for(int i=1; i<=n; i++)pos[i]=1;
	st.build(1,1,n);
	for(int i=1; i<=m; i++) {
		char opt=' ';
		while(!isalpha(opt))opt=getchar();
		int x=Get_Int(),y=Get_Int();
		if(opt=='C') {
			int k=Get_Int();
			_pos=0;
			pos[k]=sgt.insert(sgt.root,0,1,(Data) {pos[x],pos[y]});
			if(_pos)sgt.rebuild(_pos,posl,posr);
			st.update(1,k);
		} else printf("%d\n",st.query(1,x,y)); 
	}
	return 0;
}