题解 P1486 【郁闷的出纳员】

2017-12-16 10:32:28


这里给出大牛上目前跑的最快(180ms)的代码以及条平衡树的反思。

首先这里使用了带旋转的Treap,然后发现这玩意真好用。

然后这道题只调了半个小时左右吧,于是十分高兴,总结了写和调平衡树蒟蒻的经验:

  1. 对于平衡树,平常的对拍所写的的暴力就只能检查一下数据的答案,如果更好的也可以用暴力检查每一步的答案(然而不是所有题都能做得到)

  2. 然后在写平衡树的时候,有一些操作并不需要强行把基础操作组合在一起,否则常数会非常大。例如某份代码在进行S操作的时候,把所有点都遍历了一遍,然后中间还有两次复杂度高log的操作,于是最坏复杂度nlogn,还好操作次数少。于是我们有优化:

    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)。 代码如下:

    #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格式会抽)......