【poj3580】 SuperMemo

编程知识行业动态更新时间:2024-06-13 00:20:03

Description

Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, {A_{1, A_{2, ... An}. Then the host performs a series of operations and queries on the sequence which consists:}}

ADD x y D: Add D to each number in sub-sequence {Ax ... Ay}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
REVERSE x y: reverse the sub-sequence {Ax ... Ay}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
REVOLVE x y T: rotate sub-sequence {Ax ... Ay} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
INSERT x P: insert P after Ax. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
DELETE x: delete Ax. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
MIN x y: query the participant what is the minimum number in sub-sequence {Ax ... Ay}. For example, the correct answer to "MIN 2 4" on {1, 2, 3, 4, 5} is 2

To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

Input

The first line contains n (n ≤ 100000).

The following n lines describe the sequence.

Then follows M (M ≤ 100000), the numbers of operations and queries.

The following M lines describe the operations and queries.

Output

For each "MIN" query, output the correct answer.

Sample Input

Sample Output

初学splay~~感觉身体被掏空辣鸡splay 毁我青春~~ 这是splay的模板题，但是非常BT，所以磨了将近10个小时才搞定。参考学习了大神cxlove的写法orzorzorz%。网址：http://blog.csdn/acm_cxlove/article/details/7803646
splay+线段树的结构坑死人，记得处处都要pushup和pushdown。而且最好不要手残（像我）。找问题会找到疯。
revolve操作比较坑，可以理解为区间[a,b]经过转换变成区间[c,b]+[a,c-1],c大小可以通过计算得出。剩下看代码吧。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define key_root ch[ch[root][1]][0]
#define M 400050
#define inf 2000000000
using namespace std;
int pre[M],size[M],rev[M],key[M];
int ch[M][2],m[M],add[M];
int a[M];
int tot,root,n;
void pr(int r)
{
	if(r==0)return;
	pr(ch[r][0]);
	cout<<r<<" "<<key[r]<<" "<<ch[r][0]<<" "<<ch[r][1]<<" "<<pre[r]<<endl;
	pr(ch[r][1]);
}
inline void update_add(int r,int c)
{
	if(!r)return;
	add[r]+=c;
	key[r]+=c;
	m[r]+=c;
}
inline void update_rev(int r)
{
	if(!r)return;
	rev[r]^=1;
	swap(ch[r][0],ch[r][1]);
}
inline void pushup(int x)
{
	size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
	m[x]=min(key[x],min(m[ch[x][0]],m[ch[x][1]]));
}
inline void pushdown(int x)
{
	if(add[x])
	{
		update_add(ch[x][0],add[x]);
		update_add(ch[x][1],add[x]);
		add[x]=0;
	}
	if(rev[x])
	{
		update_rev(ch[x][0]);
		update_rev(ch[x][1]);
		rev[x]=0;
	}
}
inline void newnode(int &r,int father,int a)
{
	r=++tot;
	ch[r][0]=ch[r][1]=0;
	pre[r]=father;
	key[r]=m[r]=a;
	size[r]=1;
	add[r]=rev[r]=0;
}
void build(int &x,int fa,int l,int r)
{
	if(l>r)return;
	int mid=(l+r)>>1;
	newnode(x,fa,a[mid]);
	build(ch[x][0],x,l,mid-1);
	build(ch[x][1],x,mid+1,r);
	pushup(x);
}
inline void Init()
{
	tot=root=0;
	ch[root][0]=ch[root][1]=pre[root]=size[root]=0;
	rev[root]=add[root]=0;m[root]=inf;
	newnode(root,0,inf);
	newnode(ch[root][1],root,inf);
	build(key_root,ch[root][1],1,n);
	pushup(ch[root][1]);
	pushup(root);
}
inline void Rotate(int x,int kind)
{
	int y=pre[x];
	pushdown(y);pushdown(x);
	//pr(root);cout<<"RRRRRR"<<endl;system("pause");
	ch[y][!kind]=ch[x][kind];
	pre[ch[x][kind]]=y;
	if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
	pre[x]=pre[y];
	//cout<<y<<" "<<x<<" "<<ch[x][kind]<<endl;
	ch[x][kind]=y;
	pre[y]=x;
	pushup(y);
	pushup(x);
}
inline void Splay(int r,int goal)
{
	pushdown(r);
	//pr(root);system("pause");
	while(pre[r]!=goal)
	{
		if(pre[pre[r]]==goal)
		{
			pushdown(pre[r]);
			pushdown(r);
			Rotate(r,ch[pre[r]][0]==r);
		}
		else
		{
			pushdown(pre[pre[r]]);pushdown(pre[r]);pushdown(r);
			int y=pre[r];
			int kind=(ch[pre[y]][0]==y);
			if(ch[y][kind]==r)
			{
				Rotate(r,!kind);
				Rotate(r,kind);
	
			}
			else
			{
				Rotate(y,kind);
				//pr(root);cout<<"SSSSS"<<endl;
				//cout<<root<<endl<<ch[root][0]<<" "<<ch[root][1]<<" "<<key_root<<" "<<ch[ch[root][1]][0]<<endl;
				//system("pause");	
				Rotate(r,kind);
			}
		}
		
	}
	//system("pause");
	pushup(r);
	if(goal==0)root=r;
}
int Get_key(int r,int k)
{
	pushdown(r);
	int t=size[ch[r][0]]+1;
	if(t==k)return r;
	else if(t>k)return Get_key(ch[r][0],k);
	else return Get_key(ch[r][1],k-t);
}
inline void Add(int l,int r,int k)
{
	//pr(root);
	//cout<<Get_key(root,l)<<endl;system("pause");
	Splay(Get_key(root,l),0);
	//pr(root);
	Splay(Get_key(root,r+2),root);
	update_add(key_root,k);
	pushdown(key_root);
	pushup(ch[root][1]);
	pushup(root);
}
inline void Rev(int l,int r)
{
	Splay(Get_key(root,l),0);
	Splay(Get_key(root,r+2),root);
	update_rev(key_root);
	pushdown(key_root);
	pushup(ch[root][1]);
	pushup(root);
}
inline void Delete(int x)
{
	Splay(Get_key(root,x),0);
	Splay(Get_key(root,x+2),root);
	pre[key_root]=0;
	key_root=0;
	pushup(ch[root][1]);
	pushup(root);
}
inline void Insert(int x,int c)
{
	Splay(Get_key(root,x+1),0);
	Splay(Get_key(root,x+2),root);
	newnode(key_root,ch[root][1],c);
	pushup(ch[root][1]);
	pushup(root);
}
inline int Get_min(int l,int r)
{
	Splay(Get_key(root,l),0);
	Splay(Get_key(root,r+2),root);
	return m[key_root];
}
inline void Revolve(int l,int r,int t)
{
	if(t==0)return;
	int k=r-t;
	Splay(Get_key(root,l),0);
	Splay(Get_key(root,k+2),root);
	int tmp=key_root;
	key_root=0;
	pushup(ch[root][1]);
	pushup(root);
	Splay(Get_key(root,r-k+l),0);
	Splay(Get_key(root,r-k+l+1),root);
	key_root=tmp;
	pre[key_root]=ch[root][1];
	pushup(ch[root][1]);
	pushup(root);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	Init();
	int T;scanf("%d",&T);
	char str[10];
	int l,r,k;
	while(T--)
	{
		scanf("%s",str);
		if(!strcmp(str,"ADD"))
		{
			scanf("%d%d%d",&l,&r,&k);
			Add(l,r,k);
		}
		else if(!strcmp(str,"REVERSE"))
		{
			scanf("%d%d",&l,&r);
			Rev(l,r);
		}
		else if(!strcmp(str,"REVOLVE"))
		{
			scanf("%d%d%d",&l,&r,&k);
			int b=r-l+1;
			Revolve(l,r,(k%b+b)%b);
			//pr(root);
		}
		else if(!strcmp(str,"INSERT"))
		{
			scanf("%d%d",&l,&k);
			Insert(l,k);
			//pr(root);
		}
		else if(!strcmp(str,"DELETE"))
		{
			scanf("%d",&l);
			Delete(l);
		}
		else
		{
			scanf("%d%d",&l,&r);
			printf("%d\n",Get_min(l,r));
		}
	}
}

更多推荐

【poj3580】 SuperMemo

本文发布于:2023-03-29 09:55:00，感谢您对本站的认可！

本文链接:https://www.elefans.com/category/jswz/3d47a6f5b6ed3de198bb27fda2f7699b.html