Language:
SuperMemo
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, {A1, A2, ... An}. Then the host performs a series of operations and queries on the sequence which consists:
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 5 1 2 3 4 5 2 ADD 2 4 1 MIN 4 5 |
ADD:把第x-1个伸展到根节点,y+1伸展到根节点的右孩子,然后改变区间标志add
REVERSE:基本同ADD操作,修改的是rev标记
REVOLVE:先取模,然后把(pos,r+1)旋转到根的右孩子的左孩子,删除,然后把第l个伸展到根节点,l+1伸展到根节点的右孩子,然后把刚才的区间放到左孩子
INSERT:把第x个伸展到根节点,x+1伸展到根节点的右孩子,然后插入
DELETE:同上,然后递归删除
MIN:同上,直接询问minv标记
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
#define Key_value ch[ch[root][1]][0]
const int maxn=200010;
const int INF=1000000010;
char str[20];
int N,M,a[maxn],root,tot1,tot2;
int ch[maxn][2],pre[maxn],add[maxn],rev[maxn],minv[maxn];
int size[maxn],key[maxn],s[maxn];
void NewNode(int &r,int f,int val)
{
if(tot2)r=s[tot2--];
else r=++tot1;
ch[r][0]=ch[r][1]=0;
pre[r]=f;
size[r]=1;
add[r]=rev[r]=0;
key[r]=minv[r]=val;
}
void pushup(int r)
{
size[r]=size[ch[r][0]]+size[ch[r][1]]+1;
minv[r]=key[r];
if(ch[r][0])minv[r]=min(minv[r],minv[ch[r][0]]);
if(ch[r][1])minv[r]=min(minv[r],minv[ch[r][1]]);
}
void build(int &x,int l,int r,int f)
{
if(l>r)return ;
int mid=(l+r)>>1;
NewNode(x,f,a[mid]);
build(ch[x][0],l,mid-1,x);
build(ch[x][1],mid+1,r,x);
pushup(x);
}
void init()
{
root=tot1=tot2=0;
ch[root][0]=ch[root][1]=size[root]=add[root]=rev[root]=pre[root]=0;
minv[root]=INF;
NewNode(root,0,INF);
NewNode(ch[root][1],root,INF);
build(Key_value,1,N,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
}
void update_rev(int r)
{
if(!r)return;
swap(ch[r][0],ch[r][1]);
rev[r]^=1;
}
void update_add(int r,int val)
{
if(!r)return;
add[r]+=val;
key[r]+=val;
minv[r]+=val;
}
void pushdown(int r)
{
if(rev[r])
{
update_rev(ch[r][0]);
update_rev(ch[r][1]);
rev[r]=0;
}
if(add[r])
{
update_add(ch[r][0],add[r]);
update_add(ch[r][1],add[r]);
add[r]=0;
}
}
void Rotate(int x,int kind)
{
int y=pre[x];
pushdown(y);
pushdown(x);
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];
ch[x][kind]=y;
pre[y]=x;
pushup(y);
}
void Splay(int r,int goal)
{
pushdown(r);
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);
Rotate(r,kind);
}
}
}
pushup(r);
if(goal==0)root=r;
}
int get_kth(int r,int k)
{
pushdown(r);
int t=size[ch[r][0]]+1;
if(t==k)return r;
if(t>k)return get_kth(ch[r][0],k);
else return get_kth(ch[r][1],k-t);
}
void ADD(int x,int y,int D)
{
Splay(get_kth(root,x),0);
Splay(get_kth(root,y+2),root);
update_add(Key_value,D);
pushup(ch[root][1]);
pushup(root);
}
void REVERSE(int x,int y)
{
Splay(get_kth(root,x),0);
Splay(get_kth(root,y+2),root);
update_rev(Key_value);
pushup(ch[root][1]);
pushup(root);
}
void Insert(int x,int P)
{
Splay(get_kth(root,x+1),0);
Splay(get_kth(root,x+2),root);
NewNode(Key_value,ch[root][1],P);
pushup(ch[root][1]);
pushup(root);
}
void Revolve(int l,int r,int T)
{
int len=r-l+1;
T=(T%len+len)%len;
if(T==0)return;
int pos=r-T+1;
Splay(get_kth(root,pos),0);
Splay(get_kth(root,r+2),root);
int tmp=Key_value;
Key_value=0;
pushup(ch[root][1]);
pushup(root);
Splay(get_kth(root,l),0);
Splay(get_kth(root,l+1),root);
Key_value=tmp;
pre[Key_value]=ch[root][1];
pushup(ch[root][1]);
pushup(root);
}
void erase(int r)
{
if(r)
{
s[++tot2]=r;
erase(ch[r][0]);
erase(ch[r][1]);
}
}
void Delete(int x)
{
Splay(get_kth(root,x),0);
Splay(get_kth(root,x+2),root);
erase(Key_value);
pre[Key_value]=0;
Key_value=0;
pushup(ch[root][1]);
pushup(root);
}
int Min(int x,int y)
{
Splay(get_kth(root,x),0);
Splay(get_kth(root,y+2),root);
return minv[Key_value];
}
int main()
{
while(scanf("%d",&N)!=EOF)
{
for(int i=1;i<=N;i++)scanf("%d",&a[i]);
init();
scanf("%d",&M);
int x,y,D,T,P;
while(M--)
{
scanf("%s",str);
if(!strcmp(str,"ADD"))
{
scanf("%d%d%d",&x,&y,&D);
ADD(x,y,D);
}
else if(!strcmp(str,"REVERSE"))
{
scanf("%d%d",&x,&y);
REVERSE(x,y);
}
else if(!strcmp(str,"REVOLVE"))
{
scanf("%d%d%d",&x,&y,&T);
Revolve(x,y,T);
}
else if(!strcmp(str,"INSERT"))
{
scanf("%d%d",&x,&P);
Insert(x,P);
}
else if(!strcmp(str,"DELETE"))
{
scanf("%d",&x);
Delete(x);
}
else
{
scanf("%d%d",&x,&y);
printf("%d\n",Min(x,y));
}
}
}
return 0;
}
更多推荐
伸展树(区间加值,反转,循环移动,插入,删除区间,求区间最小值)poj3580
发布评论