splay终极题目- -。。。
给定一个初始的排列
(A1,A2,A3...An)(n≤105)
,还有
m(m≤105)
次操作。
ADD x y D: 把数列标号[x,y]的每个元素都加上S
REVERSE x y: 翻转区间[x,y]
REVOLVE x y T: 把区间[x,y]后移T位, 例如在数列{1, 2, 3, 4, 5} 使用”REVOLVE 2 4 2”的结果是{1, 3, 4, 2, 5}
INSERT x P: 在第x个元素后面插入P
DELETE x: 删除第x个元素
MIN x y: 查询区间[x,y]的最小值
好了,本题并没有什么思维难度,码农题,细节容易出错,一调半天0 0。
注意下数组要开
2∗105
因为有插入操作
可能会有人疑惑在对区间[L,R]操作的时候,为什么要把L旋转到根,把R+2旋转到根的右儿子。由于是闭区间,区间[L,R]内的每一个元素都要被修改,因此把L-1旋转到根,R+1旋转到根的右儿子,那么R+1的左儿子对应的子树就表示了区间[L,R],对R+1的左儿子打个标记也就是对[L,R]打上了标记。但是,我们为了预防出错在建树的时候多了0和n+1两个节点,在树中寻找第L-1,R+1个元素就变成了寻找第L,R+2个元素。
还有就是比较恶心的后移操作,T有可能大于区间长度,需要取一下余数。我们删除区间[L,R-T]是要把它移动到第R个元素后面,但是删除之后树中就缺少了R-T-L+1个元素,实则就变成了在第L+T-1和第L+T号元素之间插入删去的那个区间。例如对于排列1 2 3 4 5 6 7 8我们要把2 3 4 5 6后移两位,首先删掉2 3 4剩下1 5 6 7 8然后在L+T-1=2+2-1=3号元素后面(也就是数组中的6)插入2 3 4。(注意下之前都没有考虑多插入的那个0)
还有,要注意下pushup和pushdown操作的位置。
#include<cstdio>
#include<cstring>
#include<cctype>
#define MAXN 200010
using namespace std;
inline int Min(int a,int b)
{return a < b ? a : b;}
inline void Swap(int &a,int &b)
{int c = a; a = b; b = c;}
int minn[MAXN],a[MAXN],v[MAXN],delta[MAXN],rev[MAXN];//数组要大,不然乱访问内存导致TLE
int ch[MAXN][2],fa[MAXN],sz[MAXN],tot,n,m,root;
char c,ops[10];
void GET(int &t)
{
int f = 1; t = 0;
do{c = getchar(); if(c == '-') f = -1;}while(c>'9'||c<'0');
while(isdigit(c)) {t = t*10+c-'0'; c = getchar();}
t *= f;
}
void pushup(int x)
{
sz[x] = sz[ch[x][0]]+sz[ch[x][1]]+1;
minn[x] = v[x];
if(ch[x][0]) minn[x] = Min(minn[ch[x][0]],minn[x]);
if(ch[x][1]) minn[x] = Min(minn[ch[x][1]],minn[x]);
}
void pushdown(int x)
{
if(delta[x])
{
delta[ch[x][0]] += delta[x];
delta[ch[x][1]] += delta[x];
v[ch[x][0]] += delta[x];
v[ch[x][1]] += delta[x];
minn[ch[x][0]] += delta[x];
minn[ch[x][1]] += delta[x];
delta[x] = 0;
}
if(rev[x])
{
rev[ch[x][0]] ^= 1;
rev[ch[x][1]] ^= 1;
Swap(ch[x][0],ch[x][1]);
rev[x] = 0;
}
}
void rotate(int x)
{
int y = fa[x],z = fa[y],f = (ch[y][1]==x);
ch[y][f] = ch[x][!f];
if(ch[y][f]) fa[ch[y][f]] = y;
ch[x][!f] = y,fa[y] = x;
fa[x] = z;
if(z) ch[z][ch[z][1]==y] = x;
pushup(y);
pushup(x);
}
void splay(int x,int goal)
{
for(int y; (y=fa[x]) != goal; rotate(x))
{
int z = fa[y];
if(z != goal)
{
if((ch[z][0]==y) == (ch[y][0]==x)) rotate(y);//
else rotate(x);
}
}
if(!goal) root = x;
pushup(x);
}
void rotateTo(int k,int goal)
{
int x = root;
while(1)
{
pushdown(x);
if(sz[ch[x][0]]+1 < k) k -= sz[ch[x][0]]+1,x = ch[x][1];
else if(sz[ch[x][0]]+1 > k) x = ch[x][0];
else break;
}
splay(x,goal);
}
void New(int &x,int val,int Fa)
{
x = ++tot;
v[x] = minn[x] = val;
sz[x] = 1;
fa[x] = Fa;
}
void build_tree(int &x,int L,int R,int Fa)
{
int mid = (L+R)/2;
New(x,a[mid],Fa);
if(L == R) return;
if(L < mid) build_tree(ch[x][0],L,mid-1,x);
if(R > mid) build_tree(ch[x][1],mid+1,R,x);
pushup(x);
}
void add(int L,int R,int D)
{
rotateTo(L,0);
rotateTo(R+2,root);
int u = ch[ch[root][1]][0];
delta[u] += D;
v[u] += D;
minn[u] += D;
}
void reverse(int L,int R)
{
rotateTo(L,0);
rotateTo(R+2,root);
int u = ch[ch[root][1]][0];
rev[u] ^= 1;
}
void revolve(int L,int R,int T)
{
T = T%(R-L+1);
if(!T) return;
rotateTo(L,0);
rotateTo(R-T+2,root);
int u = ch[ch[root][1]][0];
ch[ch[root][1]][0] = 0;
pushup(ch[root][1]);
pushup(root);
rotateTo(L+T,0);
rotateTo(L+T+1,root);
ch[ch[root][1]][0] = u;//之前手残把u打成了0,一调半天
fa[u] = ch[root][1];
pushup(ch[root][1]);
pushup(root);
}
void insert(int x,int P)
{
rotateTo(x+1,0);
rotateTo(x+2,root);
New(ch[ch[root][1]][0],P,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
}
void del(int x)
{
rotateTo(x,0);
rotateTo(x+2,root);
ch[ch[root][1]][0] = 0;
pushup(ch[root][1]);
pushup(root);
}
int get_MIN(int L,int R)
{
rotateTo(L,0);
rotateTo(R+2,root);
return minn[ch[ch[root][1]][0]];
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
build_tree(root,0,n+1,0);
int x,y,z;
scanf("%d",&m);
while(m--)
{
memset(ops,0,sizeof ops);
scanf("%s",ops);
if(ops[0] == 'A')
{
GET(x);
GET(y);
GET(z);
add(x,y,z);
}
else if(ops[5] == 'S')
{
GET(x);
GET(y);
reverse(x,y);
}
else if(ops[5] == 'V')
{
GET(x);
GET(y);
GET(z);
revolve(x,y,z);
}
else if(ops[0] == 'I')
{
GET(x);
GET(y);
insert(x,y);
}
else if(ops[0] == 'D')
{
GET(x);
del(x);
}
else
{
GET(x);
GET(y);
printf("%d\n",get_MIN(x,y));
}
}
}
更多推荐
POJ3580 SuperMemo(Splay)
发布评论