题意:
给定一个数组,对数组进行6种操作。
区间加,区间翻转,插入一个值,删除一个值,区间求最小值。
区间循环移位。
题解:
前5种属于伸展树的基本操作,区间循环移位需要转化成基本操作:
区间[l,r]循环右移T位(T=T%(r-l+1) )。相当于区间[l,r-T]和区间[r-T+1,r]
调换了位置。通过区间删除和插入可以完成。
注意:删除操作需要有内存回收。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ddd puts("111");
using namespace std;
#define keyv ch[ch[root][1]][0]
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 99;
int pre[maxn],sz[maxn],ch[maxn][2],addv[maxn],minv[maxn],key[maxn],rev[maxn],root,tot1;
int s[maxn],tot2;///内存池,当有删除操作的时候进行回收
int a[maxn];
int n,q;
void update_add(int r,int add)
{
if(r==0)return;
key[r] += add;
minv[r] += add;
addv[r] += add;
}
void update_rev(int r)
{
if(r == 0)return;
swap(ch[r][0],ch[r][1]);
rev[r]^=1;///下面的反转次数+1。
}
void pushdown(int r)
{
if(rev[r])
{
update_rev(ch[r][0]);
update_rev(ch[r][1]);
rev[r] = 0;
}
if(addv[r])
{
update_add(ch[r][0],addv[r]);
update_add(ch[r][1],addv[r]);
addv[r] = 0;
}
}
void pushup(int r)
{
sz[r] = 1 + sz[ch[r][0]]+sz[ch[r][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 newnode(int &r,int fa,int k)
{
if(tot2)r = s[tot2--];
else r = ++tot1;
minv[r] = key[r] = k;
pre[r] = fa;
rev[r] = addv[r] = ch[r][0] = ch[r][1] = 0;
sz[r] = 1;
}
void build(int &x,int l,int r,int fa)
{
if(l>r)return;
int m = (l+r)>>1;
newnode(x,fa,a[m]);
build(ch[x][0],l,m-1,x);
build(ch[x][1],m+1,r,x);
pushup(x);
}
void init()
{
root = tot1 = tot2 = 0;
pre[root] = ch[root][1] = ch[root][0] = addv[root] = key[root] = rev[root] = sz[root] = 0;
minv[root] = INF;
newnode(root,0,INF);
newnode(ch[root][1],root,INF);
build(keyv,1,n,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
}
void rotate(int x,int d)
{
int y = pre[x];
pushdown(y);
pushdown(x);
ch[y][!d] = ch[x][d];
pre[ch[x][d] ] = y;
if(pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = x;
pre[x] = pre[y];
ch[x][d] = y;
pre[y] = x;
pushup(y);
}
void splay(int r,int goal)
{
while(pre[r] != goal)
{
if(pre[pre[r]] == goal)
rotate(r,ch[pre[r]][0]==r);
else
{
int y = pre[r];
int d = ch[pre[y]][0] == y;
if(ch[y][d] == r)
{
rotate(r,!d);
rotate(r,d);
}
else
{
rotate(y,d);
rotate(r,d);
}
}
}
pushup(r);
if(goal==0)root = r;
}
int kth(int r,int k)
{
pushdown(r);
int t = sz[ch[r][0]];
if(t+1 == k) return r;
else if(k<=t) return kth(ch[r][0],k);
else return kth(ch[r][1],k-1-t);
}
int getmax(int r)
{
pushdown(r);
while(ch[r][1])
{
r = ch[r][1];
pushdown(r);
}
return r;
}
int getmin(int r)
{
pushdown(r);
while(ch[r][0])
{
r = ch[r][0];
pushdown(r);
}
return r;
}
/**本题*/
void add(int l,int r,int v)
{
splay(kth(root,l),0);
splay(kth(root,r+2),root);
update_add(keyv,v);
pushup(ch[root][1]);
pushup(root);
}
void Reverse(int l,int r)
{
splay(kth(root,l),0);
splay(kth(root,r+2),root);
update_rev(keyv);
pushup(ch[root][1]);
pushup(root);
}
void revolve(int l,int r,int T)///区间循环移位
{
int len = r-l+1;
T = (T%len);
if(T==0)return;
int m = r - T;/**区间[l,m],[m+1,r]调换位置*/
splay(kth(root,m+1),0);
splay(kth(root,r+2),root);
int tmp = keyv;
keyv = 0;
pushup(ch[root][1]);
pushup(root);///先把第二个区间删除。
splay(kth(root,l),0);
splay(kth(root,l+1),root);
keyv = tmp;
pre[tmp] = ch[root][1];
pushup(ch[root][1]);
pushup(root);///再插入第一个区间前。 这样做的前提是两个区间是相邻的!
}
void Insert(int x,int p)///插入
{
splay(kth(root,x+1),0);///x后
splay(kth(root,x+2),root);///x+1前
newnode(keyv,ch[root][1],p);
pushup(ch[root][1]);
pushup(root);
}
void Erase(int r)
{
if(r)
{
s[++tot2] = r;
Erase(ch[r][0]);
Erase(ch[r][1]);
}
}
void ddelete(int r)///删除
{
splay(kth(root,r),0);
splay(kth(root,r+2),root);
Erase(keyv);
pre[keyv] = 0;
keyv = 0;
pushup(ch[root][1]);
pushup(root);
}
int mmin(int l,int r)///区间最小
{
splay(kth(root,l),0);
splay(kth(root,r+2),root);
return minv[keyv];
}
void Treavel(int x)
{
if(x)
{
pushdown(x);
Treavel(ch[x][0]);
printf("%d ",key[x]);
Treavel(ch[x][1]);
}
}
int main()
{
int x,y,z;
char op[20];
while(scanf("%d",&n)==1)
{
for(int i=1;i<=n;i++)
scanf("%d",a+i);
init();
scanf("%d",&q);
while(q--)
{
scanf("%s",op);
if(strcmp(op,"ADD") == 0)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
else if(strcmp(op,"REVERSE")==0)
{
scanf("%d%d",&x,&y);
Reverse(x,y);
}
else if(strcmp(op,"REVOLVE")==0)
{
scanf("%d%d%d",&x,&y,&z);
revolve(x,y,z);
}
else if(strcmp(op,"DELETE")==0)
{
scanf("%d",&x);
ddelete(x);
}
else if(strcmp(op,"MIN")==0)
{
scanf("%d%d",&x,&y);
printf("%d\n",mmin(x,y));
}
else if(strcmp(op,"INSERT")==0)
{
scanf("%d%d",&x,&y);
Insert(x,y);
}
//Treavel(root);
}
}
}
更多推荐
POJ 3580 SuperMemo(伸展树的几个基本操作)
发布评论