题解 P1486 【郁闷的出纳员】
Creeper_LKF
2017-12-16 10:32:28
这里给出大牛上目前跑的最快(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格式会抽)......
```