第一天

上午

讲了数据结构

平衡树（Treap）

随机的笛卡尔树的期望深度是 \(log_{n}\)。

合并

合并以 \(x,y\) 为根的 \(Treap\) 过程

若 \(x,y\) 有一个为空，则返回另一个

比较 \(x,y\) 的随机权值

若 \(x<y\) 则递归合并 \(x\) 的左儿子 和 \(y\)。

否则返回 \(x\) 和 \(y\) 的右儿子。

int merge(int x,int y){
	if(!x||!y)return x|y;
	pushdown(x),pushdown(y) ;
	if(d[x].rnd<d[y].rnd){
		d[x].rs=merge(d[x].rs,y);
		update(x);
		return x;
	}else{
		d[y].ls=merge(x,d[y].ls);
		update(y);
		return y;
	}
} 

分裂

具体看代码

void split(int u,int k,int &x,int &y){
	pushdown(u);
	if(!k){
		x=0;
		y=u;
		return;
	}else{
		if(k==d[u].sz){
			x=u,y=0;
			return ;
		}
	}
	if(k<=d[d[u].ls].sz){
		split(d[u].ls,k,x,d[u].ls);
		y=u;
	}else{
		split(d[u].rs,k-d[d[u].ls].sz-1,d[u].rs,y);
		x=u;
	}
	update(u);
} 

分块

一种通用，直观，效率偏低，码长一般的思想。

莫队

先不讲了，之后可能会补上。

下午

讲题