HDU - 5096 ACM Rank （Treap）

平衡树的题，Treap破之，比较难搞的出现相同题数罚时的情况，解决方法是在每个结点用一个set，

保证结点值的时候可以把题数和罚时保存到一个int里，令v = n*MaxPenaltySum-penalty。这样就可以很方便地做比较了。

初始化有一定技巧。细节很多容易出错。写静态版，如果有合并操作要内存池开到最大结点数量的两倍，内存多随意

写错一个变量名字查好久，尴尬

hdu似乎不资磁PB_ds这种黑科技

#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

using namespace std;

#define PB push_back

#define MP make_pair

#define fi first

#define se second

#define cer(x) cout<<#x<<'='<<endl

typedef long long ll;

const int maxn = 1e4+, MAXPEN = 1e6;//60*20+3000+666;

int st[maxn], val[maxn], pen[maxn][],lst[maxn],lsa[maxn];

struct CMP

{

    bool operator()(int a,int b) const{

        return lsa[a] < lsa[b];

    }

};

struct Node

{

    int ch[],r,s,v;

    set<int,CMP> vs;

}nds[maxn*];

queue<int> fre;

inline int newNode(int x)

{

    int i;

    Node &u = nds[i = fre.front()]; fre.pop();

    u.ch[] = u.ch[] = ;

    u.r = rand(); u.s = ; u.v = val[x];

    u.vs.clear(); u.vs.insert(x);

    return i;

}

inline void delt(int x)

{

    fre.push(x);

}

inline int cmp(int a,int b)

{

    if(a == b) return -;

    return a>b? :;

}

inline void mt(int i)

{

    Node&u = nds[i];

    u.s = (int)u.vs.size() + nds[u.ch[]].s + nds[u.ch[]].s;

}

inline void rot(int &o,int d)

{

    int k = nds[o].ch[d^];

    nds[o].ch[d^] = nds[k].ch[d];

    nds[k].ch[d] = o;

    mt(o); mt(k);

    o = k;

}

inline void initTreap(int n)

{

    for(int i = ; i < n; i++) fre.push(i);

    nds[].s = ;

}

void inst(int &o,int x)

{

    if(!o) {

        o = newNode(x); return;

    }

    Node &u = nds[o];

    int d = cmp(u.v,val[x]);

    if(~d){

        inst(u.ch[d],x);

        if(u.r < nds[u.ch[d]].r) rot(o,d^);

        //else

    }else {

        u.s++; u.vs.insert(x);

    }

    mt(o);

}

void rmov(int &o,int x)

{

    Node &u = nds[o];

    int d = cmp(u.v,val[x]);

    if(~d){

        rmov(u.ch[d],x);

    }else {

        if((int)u.vs.size() > ){

            u.vs.erase(x); u.s--;

        }else {

            if(u.ch[] && u.ch[]){

                int d2 = nds[u.ch[]].r > nds[u.ch[]].r ? :;

                rot(o,d2); rmov(nds[o].ch[d2],x);

            }else {

                delt(o);

                if(!u.ch[]) o = u.ch[];

                else o = u.ch[];

            }

        }

    }

    if(o) mt(o);

}

int Rank(int o,int x)

{

    Node &u = nds[o];

    int d = cmp(u.v,val[x]);

    if(d == ) return Rank(u.ch[],x);

    int s = nds[u.ch[]].s;

    if(d == ) return s+(int)u.vs.size()+Rank(u.ch[],x);

    return s+;

}

int Kth(int o,int k)

{

    if(!o || k <=  || k > nds[o].s) return -;//

    Node &u = nds[o];

    int s = nds[u.ch[]].s;

    if(k == s+) return *(u.vs.begin());

    if(k <= s) return Kth(u.ch[],k);

    return Kth(u.ch[],k-s-(int)u.vs.size());

}

void rmvTree(int o)

{

    if(nds[o].ch[]) rmvTree(nds[o].ch[]);

    if(nds[o].ch[]) rmvTree(nds[o].ch[]);

    delt(o);

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("data.txt","r",stdin);

#endif

    int N,M;

    char op[];

    initTreap(maxn*);

    int root = ;

    while(~scanf("%d%d",&N,&M)){

        if(root) rmvTree(root);

        root = ;

        fill(st,st+N,);

        fill(val,val+N,);

        fill(lst,lst+N,-);

        memset(pen,,sizeof(pen));

        for(int i = ; i < N; i++){

            lsa[i] = -N+i;

            inst(root,i);

        }

        int c = ;

        while(~scanf("%s",op)&&*op != 'C'){

            if(*op == 'S'){

                int t,x,re; char pro; scanf("%d:%d:%c:%d",&t,&x,&pro,&re);

                int p = pro-'A';

                if(t - lst[x] <  || (st[x]&(<<p))) continue;

                lst[x] = t;

                if(re == ){

                    printf("[%d][%c]\n",x,pro);

                    rmov(root,x);

                    lsa[x] = ++c;

                    st[x] |= <<p;

                    val[x] += MAXPEN-pen[x][p]-t;

                    inst(root,x);

                }else pen[x][p] += ;

            }else if(*op == 'R'){

                int x; scanf("%d",&x);

                printf("%d\n",Rank(root,x));

            }else if(*op == 'T'){

                int k; scanf("%d",&k);

                printf("%d\n",Kth(root,k));

            }

        }

        scanf("%s",op);

        puts("");

    }

    return ;

}

巴特西

HDU - 5096 ACM Rank （Treap）

最新文章

热门文章