妈呀,我裂开了啊,调了一天,终于出了
总结一下:
1:add懒标记是用+不是=！！！(如果本来就有标记的就覆盖了),反转也是,一定要注意懒标记不能=
2:splay用来进行区间操作的话,建树的时候可以像(BST)splay一样加入两个哨兵,一个代表下标0,一个代表下标n+1,写函数的时候就不用考虑边界了
3:splay可以像线段树一样进行区间操作,push_up,push_down,但是一定要注意,先push_down自己,再push_down孩子,先push_up孩子,再push_up自己!
4:二叉树建树以及加点多用引用,好处是真的多
代码:
#include<iostream> #include<string.h> using namespace std; const int maxn = 2e5 + 100; inline int read() { int s = 0, w = 1; char ch = getchar(); while (ch < ‘0‘ || ch > ‘9‘) { if (ch == ‘-‘) w = -1; ch = getchar(); } while (ch >= ‘0‘ && ch <= ‘9‘) s = s * 10 + ch - ‘0‘, ch = getchar(); return s * w; } #define ls(x) tree[x][0] #define rs(x) tree[x][1]//良好习惯,不加的话下面用到太多了,容易出错 int tree[maxn][2], siz[maxn], val[maxn], add[maxn], rev[maxn],fa[maxn]; int root,tot; void new_node(int& x, int f, int valu)//引用大法好,以后要经常用QAQ { x = ++tot; fa[x] = f; val[x] = valu; siz[x] = 1; rev[x] = add[x] = 0; ls(x) = rs(x) = 0; } void push_up(int rt) { siz[rt] = siz[ls(rt)] + siz[rs(rt)]+1;//不加cnt,因为排名就是在数组中的位置 } void push_down(int rt) { if (rev[rt]) { swap(ls(rt), rs(rt));//传递 rev[ls(rt)] ^= 1; rev[rs(rt)] ^= 1; rev[rt] = 0;//重置 } if (add[rt]) {//add[rt]是关于其孩子的效果 val[rs(rt)] += add[rt]; val[ls(rt)] += add[rt]; add[ls(rt)] += add[rt]; add[rs(rt)] += add[rt]; add[rt] = 0;//一定要记得重置 } } void rotate(int x) {//这里出错就没办法了,记得更新子节点同时更新子节点的父节点,两两配对 int y = fa[x], z = fa[y], f = (rs(y) == x); push_down(x); push_down(y);//先自己再父亲,我淦! tree[y][f] = tree[x][f ^ 1]; fa[tree[x][f ^ 1]] = y; if (z) { tree[z][rs(z) == y] = x; } fa[x] = z; tree[x][f ^ 1] = y; fa[y] = x; push_up(y); } void splay(int x, int top) { push_down(x);//每次tree下标作为参数的都push_down while (fa[x] != top) { int y = fa[x], z = fa[y]; ///先祖再父后自己???????? if (z != top) { if ((ls(z) == y) ^ (ls(y) == x)) { rotate(x); } else { rotate(y); } } rotate(x); } push_up(x);//可以放这里,因为每次旋转后x都是父亲节点,没必要更新,最后旋转完成来更新就行 if (top == 0)root = x;//旋转到根记得修正 } void rotto(int k,int top) {//把排名当作其在数组中的位置,这样就能轻松完成区间操作 int p = root; push_down(p); while (siz[ls(p)] != k) {//由于增加了两个点,一个最小点,一个最大点,所以查找的时候左孩子的siz就是位置 if (siz[ls(p)] > k)p = ls(p); else k -= (siz[ls(p)]+1), p = rs(p); push_down(p); } splay(p, top); } void insert(int valu, int pos) { rotto(pos, 0); rotto(pos+1, root); new_node(ls(rs(root)), rs(root), valu); push_up(rs(root));//一般插入后需要旋转到根,但是这里我们只是插入到离根位置为2的点,距离比较近,直接更新即可,记得先更新孩子,再更新根 push_up(root); } void add_val(int L, int R,int x) { rotto(L - 1, 0); rotto(R + 1, root);//把L-R区间内的数都赶到右子树的左子树上,然后给个懒标记即可 add[ls(rs(root))] += x;//2 卧槽!!!! val[ls(rs(root))] += x; } void reverse(int L, int R) { rotto(L - 1, 0); rotto(R + 1, root);//没有两个哨兵,你这个操作要多判断多少东西,想一想 rev[ls(rs(root))] ^= 1; } void del(int pos) { rotto(pos - 1, 0); rotto(pos + 1, root);//还是把pos位置的数赶到右子树的左子树,删除即可. ls(rs(root)) = 0; push_up(rs(root)); push_up(root); } void cut(int len, int last) {//把长度为len的区间接到最后面去 rotto(len+1, 0); rotto(0, root);//由于增加了两个点,第一个点的位置永远为0,最后一个点的位置为n+1 int rt = rs(ls(root));//再通过将第一个数旋转到根的儿子位置,这样就能轻松将需要的前几个数赶到一棵树上, rs(ls(root)) = 0;//删除前面len长度的数组成的树,并用rt保存根节点位置 push_up(ls(root)); push_up(root); rotto(last - len, 0);//最后一个点在右侧,把刚拆出来的树区间rt加入到右边去,刚好就是旋转过来的样子 ls(rs(root)) = rt; push_up(rs(root)); push_up(root);//记得及时更新 } int a[maxn]; void build(int l, int r, int& rt, int fa) {//引用大法好 if (l > r) { return; } int mid = (l + r) >> 1; new_node(rt, fa, a[mid]); build(l, mid-1, ls(rt), rt);//虽然和线段树很像,但是只有n个节点,所以减一啊!!!! build(mid + 1, r, rs(rt), rt); push_up(rt); } void init(int n) { for (int i = 1; i <= n; i++) { a[i] = read(); } ls(0) = rs(0) = fa[0] = siz[0] = val[0] = rev[0] = add[0] = 0; root = tot = 0;//初始化注意!!! new_node(root, 0, 0); new_node(rs(root), root, 0);//先开两个点,用来切区间的时候方便处理,一个是左区间端点,一个是友区间端点 //就是哨兵,只不过这里面为了区间操作是按照位置排序的,而常规的splay是按照权值排序的BST树,二者作用不同. build(1, n, ls(rs(root)), rs(root)); //这种方式建成的树的中序遍历结果就是1-n,所以叫中序建树(自己起的) push_up(rs(root)); push_up(root); } int main() { //freopen("test.txt", "r", stdin); int now,num=1; int n, m, k1, k2; while (~scanf("%d%d%d%d",&n,&m,&k1,&k2)) { if (n == 0 && m == 0 && k1 == 0 && k2 == 0)break; now = 1; init(n); printf("Case #%d:\n", num++); while (m--) { string t;cin >> t; char c = t[0]; if (c == ‘a‘) { int x = read(),s = now + k2-1; if (s <= n) { add_val(now, s, x); } else { add_val(now, n, x);//如果超界了就两边加上就好了 add_val(1, s - n, x); } } else if (c == ‘r‘) { int R = now + k1-1; if (R <= n) { reverse(now,R); } else { cut(R - n, n); now =n-k1+1; reverse(now, n); } } else if (c == ‘i‘) { int x = read(); insert(x, now); n++; } else if (c == ‘d‘) { del(now); if (now == n)now = 1; n--; } else if (c == ‘m‘) { int x = read(); if (x == 1)now--; else now++; if (now == 0)now = n; if (now == n + 1)now = 1; } else if(c==‘q‘) { rotto(now, 0); printf("%d\n",val[root]); } } } return 0; }
原文：https://www.cnblogs.com/MYMYACMer/p/14373034.html
