依然是伸展树的基本操作,不过这次多了一个revolve x,y,z 选取x--y的子串,平移z位。也好处理,找到起点的新位置,然后把子串拆成两段,把后面的切下来插到前边就行了。要注意的一点就是z可能很大,也可能是负数....
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <memory.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <stack>
using namespace std;
typedef int ll;
const ll inf=(1<<29);
const int maxn=200000+2000;
int pre[maxn],ch[maxn][2];
int flip[maxn];
int size[maxn];
ll key[maxn],minn[maxn],a[maxn];
int stk[maxn];
int top;
ll add[maxn];
bool same[maxn];
int root,tot,n,m;
int p,q,tt,t,k,r;
struct splaytree
{
void pushup(int r)
{
size[r]=size[ch[r][0]]+1+size[ch[r][1]];
minn[r]=min(key[r],min(minn[ch[r][0]],minn[ch[r][1]]));
}
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 x,int tgt)
{
pushdown(x);
while(pre[x]!=tgt)
{
int y=pre[x];
// pushdown(pre[y]);
// pushdown(y);
// pushdown(x);
if (pre[pre[x]]==tgt)
{
rotate(x,ch[pre[x]][0]==x);
}
else
{
int kind=ch[pre[y]][0]==y;
if (ch[y][kind]==x)
{
rotate(x,kind^1);
rotate(x,kind);
}
else
{
rotate(y,kind);
rotate(x,kind);
}
}
}
pushup(x);
if (tgt==0) root=x;
}
void select(int k,int tgt)
{
int rt=root;
pushdown(rt);
while(true)
{
if (k<=size[ch[rt][0]]) rt=ch[rt][0];
else if (k==size[ch[rt][0]]+1) break;
else k-=(size[ch[rt][0]]+1),rt=ch[rt][1];
pushdown(rt);
}
splay(rt,tgt);
}
void newnode(int &r,int father,ll k)
{
if (top) r=stk[top--];
else r=++tot;
pre[r]=father;
size[r]=1;
flip[r]=0;
add[r]=0;
minn[r]=key[r]=k;
ch[r][0]=ch[r][1]=0;
}
void build(int l,int r,int &x,int rt)
{
if (l>r) return;
int m=(l+r)>>1;
newnode(x,rt,a[m]);
build(l,m-1,ch[x][0],x);
build(m+1,r,ch[x][1],x);
pushup(x);
}
void init()
{
tot=root=0;
top=0;
minn[0]=key[0]=inf;
flip[0]=0;
add[0]=0;
ch[0][0]=ch[0][1]=0;
size[0]=0;
pre[0]=0;
newnode(root,0,inf);
newnode(ch[root][1],root,inf);
build(1,n,ch[ch[root][1]][0],ch[root][1]);
pushup(ch[root][1]);
pushup(root);
}
void go_f(int r)
{
if(!r) return;
flip[r]^=1;
swap(ch[r][0],ch[r][1]);
}
void go_a(int r,ll c)
{
if (!r) return;
add[r]+=c;
key[r]+=c;
minn[r]+=c;
}
void pushdownadd(int r)
{
if (add[r])
{
go_a(ch[r][0],add[r]);
go_a(ch[r][1],add[r]);
add[r]=0;
}
}
void pushdownflip(int r)
{
if (flip[r])
{
go_f(ch[r][0]);
go_f(ch[r][1]);
flip[r]=0;
}
}
void pushdown(int r)
{
pushdownadd(r);
pushdownflip(r);
}
void insert(int posi,ll c)
{
select(posi+1,0);
select(posi+2,root);
newnode(ch[ch[root][1]][0],ch[root][1],c);
pushup(ch[root][1]);
pushup(root);
}
void recover(int r)
{
if (!r) return;
stk[++top]=t;
recover(ch[r][0]);
recover(ch[r][1]);
}
void del(int posi)
{
select(posi,0);
select(posi+2,root);
pre[ch[ch[root][1]][0]]=0;
ch[ch[root][1]][0]=0;
pushup(ch[root][1]);
pushup(root);
}
void reverse(int x,int y)
{
select(x,0);
select(y+2,root);
go_f(ch[ch[root][1]][0]);
int k=ch[ch[root][1]][0];
}
void revolve(int x,int y,int z)
{
int p1,k;
int s;
int len=(y-x+1);
z=z-(z/len)*len;
if (z<0) z+=len;
if (!z) return;
s=x+z;
p1=x+y-s;
select(p1+1,0);
select(y+2,root);
k=ch[ch[root][1]][0];
ch[ch[root][1]][0]=0;
pushup(ch[root][1]);
pushup(root);
select(x,0);
select(x+1,root);
ch[ch[root][1]][0]=k;
pre[k]=ch[root][1];
pushup(ch[root][1]);
pushup(root);
}
void Add(int x,int y,ll c)
{
select(x,0);
select(y+2,root);
go_a(ch[ch[root][1]][0],c);
}
ll Min(int x,int y)
{
select(x,0);
select(y+2,root);
return minn[ch[ch[root][1]][0]];
}
}spt;
char cmd[10];
int x,y,z;
ll c;
int main()
{
// freopen("in.txt","r",stdin);
scanf("%d",&n);
for (int i=1; i<=n; i++)
scanf("%d",&a[i]);
scanf("%d",&m);
spt.init();
getchar();
for (int i=1; i<=m; i++)
{
scanf("%s",cmd);
if (cmd[0]=='A')
{
scanf("%d%d%d",&x,&y,&c);
spt.Add(x,y,c);
}
else
if (cmd[0]=='R' && cmd[3]=='E')
{
scanf("%d%d",&x,&y);
spt.reverse(x,y);
}
else
if (cmd[0]=='R' && cmd[3]=='O')
{
scanf("%d%d%d",&x,&y,&z);
spt.revolve(x,y,z);
}
else
if (cmd[0]=='I')
{
scanf("%d%d",&x,&c);
spt.insert(x,c);
}
else
if (cmd[0]=='D')
{
scanf("%d",&x);
spt.del(x);
}
else
if (cmd[0]=='M')
{
scanf("%d%d",&x,&y);
printf("%d\n",spt.Min(x,y));
}
}
return 0;
}
更多推荐
poj3580 SuperMemo 伸展树 splay
发布评论