洛谷 P3391
/*Splay只记模板是很困难的，而且真正运用时易生疏出错，所以必须理解，在看代码前先弄懂 Splay的原理，这篇代码是带注释的Splay模板，题目来自洛谷P3391 ———————————by 520*/ #include<bits/stdc++.h> #define il inline using namespace std; const int N = 100005; il int gi() { int a = 0; char x = getchar(); bool f = 0; while ((x<'0' || x>'9') && x != '-')x = getchar(); if (x == '-')x = getchar(), f = 1; while (x >= '0'&&x <= '9')a = a * 10 + x - 48, x = getchar(); return f ? -a : a; } int n, m, tot, root, siz[N], fa[N], lazy[N], key[N], tree[N][2], ans[N]; /*root为根节点,siz存储子树节点数，fa存储父节点，lazy是懒惰标记用来标记区间翻转操作，key数组存储原数列，tree为 splay树，ans存储答案*/ il void pushup(int rt) //作用类似与线段树 { int l = tree[rt][0], r = tree[rt][1]; //pushup作用是将子树的节点个数更新给根节点 siz[rt] = siz[l] + siz[r] + 1; } il void pushdown(int now) { if (lazy[now]) { lazy[tree[now][0]] ^= 1; lazy[tree[now][1]] ^= 1; /*pushdown作用是下放懒惰标记，若某一节点所在子树（即某一区间）被翻转 ，则将懒惰标记下放给两个儿子节点，交换左右儿子位置（中序遍历，交换左右儿子后相当于翻转）并对所在子树根节 点的标记清0,*/ swap(tree[now][0], tree[now][1]); lazy[now] = 0; } } il int getson(int x) { return tree[fa[x]][1] == x; } //getson判断x是其父亲的右儿子还是左儿子 il void rotate(int x) //旋转操作，直接写在一个函数里，可以称为上旋 { int y = fa[x], z = fa[y], b = getson(x), c = getson(y), a = tree[x][!b]; /*y是x的父节点，z是y的父节点，getson解释过了。 特别解释一下a，a为旋转时需要移动的子树，若x为左儿子则右旋时要将x的右子树移动，同理若x为右儿子则左旋时要 将x的左子树移动，所以这里a=tree[x][!b]*/ if (z)tree[z][c] = x; else root = x; fa[x] = z; /*若z不为根节点，则用x替代y的位置;若z为根节点，则将x变为根节点。*/ if (a)fa[a] = y; tree[y][b] = a; /*若存在要移动的子树a，则把a和y相连，取代原来x的位置*/ tree[x][!b] = y; fa[y] = x; /*!b的原因：若x为左儿子则旋转后y为x的右儿子，若x为右儿子则旋转后y为x的左儿子。记得将y 指向x*/ pushup(y); pushup(x); /*旋转后，对被移动了的y和x更新它们各自的子树节点数*/ } il void splay(int x, int i) { while (fa[x] != i) { //只要x没有旋转到需要的点下面，则一直旋，注意根节点的父亲为虚点0 int y = fa[x], z = fa[y]; if (z == i)rotate(x); //若x的爷爷是i，则只需旋一次 else { if (getson(x) == getson(y)) { rotate(y); rotate(x); } /*若x和y为相同偏向，则进行Zig-Zig或Zag-Zag操作*/ else { rotate(x); rotate(x); } /*否则进行Zig-Zag或Zag-Zig操作*/ /*注意rotate函数中已经包含了这四种操作情况了*/ } } } il int find(int x) //查找x的位置 { int now = root; //从根节点往下 while (1) { pushdown(now); //本次操作要将前面的标记进行翻转 if (tree[now][0] && x <= siz[tree[now][0]])now = tree[now][0]; //若存在左子树且x小于等于左子树的节点数，则x在左子树上 else { int tmp = (tree[now][0] ? siz[tree[now][0]] : 0) + 1; //往右子树找，+1代表加上这个子树的根节点 if (x == tmp)return now; //若找到了x，返回它的位置 x -= tmp; //否则x减去根节点右子树以外的节点数，这个画图能理解，因为siz值并不是直接的x的值 now = tree[now][1]; //将原来根节点的右儿子赋为新的根节点，继续递归查找x位置 } } } il int build(int l, int r, int rt) //建树过程和线段树类似 { int now = l + r >> 1; fa[now] = rt; key[now] = ans[now]; //key存原数组1到n，准确说是0到n+1,原因是主函数里的预处理 if (l < now)tree[now][0] = build(l, now - 1, now); if (r > now)tree[now][1] = build(now + 1, r, now); pushup(now); //记得pushup return now; } il void print(int now) //输出时中序遍历，按左根右输出 { pushdown(now); //记得要翻转 if (tree[now][0])print(tree[now][0]); //因为中序遍历左根右，所以递归根节点左子树到第一个数的位置 ans[++tot] = key[now]; //回溯时存储答案,注意我们翻转操作的是原数组下标 if (tree[now][1])print(tree[now][1]); //同理递归根节点的右子树 } int main() { n = gi(), m = gi(); int x, y; for (int i = 1; i <= n + 2; i++)ans[i] = i - 1; /*因为取出操作区间时旋转的是x的前驱和y的后驱，所以预处理时第i个点 存的是i的前驱*/ root = build(1, n + 2, 0); while (m--) { x = gi(), y = gi(); x = find(x), y = find(y + 2); /*查找x的前驱所在的位置，和y后驱所在的位置，因为预处理时ans存的是前趋， 所以直接查找x，而y的后驱变成了y+2*/ splay(x, 0); splay(y, x); /*将x前驱上旋至根节点，y的后驱上旋成根节点右儿子的左子树*/ lazy[tree[tree[root][1]][0]] ^= 1;//经过旋转后，此时根节点的右儿子的左子树就是需要翻转的区间，所以lazy标记 } print(root); for (int i = 1; i <= n; i++)printf("%d ", ans[i + 1]); //输出时将前驱还原为原数 return 0; }
poj 3580&BZOJ 1895
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; const int maxn = 2e5 + 7; const int INF = 1e9; int n, m; int ch[maxn][2]; //0做孩子， 1右孩子 int f[maxn]; //每个节点的父亲 int sz[maxn]; //每个节点为根子树的大小 int val[maxn]; //这个节点所表示的值 int cnt[maxn]; //这个节点所表示值的数量 int mi[maxn]; //这个节点子树的最小值 int rev[maxn]; //反转标记 int lazy[maxn]; //延迟标记 int root; // splay的根 int tot; //树所有的节点数量 void Swap(int &x, int &y) { x ^= y; y ^= x; x ^= y; } int Min(int x, int y) { return x < y ? x : y; } void update_rev(int x) //更新反转 { if (!x) return; Swap(ch[x][0], ch[x][1]); rev[x] ^= 1; //如果这一层曾经被转过下面就不用转了， 把rev取消了 } void update_add(int x, int v) { if (x) lazy[x] += v, val[x] += v, mi[x] += v; } void newnode(int rt, int v, int fa) { f[rt] = fa; sz[rt] = 1; val[rt] = mi[rt] = v; ch[rt][0] = ch[rt][1] = rev[rt] = lazy[rt] = 0; //加点的时候把所有的信息都更新了 } void delnode(int rt) //为了回收空间，其实没什么太大的用处 { f[rt] = val[rt] = sz[rt] = mi[rt] = 0; ch[rt][0] = ch[rt][1] = rev[rt] = lazy[rt] = 0; } void pushup(int x) //跟线段树一样，从下往上不断更新 { if (!x)return; sz[x] = 1, mi[x] = val[x]; if (ch[x][0]) sz[x] += sz[ch[x][0]], mi[x] = Min(mi[x], mi[ch[x][0]]); //更新个数跟当前子树最小值 if (ch[x][1]) sz[x] += sz[ch[x][1]], mi[x] = Min(mi[x], mi[ch[x][1]]); } void pushdown(int x) //向下传递lazy 跟 rev { if (!x) return; if (lazy[x]) { update_add(ch[x][0], lazy[x]); update_add(ch[x][1], lazy[x]); lazy[x] = 0; } if (rev[x]) { update_rev(ch[x][0]); update_rev(ch[x][1]); rev[x] = 0; } } void build(int &rt, int l, int r, int fa) //rt是节点编号，节点的大小代表了两个数位置的相对顺序 { //一共tot个节点 if (l > r) return; int mid = (r + l) >> 1; rt = mid; newnode(rt, val[rt], fa); build(ch[rt][0], l, mid - 1, rt); build(ch[rt][1], mid + 1, r, rt); pushup(rt); } void Rotate(int x, int k) // k = 0左旋， k = 1右旋 { int y = f[x]; int z = f[y]; pushdown(y); pushdown(x); ch[y][!k] = ch[x][k]; if (ch[x][k]) f[ch[x][k]] = y; f[x] = z; if (z) ch[z][ch[z][1] == y] = x; f[y] = x; ch[x][k] = y; pushup(y), pushup(x); } void splay(int x, int goal) { pushdown(x); while (f[x] != goal) { int y = f[x], z = f[y]; //在这里下传翻转标记，在rotate里下传标记可能会使树形改变导致旋转出错 pushdown(z); pushdown(y); pushdown(x); if (f[y] == goal) Rotate(x, ch[y][0] == x); else { int p = ch[f[y]][0] == y; if (ch[y][p] == x) Rotate(x, !p), Rotate(x, p); else Rotate(y, p), Rotate(x, p); } } pushup(x); if (goal == 0) root = x; } //以x为根的子树 的极值点 0 极小 1 极大 int extreme(int x, int k) { while (ch[x][k]) x = ch[x][k]; splay(x, 0); //所有操作之后都伸展下 return x; } //以节点编号x为根的子树 第k个数的节点编号 int kth(int x, int k) { pushdown(x); if (sz[ch[x][0]] + 1 == k) return x; else if (sz[ch[x][0]] >= k) return kth(ch[x][0], k); else return kth(ch[x][1], k - sz[ch[x][0]] - 1); } //区间交换 void exchange(int l1, int r1, int l2, int r2) { int x = kth(root, l2 - 1), y = kth(root, r2 + 1); splay(x, 0), splay(y, x); int tmp_right = ch[y][0]; ch[y][0] = 0; //“剪贴下来” x = kth(root, l1 - 1), y = kth(root, l1); splay(x, 0), splay(y, x); ch[y][0] = tmp_right; f[tmp_right] = y; } //区间翻转 void reversal(int l, int r) { int x = kth(root, l - 1), y = kth(root, r + 1); splay(x, 0); splay(y, x); update_rev(ch[y][0]); //ch[y][0]就是l-r区间 } //区间加 void add(int l, int r, int v) { int x = kth(root, l - 1), y = kth(root, r + 1); // cout << 1 <<endl; splay(x, 0); splay(y, x); update_add(ch[y][0], v); //ch[y][0]就是l-r区间 } //在第k个数后插入值为x的节点 void Insert(int k, int x) { int r = kth(root, k), rr = kth(root, k + 1); splay(r, 0), splay(rr, r); newnode(++tot, x, rr); ch[rr][0] = tot; //节点个数增加 for (r = rr; r; r = f[r]) pushdown(r), pushup(r); splay(rr, 0); } //删除第k位置的数 void Delete(int k) { splay(kth(root, k - 1), 0); splay(kth(root, k + 1), root); delnode(ch[ch[root][1]][0]); ch[ch[root][1]][0] = 0; pushup(ch[root][1]); pushup(root); } // 获取区间最大值 //int get_max(int l,int r) //{ // int x = kth(root,l-1), y = kth(root,r+1); // splay(x,0); splay(y,x); // return mx[ch[y][0]]; //} //获取区间最小值 int get_min(int l, int r) { int x = kth(root, l - 1), y = kth(root, r + 1); splay(x, 0); splay(y, x); return mi[ch[y][0]]; } void init(int n) { root = 0; //不断更新的， 不断插入的， 需要一个tot记录插入节点的编号 // tot = 0; // newnode(++tot, -INF, 0); // newnode(++tot, INF, root); // ch[root][1] = tot; f[0] = sz[0] = ch[0][0] = ch[0][1] = rev[0] = lazy[0] = 0; //rt编号多加两个，处理区间[1,n] build(root, 1, n, 0); pushup(root); } char s[12]; int main() { scanf("%d", &n); val[1] = val[n + 2] = INF; //多加两个编号0,n+1， 把区间1-n包起来 for (int i = 2; i <= n + 1; i++) scanf("%d", &val[i]); tot = n + 2; init(n + 2); scanf("%d", &m); for (int i = 1; i <= m; i++) { int d, l, r; scanf(" %s", s); if (s[0] == 'A') { //ADD scanf("%d%d%d", &l, &r, &d); add(l + 1, r + 1, d); } else if (s[0] == 'I') { //INSERT scanf("%d%d", &l, &d); Insert(l + 1, d); } else if (s[0] == 'M') { //MIN scanf("%d%d", &l, &r); printf("%d\n", get_min(l + 1, r + 1)); } else if (s[0] == 'D') { //DELETE scanf("%d", &l); Delete(l + 1); } else if (s[3] == 'E') { //REVERSE scanf("%d%d", &l, &r); reversal(l + 1, r + 1); //增加了1一个节点全体后移一个 } else { //REVOLVE scanf("%d%d%d", &l, &r, &d); d = d % (r - l + 1); if (d) exchange(l + 1, r - d + 1, r - d + 1 + 1, r + 1); } } return 0; }
