//本来用指针的那种写法,wa了20多次受不了了,看了一个大佬的博客,代码基本照抄,只不过将splay时pushdown(x)修该到Rotate里面
#include <iostream>
#include <cstdio>#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e5+10;
const int INF = 0x3f3f3f3f;
struct splaytree {
int Size,root,top;
int st[maxn],a[maxn];
int next[maxn][2],pre[maxn],key[maxn],num[maxn];
int add[maxn],Min[maxn];
bool flip[maxn];
void newnode(int &x,int father,int val) {
if (top != -1) {
x = st[top--];
}
else x = ++Size;
next[x][0] = next[x][1] = add[x] = 0;
pre[x] = father;
key[x] = Min[x] = val;
num[x] = 1;
flip[x] = false;
}
void pushup(int x) {
num[x] = num[next[x][0]]+num[next[x][1]]+1;
Min[x] = min(Min[next[x][0]],Min[next[x][1]]);
Min[x] = min(Min[x],key[x]);
}
void pushdown(int x) {
int l = next[x][0];
int r = next[x][1];
if (add[x]) {
if (l) {
add[l] += add[x];
Min[l] += add[x];
key[l] += add[x];
}
if (r) {
add[r] += add[x];
Min[r] += add[x];
key[r] += add[x];
}
add[x] = 0;
}
if (flip[x]) {
flip[l] ^= 1;
flip[r] ^= 1;
swap(next[x][0],next[x][1]);
flip[x] = 0;
}
}
void build(int &x,int l,int r,int father) {
if (l <= r) {
int m = (l+r)>>1;
newnode(x,father,a[m]);
build(next[x][0],l,m-1,x);
build(next[x][1],m+1,r,x);
pushup(x);
}
}
void init(int n) {
root = Size = 0;
top = -1;
flip[0] = false;
next[0][0] = next[0][1] = add[0] = pre[0] = num[0] = 0;
key[0] = Min[0] = INF;
newnode(root,0,INF);
newnode(next[root][1],root,INF);
build(next[next[root][1]][0],1,n,next[root][1]);
pushup(next[root][1]);
pushup(root);
}
void Rotate(int x,int kind) {
int y = pre[x];
int z = pre[y];
pushdown(y);
pushdown(x);
next[y][!kind] = next[x][kind];
pre[next[x][kind]] = y;
next[z][next[z][1] == y] = x;
pre[x] = z;
next[x][kind] = y;
pre[y] = x;
pushup(y);
}
void Splay(int x,int goal) {
if (x != goal) {
while(pre[x] != goal) {
if (next[pre[x]][0] == x)
Rotate(x,1);
else
Rotate(x,0);
}
pushup(x);
if (!goal) root = x;
}
}
int Select (int k) {
pushdown(root);
int x;
for (x = root; num[next[x][0]]+1 != k; ) {
if (num[next[x][0]]+1 > k)
x = next[x][0];
else {
k -= num[next[x][0]]+1;
x = next[x][1];
}
pushdown(x);
}
return x;
}
void Add(int x,int y,int val) {
x = Select(x-1);
y = Select(y+1);
Splay(x,0);
Splay(y,x);
add[next[y][0]] += val;
Min[next[y][0]] += val;
key[next[y][0]] += val;
pushup(y);
pushup(x);
}
void Flip(int x, int y) {
x = Select(x - 1);
y = Select(y + 1);
Splay(x, 0);
Splay(y, x);
flip[next[y][0]] ^= true;
}
int Revolve(int x,int y,int d) {
d = (d%(y-x+1)+(y-x+1))%(y-x+1);
if (d) {
Flip(x,y-d);
Flip(y-d+1,y);
Flip(x,y);
}
}
void Insert(int x,int val) {
int a = Select(x);
int b = Select(x+1);
Splay(a,0);
Splay(b,a);
newnode(next[b][0],b,val);
pushup(b);
pushup(a);
}
void Delete(int x) {
int a = Select(x-1);
int b = Select(x+1);
Splay(a,0);
Splay(b,a);
st[++top] = next[b][0];
next[b][0] = 0;
pushup(b);
pushup(a);
}
int Getmin(int x,int y) {
int a = Select(x-1);
int b = Select(y+1);
Splay(a,0);
Splay(b,a);
return Min[next[b][0]];
}
}spt;
int main() {
char cmd[18];
int n, q, i;
int x, y, val;
while (~scanf("%d", &n)) {
for (i = 1; i <= n; i++)
scanf("%d", &spt.a[i]);
spt.init(n);
scanf("%d", &q);
while (q--) {
scanf(" %s", cmd);
if (strcmp(cmd, "ADD") == 0) {
scanf("%d%d%d", &x, &y, &val);
spt.Add(x + 1, y + 1, val);
} else if (strcmp(cmd, "REVERSE") == 0) {
scanf("%d%d", &x, &y);
spt.Flip(x + 1, y + 1);
} else if (strcmp(cmd, "REVOLVE") == 0) {
scanf("%d%d%d", &x, &y, &val);
spt.Revolve(x + 1, y + 1, val);
} else if (strcmp(cmd, "INSERT") == 0) {
scanf("%d%d", &x, &val);
spt.Insert(x + 1, val);
} else if (strcmp(cmd, "DELETE") == 0) {
scanf("%d", &x);
spt.Delete(x + 1);
} else {
scanf("%d%d", &x, &y);
printf("%d\n", spt.Getmin(x + 1, y + 1));
}
}
}
return 0;
}
更多推荐
poj 3580 (splay 模板)
发布评论