牛客网暑期ACM多校训练营(第三场)C.Shuffle Cards
题意:
给你一个n,代表序列1,2,3,...n.给你若干个区间si,pi代表L=si,R=si+pi-1,的区间[L,R] 删除并插入到序列的开头。
样例
5 3 2 3
初始序列[1 2 3 4 5], 操作区间[2, 4]吧 把元素{2,3,4}丢到开头{2,3,4,1,5}。
分析
题意很简单,对区间一段序列移动到另一位置。
1,数组删除,涉及大量元素移动操作。
2,链表模拟,找到区间L,R的端点需要线性扫描。
组合一下【块状链表】,复杂度O(n*sqrt(n))不知道能不能过。
比赛的时候想起的是splay的能在log(n)的时间内删除一个区间,在log(n)的时间内插入一个区间。复杂度是O(q*log(n))的,然后百度翻个splay板子,splay区间平移,然后改改就1A过了。比赛的改板子过了就没管了,赛后才找到自己的splay在哪里冏
还有一种rope,属于一种非标准的stl函数,也就是不是所有OJ都支持,起码C++11
rope你把他当成vector用,复杂度底层非常优秀,块状链表,平衡树的实习。。。具体我也不懂。
知道名字后你们应该都会去搜索这东西怎么用了,就不多说,用法看函数名都很好懂。
然后在啰嗦一句crope a相当于 rope<char> a。补题的时候现学现卖,这个学一学以后能当***树用
#include <bits/stdc++.h> #include <ext/rope> //头文件 using namespace std; using namespace __gnu_cxx; //必备命名空间 const int MAXN = 1e5 + 10; int n, m; int main() { while(~scanf("%d %d", &n, &m)) { rope<int> rop; for(int i = 1; i <= n; i++ ) { rop.push_back(i); } for(int i = 1; i <= m; i++ ) { int l, r; scanf("%d %d", &l, &r); // r = l + r - 1; rop.insert(0, rop.substr(l - 1, r)); rop.erase(l + r - 1, r); } for(int i = 0; i < n; i++ ) { if(i != 0) { printf(" "); } printf("%d", rop[i]); } puts(""); } return 0; }
赛后猜正紧补题,然后才是自己的splay板子。splay的区间翻转操作是常规操作,这里不赘述。我们可以通过三次区间翻转来实习一个区间的平移。
1,2,3,4,5 翻转1~4(这里指的是下标)
4,3,2,1,5 翻转1~3
2,3,4,1,5 翻转4~4
或者你写删除一个区间,插入一个区间来实习也可以。基本是个模板题,但是就是这个模板比较高级。没点过splay技能的几乎想不到。第一次在牛客写题解,有错误欢迎指正
然后留下自己又丑又长的splay模板。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 5e5 + 7; const int inf = 1e9 + 7; int n, m, arr[maxn]; struct Splay_Tree { struct Node { int father, childs[2], key, cnt, _size, rev; inline void init() { father = childs[0] = childs[1] = key = cnt = _size = rev = 0; } inline void init(int father, int lchild, int rchild, int key, int cnt, int sz) { this -> father = father, childs[0] = lchild, childs[1] = rchild; this -> key = key, this -> cnt = cnt, _size = sz; this -> rev = 0; } } tre[maxn]; int sign, root; inline void init() { sign = root = 0; } inline bool judge(int x) { return tre[ tre[x].father ].childs[1] == x; } inline void update(int x) { if(x) { tre[x]._size = tre[x].cnt; if(tre[x].childs[0]) { tre[x]._size += tre[ tre[x].childs[0] ]._size; } if(tre[x].childs[1]) { tre[x]._size += tre[ tre[x].childs[1] ]._size; } } } inline void rotate(int x) { int y = tre[x].father, z = tre[y].father, k = judge(x); pushdown(y), pushdown(x); //tre[y].childs[k] = tre[x].childs[!k], tre[ tre[x].childs[!k] ].father = y; //tre[x].childs[!k] = y, tre[y].father = x; //tre[z].childs[ tre[z].childs[1] == y ] = x, tre[x].father = z; if(k == 0) {///zig tre[y].childs[0] = tre[x].childs[1], tre[ tre[x].childs[1] ].father = y; tre[x].childs[1] = y, tre[y].father = x; } else { ///zag tre[y].childs[1] = tre[x].childs[0], tre[ tre[x].childs[0] ].father = y; tre[x].childs[0] = y, tre[y].father = x; } tre[z].childs[ tre[z].childs[1] == y ] = x, tre[x].father = z; update(y); } inline void splay(int x,int goal) { for(int father; (father = tre[x].father) != goal; rotate(x) ) { if(tre[father].father != goal) { rotate(judge(x) == judge(father) ? father : x); } } if(goal == 0) { root = x; } } inline void pushdown(int x) { if(x && tre[x].rev) { tre[ tre[x].childs[0] ].rev ^= 1; tre[ tre[x].childs[1] ].rev ^= 1; swap(tre[x].childs[0], tre[x].childs[1]); tre[x].rev = 0; } } int build(int l, int r, int fa) { if(l > r) { return 0; } int mid = (l + r) >> 1; int now = ++ sign; tre[now].init(fa, 0, 0, arr[mid], 1, 1); tre[now].childs[0] = build(l, mid - 1, now); tre[now].childs[1] = build(mid + 1, r, now); update(now); return now; } int find(int x) { int now = root; while(1) { pushdown(now); if(x <= tre[ tre[now].childs[0] ]._size) { now = tre[now].childs[0]; } else { x -= tre[ tre[now].childs[0] ]._size + 1; if(!x) { return now; } now = tre[now].childs[1]; } } } void reverse(int x, int y) { int L = x - 1, R = y + 1, pos; L = find(L), R = find(R); splay(L, 0); splay(R, L); pos = tre[root].childs[1]; pos = tre[pos].childs[0]; tre[pos].rev ^= 1; } inline void dfs(int now) { pushdown(now); if(tre[now].childs[0]) { dfs(tre[now].childs[0]); } if(tre[now].key != -inf && tre[now].key != inf) { printf("%d ", tre[now].key); } if(tre[now].childs[1]) { dfs(tre[now].childs[1]); } } void solve(int l, int r) { reverse(2, r); reverse(2, 2 + r - l); reverse(2 + r - l + 1, r); } } S; int main() { scanf("%d %d", &n, &m); S.init(); arr[1] = -inf, arr[n + 2] = inf; for(int i = 1; i <= n; i ++ ) { arr[i + 1] = i; } S.root = S.build(1, n + 2, 0); for(int i = 1; i <= m; i ++ ) { int x, y; scanf("%d %d", &x, &y); int l = x, r = x + y - 1; l++, r++; S.solve(l, r); } S.dfs(S.root); return 0; }
全部评论
(1) 回帖