1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108

template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
template<typename T,int size>
struct QUE
{
	T ary[size+1];
	int f,t,cnt;
	void clear(){f=t=cnt=0;}
	bool empty(){return cnt==0;}
	void push(const T& w)
	{
		ary[t++]=w,++cnt;
		if(t==size)t=0;
	}
	void pop(){++f,--cnt;if(f==size)f=0;}
	T front(){return ary[f];}
};
template<typename T,int size,bool comp(const T& a,const T& b)>
struct LTREE
{
	T v[size+1];
	int l[size+1],r[size+1];
	int d[size+1];
	int f[size+1];
	QUE<int,size> id;
	int t;
	void clear()
	{
		t=0;
		id.clear();
		memset(v,0,(n+1)*sizeof(int));
		memset(l,0,(n+1)*sizeof(int));
		memset(r,0,(n+1)*sizeof(int));
		memset(d,0,(n+1)*sizeof(int));
		memset(f,0,(n+1)*sizeof(int));
		d[0]=-1;
	}
	void update(int x)
	{
		//...
	}
	int merge(int x,int y)//merge y to x
	{
		if(x==y)return x;
		if(!x)return y;
		if(!y)return x;
		if(comp(v[y],v[x]))Swap(x,y);
		r[x]=merge(r[x],y);
		f[r[x]]=x;
		update(x);
		if(d[l[x]]<d[r[x]])Swap(l[x],r[x]);	
		//if(r[x])
		d[x]=d[r[x]]+1;
		//else d[x]=0;
		return x;
	}
	int pop(int x)// x must be a root
	{
		f[l[x]]=l[x],f[r[x]]=r[x];
		id.push(x);
		return merge(l[x],r[x]);
	}
	int findf(int x)
	{
		if(x==f[x])return x;
		else return findf(f[x]);
	}
	int push(int x,const T& w)
	{
		x=findf(x);
		int now;
		if(!q.empty())now=q.front();
		else now=++t;
		v[now]=w;
		f[now]=now;
		l[now]=r[now]=d[now]=0;
		return merge(x,now);
	}
	void balance(int x)//from x to  top
	{
		if(d[l[x]]<d[r[x]])Swap(l[x],r[x]);
		if(d[x]!=d[r[x]]+1&&f[x]!=x)
			d[x]=d[r[x]]+1,balance(f[x]);
	}
	void del(int x)
	{
		int fa=f[x];
		int son=merge(l[x],r[x]);		
		if(r[fa]==x)r[fa]=son;
		if(l[fa]==x)l[fa]=son;
		f[son]=fa;
		balance(fa);
	}
	void makeTree(int* ary,int n)//used queue in O(n)
	{
		static QUE<int,size> q;
		q.clear();
		for(int i=1;i<=n;++i)
			q.push(add(ary[i]));
		while(q.cnt!=1)
		{
			int t1=q.front();q.pop();
			int t2=q.front();q.pop();
			q.push(merge(t1,t2));
		}
		//need to be completed
	}
};