inline void updata(int x)
{
	sum(x)=sum(lc(x))+sum(rc(x))+1;
	min_num(x)=d(x);
	if (lc(x)) min_num(x)=minn(min_num(x),min_num(lc(x)));
	if (rc(x)) min_num(x)=minn(min_num(x),min_num(rc(x)));
	return;
}
inline void l_rotate(int x)
{
	int y,z; y=fa(x); z=fa(y);
	if (lc(z)==y) lc(z)=x;
	else if (rc(z)==y) rc(z)=x;
	fa(x)=z; rc(y)=lc(x); fa(lc(x))=y; lc(x)=y; fa(y)=x;
	if (!fa(x)) root=x;
	updata(y);
	return;
}
inline void r_rotate(int x)
{
	int y,z; y=fa(x); z=fa(y);
	if (lc(z)==y) lc(z)=x;
	else if (rc(z)==y) rc(z)=x;
	fa(x)=z; lc(y)=rc(x); fa(rc(x))=y; rc(x)=y; fa(y)=x;
	if (!fa(x)) root=x;
	updata(y);
}
inline void add(int x,int y)
{
	d(x)+=y; min_num(x)+=y; late(x)+=y;
	return;
}
inline void put(int x)
{
	rev(x)=!rev(x);
	swap(lc(x),rc(x));
	return;
}
inline void push(int x)
{
	if (x==0) return;
	if (late(x)) add(lc(x),late(x)),add(rc(x),late(x)),late(x)=0;
	if (rev(x)) put(lc(x)),put(rc(x)),rev(x)=0;
	return;
}
inline void splay(int x,int goal)
{
	if (!x) return;
	int y,z; y=fa(x); z=fa(y);
	push(z); push(y); push(x);
	while (fa(x)!=goal)
	{
		y=fa(x); z=fa(y);
		push(z); push(y); push(x);
		if (fa(y)==goal)
		{
			if (lc(y)==x) r_rotate(x);
			else l_rotate(x);
		}
		else
		{
			if (lc(z)==y)
			{
				if (lc(y)==x) r_rotate(y),r_rotate(x);
				else l_rotate(x),r_rotate(x);
			}
			else
			{
				if (lc(y)==x) r_rotate(x),l_rotate(x);
				else l_rotate(y),l_rotate(x);
			}
		}
	}
	if (!goal) root=x;
	updata(x);
	return;
}
inline int find(int now,int x)
{
	clear(0); push(now);
	if (x<1) return 0;
	if (x>sum(now)) return sum(now)+1;
	if (sum(lc(now))>=x) return find(lc(now),x);
	else if (sum(lc(now))+1==x) return now;
	else return find(rc(now),x-sum(lc(now))-1);
}
inline int find_left(int x)
{
	push(x);
	while (lc(x)){
		x=lc(x);
		push(x);
	}
	return x;
}
inline int find_right(int x)
{
	push(x);
	while (rc(x)){
		x=rc(x);
		push(x);
	}
	return x;
}
inline void ins(int w,int x)
{
	int i,j,p;
	w=find(root,w);
	splay(w,0);
	if (s_head!=s_tail) p=s[s_head++];
	else p=++total;
	if (s_head>=maxn) s_head=1;
	d(p)=x; updata(p);
	if (!w)
	{
		rc(p)=root; fa(root)=p; root=p;
	}
	else
	{
		if (!rc(w)) rc(w)=p,fa(p)=w;
		else
		{
			w=rc(w); w=find_left(w); lc(w)=p; fa(p)=w;
		}
	}
	splay(p,0);
	return;
}
inline void work(int type,int x,int y,int z)
{
	int i,j,d,f,g,p,w,len=y-x-1,xx=x,yy=y;
	if (x>y) swap(x,y);
	if (x>0){
		x=find(root,x);
		splay(x,0);
	}
	if (y<=sum(root)){
		y=find(root,y);
		splay(y,x);
	}
	if (yy<=sum(root)) p=lc(y);
	else if (xx>0) p=rc(x);
	else p=root;
	if (type==1) add(p,z),splay(p,0);
	else if (type==2) put(p);
	else if (type==3)
	{
		z%=len; if (z==0) return;
		if (z<0) w=z+1; else w=len-z+1;
		d=find(p,w);
		if (yy<=sum(root)) splay(d,y);
		else if (xx>0) splay(d,x);
		else splay(d,0);
		f=lc(d); fa(lc(d))=0; lc(d)=0; updata(d);
		g=find_right(d); rc(g)=f; fa(f)=g; updata(g); splay(f,0);
	}
	else if (type==4) printf("%d\n",min_num(p));
	else
	{
		if (lc(fa(p))==p) lc(fa(p))=0;
		else rc(fa(p))=0;
		updata(fa(p)); splay(fa(p),0);
		clear(p);
		s[s_tail++]=p; if (s_tail>=maxn) s_tail=1;
	}
	return;
}

• Re:虽然没人帮我，但我终于A了 (22) xcszbdnl 2014-03-30 14:23:07
  • Re:虽然没人帮我，但我终于A了 (28) 20181gdgzoi236 2019-01-18 11:22:23