本文共 4144 字，大约阅读时间需要 13 分钟。
传送门：
题解：Splay树
如果要把指针从1移到2，可以把1先删除，再插入到n的后面，如果要把指针从1移动到n，可以把n删除，再插入到1的前面
#includeusing namespace std;const int MX = 2e5 + 5;int m, k1, k2;int n;int a[MX];int root, rear; //根节点,节点总数int rem[MX], tot; //经过删除后未被使用的节点int ch[MX][2], fa[MX];int val[MX], col[MX], add[MX];int sz[MX];void NewNode(int &rt, int father, int v) { if (tot) rt = rem[tot--]; else rt = ++rear; fa[rt] = father; ch[rt][0] = ch[rt][1] = col[rt] = add[rt] = 0; val[rt] = v; sz[rt] = 1;}void PushUP(int rt) { int ls = ch[rt][0], rs = ch[rt][1]; sz[rt] = sz[ls] + sz[rs] + 1;}void PushDown(int rt) { if (col[rt]) { col[ch[rt][0]] ^= col[rt]; col[ch[rt][1]] ^= col[rt]; swap(ch[rt][0], ch[rt][1]); col[rt] = 0; } if (add[rt]) { add[ch[rt][0]] += add[rt]; add[ch[rt][1]] += add[rt]; val[ch[rt][0]] += add[rt]; val[ch[rt][1]] += add[rt]; add[rt] = 0; }}void build(int &rt, int l, int r, int father) { if (l > r) return; int m = (l + r) >> 1; NewNode(rt, father, a[m]); build(ch[rt][0], l, m - 1, rt); build(ch[rt][1], m + 1, r, rt); PushUP(rt);}void init() { root = rear = tot = 0; NewNode(root, 0, 0); //一共n+2个节点,0~n+1 NewNode(ch[root][1], root, 0); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); build(ch[ch[root][1]][0], 1, n, ch[root][1]); PushUP(root);}void Link(int x, int y, int c) { fa[x] = y; ch[y][c] = x;}void Rotate(int x, int c) { //c=0表示左旋,c=1表示右旋 int y = fa[x]; PushDown(y); PushDown(x); Link(x, fa[y], ch[fa[y]][1] == y); Link(ch[x][c], y, !c); Link(y, x, c); PushUP(y); //y变成x子节点,只要更新y}void Splay(int x, int f) { PushDown(x); while (fa[x] != f) { int y = fa[x]; if (fa[y] == f) Rotate(x, ch[y][0] == x); else { int t = ch[fa[y]][0] == y; if (ch[y][t] == x) Rotate(x, !t); else Rotate(y, t); Rotate(x, t); } } PushUP(x); //更新x if (f == 0) root = x;}int get_kth(int rt, int k) { PushDown(rt); int t = sz[ch[rt][0]] + 1, ret; if (t == k) ret = rt; else if (t > k) ret = get_kth(ch[rt][0], k); else ret = get_kth(ch[rt][1], k - t); PushUP(rt); return ret;}void Update(int L, int R, int v) { Splay(get_kth(root, L), 0); Splay(get_kth(root, R + 2), root); int t = ch[ch[root][1]][0]; add[t] += v; val[t] += v;}void Reverse(int L, int R) { Splay(get_kth(root, L), 0); Splay(get_kth(root, R + 2), root); int t = ch[ch[root][1]][0]; col[t] ^= 1;}void Insert(int p, int v) { Splay(get_kth(root, p + 1), 0); //将第p个数旋转到根节点 Splay(get_kth(root, p + 2), root); //将第p+1个数旋转到根节点的右儿子，此时该节点没有左儿子 NewNode(ch[ch[root][1]][0], ch[root][1], v); PushUP(ch[root][1]); PushUP(root); n++;}void erase(int rt) { if (!rt)return; fa[rt] = 0; rem[++tot] = rt; n--; erase(ch[rt][0]); erase(ch[rt][1]);}int Delete(int p) { Splay(get_kth(root, p), 0); //将第p-1个数旋转到根节点 Splay(get_kth(root, p + 2), root);//将第p+1个数旋转到根节点的右儿子，此时该节点左儿子为p int t = ch[ch[root][1]][0]; erase(t); ch[ch[root][1]][0] = 0; PushUP(ch[root][1]); PushUP(root); return t;}int Query(int p) { Splay(get_kth(root, p + 1), 0); //将第p个数旋转到根节点 return val[root];}void Move(int x) { if (x == 1) { int t = Delete(n); Insert(0, val[t]); } else { int t = Delete(1); Insert(n, val[t]); }}int main() { char op[10]; int x, cas = 0; //freopen("in.txt","r",stdin); while (scanf("%d%d%d%d", &n, &m, &k1, &k2), n || m || k1 || k2) { printf("Case #%d:\n", ++cas); init(); while (m--) { scanf("%s", op); if (op[0] == 'a') { scanf("%d", &x); Update(1, k2, x); } else if (op[0] == 'r') Reverse(1, k1); else if (op[0] == 'i') { scanf("%d", &x); Insert(1, x); } else if (op[0] == 'd') { Delete(1); } else if (op[0] == 'm') { scanf("%d", &x); Move(x); } else printf("%d\n", Query(1)); } } return 0;}
转载地址：http://ypwpn.baihongyu.com/