Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

坑爹题，Splay单旋AC，双旋TLE。。

Posted by cz_xuyixuan at 2016-08-11 15:39:06 on Problem 3468

//单旋代码
#include<stdio.h>
#define MAXN	150000
using namespace std;
struct data
{
	long long sum,lazy,left,right,father,value,size;
} tree[MAXN];
long long z,n,q,x,y,i,t,root,total;
char s[2];
void pushup(long long p)
{
	tree[p].size=1+tree[tree[p].left].size+tree[tree[p].right].size;
	tree[p].sum=tree[p].value+tree[tree[p].left].sum+tree[tree[p].right].sum;
}
void pushdown(long long p)
{
	tree[tree[p].left].sum+=tree[p].lazy*tree[tree[p].left].size;
	tree[tree[p].right].sum+=tree[p].lazy*tree[tree[p].right].size;
	tree[tree[p].left].lazy+=tree[p].lazy;
	tree[tree[p].right].lazy+=tree[p].lazy;
	tree[p].value+=tree[p].lazy;
	tree[p].lazy=0;
}
void zig(long long p)
{
	int f=tree[p].father;
	pushdown(f);
	pushdown(p);
	tree[f].left=tree[p].right;
	tree[tree[p].right].father=f;
	tree[p].father=tree[f].father;
	if (tree[f].father!=0)
	{
		if (f==tree[tree[f].father].left) tree[tree[f].father].left=p;
		else tree[tree[f].father].right=p;
	}
	tree[p].right=f;
	tree[f].father=p;
	pushup(f);
	pushup(p);
}
void zag(long long p)
{
	int f=tree[p].father;
	pushdown(f);
	pushdown(p);
	tree[f].right=tree[p].left;
	tree[tree[p].left].father=f;
	tree[p].father=tree[f].father;
	if (tree[f].father!=0)
	{
		if (f==tree[tree[f].father].left) tree[tree[f].father].left=p;
		else tree[tree[f].father].right=p;
	}
	tree[p].left=f;
	tree[f].father=p;
	pushup(f);
	pushup(p);
}
void splay(long long r,long long p)
{
	if (r==p) return;
	while (tree[p].father!=r)
	{
		if (p==tree[tree[p].father].left) zig(p);
		else zag(p);
	}
	if (p==tree[tree[p].father].left) zig(p);
	else zag(p);
	if (r==root) root=p;
}
int maketree(long long x_make,long long y_make,long long f)
{
	if (x_make>y_make) return 0;
	int r=(x_make+y_make)/2;
	tree[r].father=f;
	tree[r].left=maketree(x_make,r-1,r);
	tree[r].right=maketree(r+1,y_make,r);
	pushup(r);
	return r;
}
int main()
{
//	freopen("input.txt", "r", stdin);
	scanf("%I64d%I64d",&n,&q);
	for (i=1;i<=n;i++)
	{
		scanf("%I64d",&tree[i].value);
	}
	root=maketree(1,n,0);
	for (i=1;i<=q;i++)
	{
		scanf("%s",s);
		if (s[0]=='Q')
		{
			scanf("%I64d%I64d",&x,&y);
			if (x==1 and y==n)
			{
				printf("%I64d\n",tree[root].sum);
			}
			if (x==1 and y!=n)
			{
				splay(root,y+1);
				t=tree[root].left;
				printf("%I64d\n",tree[t].sum);
			}
			if (x!=1 and y==n)
			{
				splay(root,x-1);
				t=tree[root].right;
				printf("%I64d\n",tree[t].sum);
			}
			if (x!=1 and y!=n)
			{
				splay(root,x-1);
				t=tree[root].right;
				splay(t,y+1);
				t=tree[root].right;
				t=tree[t].left;
				printf("%I64d\n",tree[t].sum);
			}
		}
		else
		{
			scanf("%I64d%I64d%I64d",&x,&y,&z);
			if (x==1 and y==n)
			{
				tree[root].lazy+=z;
				tree[root].sum+=z*tree[root].size;
			}
			if (x==1 and y!=n)
			{
				splay(root,y+1);
				t=tree[root].left;
				tree[t].lazy+=z;
				tree[t].sum+=z*tree[t].size;
				tree[root].sum+=z*tree[t].size;
			}
			if (x!=1 and y==n)
			{
				splay(root,x-1);
				t=tree[root].right;
				tree[t].lazy+=z;
				tree[t].sum+=z*tree[t].size;
				tree[root].sum+=z*tree[t].size;
			}
			if (x!=1 and y!=n)
			{
				splay(root,x-1);
				t=tree[root].right;
				splay(t,y+1);
				t=tree[root].right;
				t=tree[t].left;
				tree[t].lazy+=z;
				tree[t].sum+=z*tree[t].size;
				tree[tree[root].right].sum+=z*tree[t].size;
				tree[root].sum+=z*tree[t].size;
			}
		}
	}
	return 0;
}
//双旋代码
#include<stdio.h>
#define MAXN	150000
using namespace std;
struct data
{
	long long sum,lazy,left,right,father,value,size;
} tree[MAXN];
long long z,n,q,x,y,i,t,root,total;
char s[2];
void pushup(long long p)
{
	tree[p].size=1+tree[tree[p].left].size+tree[tree[p].right].size;
	tree[p].sum=tree[p].value+tree[tree[p].left].sum+tree[tree[p].right].sum;
}
void pushdown(long long p)
{
	tree[tree[p].left].sum+=tree[p].lazy*tree[tree[p].left].size;
	tree[tree[p].right].sum+=tree[p].lazy*tree[tree[p].right].size;
	tree[tree[p].left].lazy+=tree[p].lazy;
	tree[tree[p].right].lazy+=tree[p].lazy;
	tree[p].value+=tree[p].lazy;
	tree[p].lazy=0;
}
void zig(long long p)
{
	int f=tree[p].father;
	pushdown(f);
	pushdown(p);
	tree[f].left=tree[p].right;
	tree[tree[p].right].father=f;
	tree[p].father=tree[f].father;
	if (tree[f].father!=0)
	{
		if (f==tree[tree[f].father].left) tree[tree[f].father].left=p;
		else tree[tree[f].father].right=p;
	}
	tree[p].right=f;
	tree[f].father=p;
	pushup(f);
	pushup(p);
}
void zag(long long p)
{
	int f=tree[p].father;
	pushdown(f);
	pushdown(p);
	tree[f].right=tree[p].left;
	tree[tree[p].left].father=f;
	tree[p].father=tree[f].father;
	if (tree[f].father!=0)
	{
		if (f==tree[tree[f].father].left) tree[tree[f].father].left=p;
		else tree[tree[f].father].right=p;
	}
	tree[p].left=f;
	tree[f].father=p;
	pushup(f);
	pushup(p);
}
void splay(long long r,long long p)
{
	if (r==p) return;
	while (tree[p].father!=r)
	{
		if (tree[tree[p].father].father!=r)
		{
			if (tree[p].father==tree[tree[tree[p].father].father].left) zig(tree[p].father);
			else zag(tree[p].father);
			if (p==tree[tree[p].father].left) zig(p);
			else zag(p);
		}
		else
		{
			if (p==tree[tree[p].father].left) zig(p);
			else zag(p);
		}
	}
	if (p==tree[tree[p].father].left) zig(p);
	else zag(p);
	if (r==root) root=p;
}
int maketree(long long x_make,long long y_make,long long f)
{
	if (x_make>y_make) return 0;
	int r=(x_make+y_make)/2;
	tree[r].father=f;
	tree[r].left=maketree(x_make,r-1,r);
	tree[r].right=maketree(r+1,y_make,r);
	pushup(r);
	return r;
}
int main()
{
//	freopen("input.txt", "r", stdin);
	scanf("%I64d%I64d",&n,&q);
	for (i=1;i<=n;i++)
	{
		scanf("%I64d",&tree[i].value);
	}
	root=maketree(1,n,0);
	for (i=1;i<=q;i++)
	{
		scanf("%s",s);
		if (s[0]=='Q')
		{
			scanf("%I64d%I64d",&x,&y);
			if (x==1 and y==n)
			{
				printf("%I64d\n",tree[root].sum);
			}
			if (x==1 and y!=n)
			{
				splay(root,y+1);
				t=tree[root].left;
				printf("%I64d\n",tree[t].sum);
			}
			if (x!=1 and y==n)
			{
				splay(root,x-1);
				t=tree[root].right;
				printf("%I64d\n",tree[t].sum);
			}
			if (x!=1 and y!=n)
			{
				splay(root,x-1);
				t=tree[root].right;
				splay(t,y+1);
				t=tree[root].right;
				t=tree[t].left;
				printf("%I64d\n",tree[t].sum);
			}
		}
		else
		{
			scanf("%I64d%I64d%I64d",&x,&y,&z);
			if (x==1 and y==n)
			{
				tree[root].lazy+=z;
				tree[root].sum+=z*tree[root].size;
			}
			if (x==1 and y!=n)
			{
				splay(root,y+1);
				t=tree[root].left;
				tree[t].lazy+=z;
				tree[t].sum+=z*tree[t].size;
				tree[root].sum+=z*tree[t].size;
			}
			if (x!=1 and y==n)
			{
				splay(root,x-1);
				t=tree[root].right;
				tree[t].lazy+=z;
				tree[t].sum+=z*tree[t].size;
				tree[root].sum+=z*tree[t].size;
			}
			if (x!=1 and y!=n)
			{
				splay(root,x-1);
				t=tree[root].right;
				splay(t,y+1);
				t=tree[root].right;
				t=tree[t].left;
				tree[t].lazy+=z;
				tree[t].sum+=z*tree[t].size;
				tree[tree[root].right].sum+=z*tree[t].size;
				tree[root].sum+=z*tree[t].size;
			}
		}
	}
	return 0;
}

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> //单旋代码
> #include<stdio.h>
> #define MAXN	150000
> using namespace std;
> struct data
> {
> 	long long sum,lazy,left,right,father,value,size;
> } tree[MAXN];
> long long z,n,q,x,y,i,t,root,total;
> char s[2];
> void pushup(long long p)
> {
> 	tree[p].size=1+tree[tree[p].left].size+tree[tree[p].right].size;
> 	tree[p].sum=tree[p].value+tree[tree[p].left].sum+tree[tree[p].right].sum;
> }
> void pushdown(long long p)
> {
> 	tree[tree[p].left].sum+=tree[p].lazy*tree[tree[p].left].size;
> 	tree[tree[p].right].sum+=tree[p].lazy*tree[tree[p].right].size;
> 	tree[tree[p].left].lazy+=tree[p].lazy;
> 	tree[tree[p].right].lazy+=tree[p].lazy;
> 	tree[p].value+=tree[p].lazy;
> 	tree[p].lazy=0;
> }
> void zig(long long p)
> {
> 	int f=tree[p].father;
> 	pushdown(f);
> 	pushdown(p);
> 	tree[f].left=tree[p].right;
> 	tree[tree[p].right].father=f;
> 	tree[p].father=tree[f].father;
> 	if (tree[f].father!=0)
> 	{
> 		if (f==tree[tree[f].father].left) tree[tree[f].father].left=p;
> 		else tree[tree[f].father].right=p;
> 	}
> 	tree[p].right=f;
> 	tree[f].father=p;
> 	pushup(f);
> 	pushup(p);
> }
> void zag(long long p)
> {
> 	int f=tree[p].father;
> 	pushdown(f);
> 	pushdown(p);
> 	tree[f].right=tree[p].left;
> 	tree[tree[p].left].father=f;
> 	tree[p].father=tree[f].father;
> 	if (tree[f].father!=0)
> 	{
> 		if (f==tree[tree[f].father].left) tree[tree[f].father].left=p;
> 		else tree[tree[f].father].right=p;
> 	}
> 	tree[p].left=f;
> 	tree[f].father=p;
> 	pushup(f);
> 	pushup(p);
> }
> void splay(long long r,long long p)
> {
> 	if (r==p) return;
> 	while (tree[p].father!=r)
> 	{
> 		if (p==tree[tree[p].father].left) zig(p);
> 		else zag(p);
> 	}
> 	if (p==tree[tree[p].father].left) zig(p);
> 	else zag(p);
> 	if (r==root) root=p;
> }
> int maketree(long long x_make,long long y_make,long long f)
> {
> 	if (x_make>y_make) return 0;
> 	int r=(x_make+y_make)/2;
> 	tree[r].father=f;
> 	tree[r].left=maketree(x_make,r-1,r);
> 	tree[r].right=maketree(r+1,y_make,r);
> 	pushup(r);
> 	return r;
> }
> int main()
> {
> //	freopen("input.txt", "r", stdin);
> 	scanf("%I64d%I64d",&n,&q);
> 	for (i=1;i<=n;i++)
> 	{
> 		scanf("%I64d",&tree[i].value);
> 	}
> 	root=maketree(1,n,0);
> 	for (i=1;i<=q;i++)
> 	{
> 		scanf("%s",s);
> 		if (s[0]=='Q')
> 		{
> 			scanf("%I64d%I64d",&x,&y);
> 			if (x==1 and y==n)
> 			{
> 				printf("%I64d\n",tree[root].sum);
> 			}
> 			if (x==1 and y!=n)
> 			{
> 				splay(root,y+1);
> 				t=tree[root].left;
> 				printf("%I64d\n",tree[t].sum);
> 			}
> 			if (x!=1 and y==n)
> 			{
> 				splay(root,x-1);
> 				t=tree[root].right;
> 				printf("%I64d\n",tree[t].sum);
> 			}
> 			if (x!=1 and y!=n)
> 			{
> 				splay(root,x-1);
> 				t=tree[root].right;
> 				splay(t,y+1);
> 				t=tree[root].right;
> 				t=tree[t].left;
> 				printf("%I64d\n",tree[t].sum);
> 			}
> 		}
> 		else
> 		{
> 			scanf("%I64d%I64d%I64d",&x,&y,&z);
> 			if (x==1 and y==n)
> 			{
> 				tree[root].lazy+=z;
> 				tree[root].sum+=z*tree[root].size;
> 			}
> 			if (x==1 and y!=n)
> 			{
> 				splay(root,y+1);
> 				t=tree[root].left;
> 				tree[t].lazy+=z;
> 				tree[t].sum+=z*tree[t].size;
> 				tree[root].sum+=z*tree[t].size;
> 			}
> 			if (x!=1 and y==n)
> 			{
> 				splay(root,x-1);
> 				t=tree[root].right;
> 				tree[t].lazy+=z;
> 				tree[t].sum+=z*tree[t].size;
> 				tree[root].sum+=z*tree[t].size;
> 			}
> 			if (x!=1 and y!=n)
> 			{
> 				splay(root,x-1);
> 				t=tree[root].right;
> 				splay(t,y+1);
> 				t=tree[root].right;
> 				t=tree[t].left;
> 				tree[t].lazy+=z;
> 				tree[t].sum+=z*tree[t].size;
> 				tree[tree[root].right].sum+=z*tree[t].size;
> 				tree[root].sum+=z*tree[t].size;
> 			}
> 		}
> 	}
> 	return 0;
> }
> //双旋代码
> #include<stdio.h>
> #define MAXN	150000
> using namespace std;
> struct data
> {
> 	long long sum,lazy,left,right,father,value,size;
> } tree[MAXN];
> long long z,n,q,x,y,i,t,root,total;
> char s[2];
> void pushup(long long p)
> {
> 	tree[p].size=1+tree[tree[p].left].size+tree[tree[p].right].size;
> 	tree[p].sum=tree[p].value+tree[tree[p].left].sum+tree[tree[p].right].sum;
> }
> void pushdown(long long p)
> {
> 	tree[tree[p].left].sum+=tree[p].lazy*tree[tree[p].left].size;
> 	tree[tree[p].right].sum+=tree[p].lazy*tree[tree[p].right].size;
> 	tree[tree[p].left].lazy+=tree[p].lazy;
> 	tree[tree[p].right].lazy+=tree[p].lazy;
> 	tree[p].value+=tree[p].lazy;
> 	tree[p].lazy=0;
> }
> void zig(long long p)
> {
> 	int f=tree[p].father;
> 	pushdown(f);
> 	pushdown(p);
> 	tree[f].left=tree[p].right;
> 	tree[tree[p].right].father=f;
> 	tree[p].father=tree[f].father;
> 	if (tree[f].father!=0)
> 	{
> 		if (f==tree[tree[f].father].left) tree[tree[f].father].left=p;
> 		else tree[tree[f].father].right=p;
> 	}
> 	tree[p].right=f;
> 	tree[f].father=p;
> 	pushup(f);
> 	pushup(p);
> }
> void zag(long long p)
> {
> 	int f=tree[p].father;
> 	pushdown(f);
> 	pushdown(p);
> 	tree[f].right=tree[p].left;
> 	tree[tree[p].left].father=f;
> 	tree[p].father=tree[f].father;
> 	if (tree[f].father!=0)
> 	{
> 		if (f==tree[tree[f].father].left) tree[tree[f].father].left=p;
> 		else tree[tree[f].father].right=p;
> 	}
> 	tree[p].left=f;
> 	tree[f].father=p;
> 	pushup(f);
> 	pushup(p);
> }
> void splay(long long r,long long p)
> {
> 	if (r==p) return;
> 	while (tree[p].father!=r)
> 	{
> 		if (tree[tree[p].father].father!=r)
> 		{
> 			if (tree[p].father==tree[tree[tree[p].father].father].left) zig(tree[p].father);
> 			else zag(tree[p].father);
> 			if (p==tree[tree[p].father].left) zig(p);
> 			else zag(p);
> 		}
> 		else
> 		{
> 			if (p==tree[tree[p].father].left) zig(p);
> 			else zag(p);
> 		}
> 	}
> 	if (p==tree[tree[p].father].left) zig(p);
> 	else zag(p);
> 	if (r==root) root=p;
> }
> int maketree(long long x_make,long long y_make,long long f)
> {
> 	if (x_make>y_make) return 0;
> 	int r=(x_make+y_make)/2;
> 	tree[r].father=f;
> 	tree[r].left=maketree(x_make,r-1,r);
> 	tree[r].right=maketree(r+1,y_make,r);
> 	pushup(r);
> 	return r;
> }
> int main()
> {
> //	freopen("input.txt", "r", stdin);
> 	scanf("%I64d%I64d",&n,&q);
> 	for (i=1;i<=n;i++)
> 	{
> 		scanf("%I64d",&tree[i].value);
> 	}
> 	root=maketree(1,n,0);
> 	for (i=1;i<=q;i++)
> 	{
> 		scanf("%s",s);
> 		if (s[0]=='Q')
> 		{
> 			scanf("%I64d%I64d",&x,&y);
> 			if (x==1 and y==n)
> 			{
> 				printf("%I64d\n",tree[root].sum);
> 			}
> 			if (x==1 and y!=n)
> 			{
> 				splay(root,y+1);
> 				t=tree[root].left;
> 				printf("%I64d\n",tree[t].sum);
> 			}
> 			if (x!=1 and y==n)
> 			{
> 				splay(root,x-1);
> 				t=tree[root].right;
> 				printf("%I64d\n",tree[t].sum);
> 			}
> 			if (x!=1 and y!=n)
> 			{
> 				splay(root,x-1);
> 				t=tree[root].right;
> 				splay(t,y+1);
> 				t=tree[root].right;
> 				t=tree[t].left;
> 				printf("%I64d\n",tree[t].sum);
> 			}
> 		}
> 		else
> 		{
> 			scanf("%I64d%I64d%I64d",&x,&y,&z);
> 			if (x==1 and y==n)
> 			{
> 				tree[root].lazy+=z;
> 				tree[root].sum+=z*tree[root].size;
> 			}
> 			if (x==1 and y!=n)
> 			{
> 				splay(root,y+1);
> 				t=tree[root].left;
> 				tree[t].lazy+=z;
> 				tree[t].sum+=z*tree[t].size;
> 				tree[root].sum+=z*tree[t].size;
> 			}
> 			if (x!=1 and y==n)
> 			{
> 				splay(root,x-1);
> 				t=tree[root].right;
> 				tree[t].lazy+=z;
> 				tree[t].sum+=z*tree[t].size;
> 				tree[root].sum+=z*tree[t].size;
> 			}
> 			if (x!=1 and y!=n)
> 			{
> 				splay(root,x-1);
> 				t=tree[root].right;
> 				splay(t,y+1);
> 				t=tree[root].right;
> 				t=tree[t].left;
> 				tree[t].lazy+=z;
> 				tree[t].sum+=z*tree[t].size;
> 				tree[tree[root].right].sum+=z*tree[t].size;
> 				tree[root].sum+=z*tree[t].size;
> 			}
> 		}
> 	}
> 	return 0;
> }

Home Page Go Back To top