题解 P1486 【郁闷的出纳员】

Creeper_LKF

2017-12-16 10:32:28

Solution

这里给出大牛上目前跑的最快(180ms)的代码以及条平衡树的反思。 首先这里使用了带旋转的Treap,然后发现这玩意真好用。 然后这道题只调了半个小时左右吧,于是十分高兴,总结了写和调平衡树蒟蒻的经验: 1. 对于平衡树,平常的对拍所写的的暴力就只能检查一下数据的答案,如果更好的也可以用暴力检查每一步的答案(然而不是所有题都能做得到) 2. 然后在写平衡树的时候,有一些操作并不需要强行把基础操作组合在一起,否则常数会非常大。例如某份代码在进行S操作的时候,把所有点都遍历了一遍,然后中间还有两次复杂度高log的操作,于是最坏复杂度nlogn,还好操作次数少。于是我们有优化: ```cpp inline void Delete_Lower_Bound(int tar, int &node){ if(!node) return ; if(num[node] < tar){ Delete_Tree(lc);//删除子树 Delete_Lower_Bound(tar, rc);//仿STL Delete(num[node], node);//删除节点 } else if(num[node] >= tar) Delete_Lower_Bound(tar, lc); Updata(node); } ``` 在这种情况下,由于删除子树的时候只要更改值,所以其实可以直接O(1)的断开链接即可(在下面的代码中还是递归),然后Lower\_Bound操作log的,Delete由于已经确定了num[node],而且左儿子已经删完了,所以操作都是O(1)的,总复杂度O(log)。 代码如下: ```cpp #include <cstdio> #include <cctype> using namespace std; #define LL long long #define MAXN 2000005 #define INF 0x3f3f3f3f const LL MODS = 5371321, PRI = 832211; inline char get_char(){ static char buf[5000001], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 5000000, stdin), p1 == p2) ? EOF : *p1 ++; } inline int read(){ int num = 0; char c; while (isspace(c = get_char())); while (num = num * 10 + c - 48, isdigit(c = get_char())); return num; } inline char get_ch(){ char c; while(isspace(c = get_char())); return c; } inline void upmax(int &a, const int &b){ if(a < b) a = b; } int m, min_m, loc, ans; int cnt, tot; int tree[MAXN][2], size[MAXN], wv[MAXN], num[MAXN]; #define lc tree[node][0] #define rc tree[node][1] inline int rand(){ static int sed = 15; return sed = (LL)(sed * PRI) % MODS; } namespace Treap{ inline void Updata(int node){ if(node) size[node] = size[tree[node][0]] + size[tree[node][1]] + 1; } inline void Rotate(int &node, int son){ int tmp = tree[node][son]; tree[node][son] = tree[tmp][!son], tree[tmp][!son] = node; Updata(node), Updata(tmp); node = tmp; } inline void Insert(int tar, int &node){ if(!node) node = ++cnt, size[node] = 1, wv[node] = rand(), num[node] = tar; else { size[node]++; if(tar <= num[node]){ Insert(tar, lc); if(wv[lc] < wv[node]) Rotate(node, 0); } else { Insert(tar, rc); if(wv[rc] < wv[node]) Rotate(node, 1); } } } inline void Delete(int tar, int &node){ if(num[node] == tar){ ans++; if(!(lc * rc)){ node = lc | rc; return ; } if(num[lc] > num[rc]) Rotate(node, 1), Delete(tar, lc); else Rotate(node, 0), Delete(tar, rc); } else { if(num[node] > tar) Delete(tar, lc); else Delete(tar, rc); } Updata(node); } inline void Delete_Tree(int &node){ if(!node) return; if(lc) Delete_Tree(lc); if(rc) Delete_Tree(rc); Updata(node); node = 0, ans++; } inline void Delete_Lower_Bound(int tar, int &node){ if(!node) return ; if(num[node] < tar){ Delete_Tree(lc); Delete_Lower_Bound(tar, rc); Delete(num[node], node); } else if(num[node] >= tar) Delete_Lower_Bound(tar, lc); Updata(node); } inline int Get_Kth(int k, int node){ if(size[lc] == k - 1) return num[node]; if(size[lc] >= k) return Get_Kth(k, lc); return Get_Kth(k - size[lc] - 1, rc); } } int main(){ m = read(), min_m = read(); for(int i = 1; i <= m; i++){ char cons = get_ch(); int tar = read(); if(cons == 'I'){ if(tar >= min_m) Treap::Insert(tar - loc, tot); } else if(cons == 'A') loc += tar; else if(cons == 'S'){ loc -= tar; int tmp = loc - min_m; Treap::Delete_Lower_Bound(-tmp, tot); } else { printf("%d\n", size[tot] >= tar ? Treap::Get_Kth(size[tot] - tar + 1, tot) + loc : -1); } } printf("%d", ans); return 0; } (可能luogu格式会抽)...... ```