这是一道站外题（POJ2828买票）

大概就是不断的在第 $i$ 个数前插入新值，求最终的序列。

写了个 splay，在插入时有问题。

参考tj发现需要写一个 build 函数

void build(int &p,int l,int r,int fa){
	if(l>r)return;
	int mid=l+r>>1;
	p=++idx;
	tr[p].init(-1,fa);
	build(tr[p].son[0],l,mid-1,p);build(tr[p].son[1],mid+1,r,p);
	pushup(p);
}

请问这个 build 有什么作用？为什么不加就会陷入循环？

完整代码

#include <bits/stdc++.h>
using namespace std;

int n,root,idx;
struct node{
	int son[2],fa,siz,v;
	void init(int _v,int _fa){
		v=_v;fa=_fa,siz=1;
	}
}tr[200005];
void pushup(int p){tr[p].siz=tr[tr[p].son[0]].siz+tr[tr[p].son[1]].siz+1;}
void rotate(int x){
	int y=tr[x].fa,z=tr[y].fa;
	int k=tr[y].son[1]==x;
	tr[z].son[tr[z].son[1]==y]=x,tr[x].fa=z;
	tr[y].son[k]=tr[x].son[k^1],tr[tr[x].son[k^1]].fa=y;
	tr[x].son[k^1]=y,tr[y].fa=x;
	pushup(y);pushup(x);
}
void splay(int x,int goal){
	while(tr[x].fa!=goal){
		int y=tr[x].fa,z=tr[y].fa;
		if(z!=goal){
			if(tr[y].son[1]==x ^ tr[z].son[1]==y)rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	if(!goal)root=x;
}
int get(int k){
	int p=root;
	while(true){
		if(tr[tr[p].son[0]].siz>=k)p=tr[p].son[0];
		else if(tr[tr[p].son[0]].siz+1==k)return p;
		else k-=tr[tr[p].son[0]].siz+1,p=tr[p].son[1];
	}
}
void insert(int rk,int v){
	int L=get(rk),R=get(rk+1);
	splay(L,0);splay(R,L);
	tr[R].son[0]=++idx;
	tr[idx].init(v,R);
	pushup(R);pushup(L);
}
void print(int p){
	if(tr[p].son[0])print(tr[p].son[0]);
	if(tr[p].v!=-1)printf("%d ",tr[p].v);
	if(tr[p].son[1])print(tr[p].son[1]);
}

void build(int &p,int l,int r,int fa){
	if(l>r)return;
	int mid=l+r>>1;
	p=++idx;
	tr[p].init(-1,fa);
	build(tr[p].son[0],l,mid-1,p);build(tr[p].son[1],mid+1,r,p);
	pushup(p);
}

int main(){
	scanf("%d",&n);
//	root=1;
//	tr[root].init(-1,0);
//	tr[root].son[0]=++idx;tr[idx].init(-1,root);
//	tr[root].son[1]=++idx;tr[idx].init(-1,root);
//	pushup(root);
	build(root,1,2,0);
	while(n--){
		int x,y;scanf("%d%d",&x,&y);
		insert(++x,y);
	}
	print(root);
}