很好的一道题，用了三天多的时间，终于知道了我为什么T的原因，也知道了在Splay的同时该怎样子的节约时间，因为Splay本身就是大常数的O（N*logN），我们如果不在各种细节上节约时间，很容易就会造成T的是因为我们制造了一个同样的大常数。
先讲解一下题意：有两种操作，一个是一段区间内的值翻转，另一个是讲[a, b]裁剪下来，然后将这段区间贴到剩下的元素的第c位后面。
然后讲一下Splay翻转的几个要点，还有就是可能的T的点，我们要做到的翻转的操作自然不是太过于难想，很多人都能想到的就是lazy标记的下推，然后改变相对应的值即可。同样的，区间的裁剪再贴到最后也不是那么的难想到，就是裁剪[l, r]这样的区间，我们只需要找到Kth(l-1)和Kth(r+1)，然后裁剪下来他们的中间区域，（这里记得要先pushup(r+1)，然后pushup(l-1)也就是根节点）然后再去寻找到第c大的，还有c+1大的，我们将值放在（c+1）大的左子树那块即可。思路就是这样子的，但是代码总是T，我一开始还写了快速读入，还以为能卡时间，但是很显然，时间不在于输入处，而是Splay的时候，翻转过于浪费时间，那么具体是哪里浪费时间了呢，我们慢慢看。
现在开始讲解Splay会T的一些原因，Splay的操作主要就是在Splay()这个函数，所以当T的时候，我们应该先考虑一下是不是在翻转Splay()的时候有一些可以去掉的大常数，譬如说，我将pushup()还有pushdown()这两个函数写在了Rotate()函数里面，那么我们就不必要再在Splay()函数里面写pushup()和pushdown()了，这里就是可以优化掉一个大常数（这是我到最后发现的TLE的最最最关键的原因）。
当然，我们裁剪掉一部分pushup()以及pushdown()的同时，还需要保证留下足够的对应的返回更新和下放懒标记的函数才行，这里给出哪里必需要放置这两个函数：
inline void pushup(int x) { t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + 1; }
inline void pushdown(int x) { if(t[x].lazy) { t[t[x].ch[0]].lazy ^= 1; t[t[x].ch[1]].lazy ^= 1; swap(t[x].ch[0], t[x].ch[1]); t[x].lazy = 0; } }
然后接下去说说看哪几处地方一定是要放这两个函数的：
void Rotate(int x) { int y = t[x].ff, z = t[y].ff; pushdown(y); pushdown(x); int k = t[y].ch[1] == x; t[z].ch[t[z].ch[1] == y] = x; t[x].ff = z; t[y].ch[k] = t[x].ch[k^1]; t[t[x].ch[k^1]].ff = y; t[x].ch[k^1] = y; t[y].ff = x; pushup(y); pushup(x); }
在Rotate的时候是一定要加上这两个函数的，因为我们在旋转的同时我们会改变节点，所以首先就需要pushdown()，然后，最后需要pushup()。
inline void build_Splay_tree(int &rt, int l, int r, int fa) { if(l > r) return; int mid = HalF; new_node(rt, fa, mid); build_Splay_tree(t[rt].ch[0], l, mid-1, rt); build_Splay_tree(t[rt].ch[1], mid + 1, r, rt); pushup(rt); }
在建Splay树的时候，我们就需要pushup()来得到size的传递。
int Kth(int k) { int u = root; if(t[u].siz < k) return 0; while(true) { pushdown(u); int y = t[u].ch[0]; if(k > t[y].siz + 1) { k -= t[y].siz + 1; u = t[u].ch[1]; } else { if(t[y].siz >= k) u = y; else return u; //找到对应的节点编号了 } } }
我们要找第K个数的时候，也需要pushdown()，因为我们的左右子树的size是不一定相同的，我们要改变翻转的懒标记，然后同时改变左右的子树的位置。
inline void Cut(int l, int r, int pos) { int las = Kth(l), nex = Kth(r + 2); Splay(las, 0); Splay(nex, las); int del = t[nex].ch[0]; t[nex].ch[0] = 0; pushup(nex); pushup(root); int u = Kth(pos + 1), v = Kth(pos + 2); Splay(u, 0); Splay(v, u); t[t[root].ch[1]].ch[0] = del; t[del].ff = v; pushup(v); pushup(u); }
我们cut下来的时候，就需要一次的pushup()，因为此时的两个节点的size都改变了，然后在接下去，我们接上去的时候也需要pushup()，这时候这两个节点就有更多的size了，也是需要更新了。
inline void _OUT(int u) { pushdown(u); if(t[u].ch[0]) _OUT(t[u].ch[0]); if(t[u].val >= 1 && t[u].val <= N) { cnt++; printf("%d%c", t[u].val, cnt == N ? 'n' : ' '); } if(t[u].ch[1]) _OUT(t[u].ch[1]); }
输出的操作当然是要pushdown()的呀，毕竟要对应的找左右嘛，所谓的中序遍历。
好了，上面的所有的情况都考虑到了，基本就能A了吧，也祝愿大家都能过美美哒过这题，不像我……卡了好几天…… (*≧ω≦)
5 4 FLIP 2 4 CUT 2 3 3 FLIP 2 5 CUT 1 3 1 ans:5 1 3 4 2
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r using namespace std; typedef unsigned long long ull; typedef long long ll; const int maxN = 3e5 + 7; int N, M, root, tot; struct node { int ff, val, siz, ch[2], lazy; node() { ff = val = siz = ch[0] = ch[1] = lazy = 0; } }t[maxN]; inline void new_node(int &x, int fa, int val) { x = ++tot; t[x].ff = fa; t[x].val = val; t[x].siz = 1; t[x].ch[0] = t[x].ch[1] = t[x].lazy = 0; } inline void pushdown(int x) { if(t[x].lazy) { t[t[x].ch[0]].lazy ^= 1; t[t[x].ch[1]].lazy ^= 1; swap(t[x].ch[0], t[x].ch[1]); t[x].lazy = 0; } } inline void pushup(int x) { t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + 1; } void Rotate(int x) { int y = t[x].ff, z = t[y].ff; pushdown(y); pushdown(x); int k = t[y].ch[1] == x; t[z].ch[t[z].ch[1] == y] = x; t[x].ff = z; t[y].ch[k] = t[x].ch[k^1]; t[t[x].ch[k^1]].ff = y; t[x].ch[k^1] = y; t[y].ff = x; pushup(y); pushup(x); } void Splay(int x, int goal) { while(t[x].ff != goal) { int y = t[x].ff, z = t[y].ff; if(z != goal) (t[z].ch[0] == y) ^ (t[y].ch[0] == x) ? Rotate(x) : Rotate(y); Rotate(x); } if(!goal) root = x; } inline void insert(int x) { int u = root, ff = 0; while(u && t[u].val != x) { ff = u; u = t[u].ch[x > t[u].val]; } new_node(u, ff, x); if(ff) t[ff].ch[x > t[ff].val] = u; Splay(u, 0); } inline void build_Splay_tree(int &rt, int l, int r, int fa) { if(l > r) return; int mid = HalF; new_node(rt, fa, mid); build_Splay_tree(t[rt].ch[0], l, mid-1, rt); build_Splay_tree(t[rt].ch[1], mid + 1, r, rt); pushup(rt); } int Kth(int k) { int u = root; if(t[u].siz < k) return 0; while(true) { pushdown(u); int y = t[u].ch[0]; if(k > t[y].siz + 1) { k -= t[y].siz + 1; u = t[u].ch[1]; } else { if(t[y].siz >= k) u = y; else return u; //找到对应的节点编号了 } } } inline void Ex_change(int l, int r) { int las = Kth(l), nex = Kth(r + 2); Splay(las, 0); Splay(nex, las); t[t[nex].ch[0]].lazy ^= 1; } inline void Cut(int l, int r, int pos) { int las = Kth(l), nex = Kth(r + 2); Splay(las, 0); Splay(nex, las); int del = t[nex].ch[0]; t[nex].ch[0] = 0; pushup(nex); pushup(root); int u = Kth(pos + 1), v = Kth(pos + 2); Splay(u, 0); Splay(v, u); t[t[root].ch[1]].ch[0] = del; t[del].ff = v; pushup(v); pushup(u); } int cnt; inline void _OUT(int u) { pushdown(u); if(t[u].ch[0]) _OUT(t[u].ch[0]); if(t[u].val >= 1 && t[u].val <= N) { cnt++; printf("%d%c", t[u].val, cnt == N ? 'n' : ' '); } if(t[u].ch[1]) _OUT(t[u].ch[1]); } inline void init() { tot = root = cnt = 0; t[0].siz = t[0].ch[0] = t[0].ch[1] = 0; build_Splay_tree(root, 0, N + 1, 0); } char op[10]; int main() { while(scanf("%d%d", &N, &M) != EOF) { if(N < 0 || M < 0) break; init(); int a, b, c; while(M--) { scanf("%s", op); if(op[0] == 'C') { scanf("%d%d%d", &a, &b, &c); Cut(a, b, c); } else { scanf("%d%d", &a, &b); Ex_change(a, b); } //cnt = 0; //_OUT(root); } _OUT(root); } return 0; } /* 5 4 FLIP 2 4 CUT 2 3 3 FLIP 2 5 CUT 1 3 1 ans:5 1 3 4 2 */
- 还没有人评论，欢迎说说您的想法！
客服
