> #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;
> }

• 求各位路过神牛帮忙 (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