#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<iostream>
using namespace std;
inline int maxx(int a,int b){return a>b?a:b;}
inline int minn(int a,int b){return a<b?a:b;}
inline void swap(int &a,int &b){int tt=a; a=b; b=tt; return;}
#define oo 1000000000
#define maxn 200010
struct node{
				int lc,rc,fa,d,sum,min_num,late,rev;
				#define lc(x) tr[x].lc
				#define rc(x) tr[x].rc
				#define fa(x) tr[x].fa
				#define d(x) tr[x].d
				#define sum(x) tr[x].sum
				#define min_num(x) tr[x].min_num
				#define late(x) tr[x].late
				#define rev(x) tr[x].rev
			}tr[maxn];
int n,m,s[maxn],s_head,s_tail,total,root;
inline void clear(int p)
{
	lc(p)=rc(p)=fa(p)=d(p)=sum(p)=min_num(p)=late(p)=rev(p)=0;
	return;
}
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 (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;
	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);
	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)
{
	while (lc(x)) x=lc(x);
	return x;
}
inline int find_right(int x)
{
	while (rc(x)) x=rc(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; 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;
	if (x>y) swap(x,y);
	x=find(root,x); y=find(root,y);
	if (x>0) splay(x,0); if (y<=sum(root)) splay(y,x);
	if (y<=sum(root)) p=lc(y);
	else if (x>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%=(y-x-1); if (z==0) return;
		if (z<0) w=z+1; else w=y-x-1-z+1;
		d=find(p,w);
		if (y<=sum(root)) splay(d,y);
		else if (x>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;
}
int main()
{
	freopen("poj3580.in","r",stdin); freopen("poj3580.out","w",stdout);
	int i,j,x,y,z; char ch[10];
	memset(tr,0,sizeof(tr)); total=0; s_head=s_tail=1; memset(s,0,sizeof(s));
	scanf("%d",&n); getchar();
	for (i=1; i<=n; i++)
	{
		scanf("%d",&x); getchar();
		ins(i-1,x);
	}
	scanf("%d",&m); getchar();
	for (i=1; i<=m; i++)
	{
		scanf("%s",ch);
		if (strcmp(ch,"ADD")==0)
		{
			scanf("%d%d%d",&x,&y,&z); work(1,x-1,y+1,z);
		}
		else if (strcmp(ch,"REVERSE")==0)
		{
			scanf("%d%d",&x,&y); work(2,x-1,y+1,0);
		}
		else if (strcmp(ch,"REVOLVE")==0)
		{
			scanf("%d%d%d",&x,&y,&z); work(3,x-1,y+1,z);
		}
		else if (strcmp(ch,"MIN")==0)
		{
			scanf("%d%d",&x,&y); work(4,x-1,y+1,0);
		}
		else if (strcmp(ch,"INSERT")==0)
		{
			scanf("%d%d",&x,&y); ins(x,y);
		}
		else
		{
			scanf("%d",&x); work(5,x-1,x+1,0);
		}
		getchar();
	}
	return 0;
}

• Re:splay写了几天了，依然TLE 求各路神牛帮忙（代码个人觉得还挺精简的，求帮忙）！T-T (5185) shuaige123 2012-09-05 13:52:42
  • 求各位路过神牛帮忙 (0) shuaige123 2012-09-05 13:53:09
  • 精诚所至金石为开，发帖向路过的大牛们求救! T-T (0) shuaige123 2012-09-05 16:34:53
  • 求感动大牛! 另附我最新的代码 (4812) shuaige123 2012-09-05 18:39:36
  • 精诚所至，金石为开，求各位路过神牛帮忙! (0) shuaige123 2012-09-06 13:38:02
  • Re:splay写了几天了，依然TLE 求各路神牛帮忙（代码个人觉得还挺精简的，求帮忙）！T-T (0) 20181gdgzoi236 2019-01-18 11:21:53
• 虽然没人帮我，但我终于A了 (3236) shuaige123 2012-09-06 16:53:01
  • Re:虽然没人帮我，但我终于A了 (22) xcszbdnl 2014-03-30 14:23:07
    • Re:虽然没人帮我，但我终于A了 (28) 20181gdgzoi236 2019-01-18 11:22:23