2014-team1/OMG

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

struct BITmap{
    static const LL SIZE=1ll<<32, BIAS=5;
    unordered_map <LL, LL> u;
    void clear(){ u.clear(); }
    LL U(LL x){
        if (u.find(x)!=u.end()) return u[x];
        return 0;
    }
    LL X(LL x){ return x-BIAS; }

    void add(LL x){
        for (x+=BIAS; x<=SIZE; x+=x&-x) u[x]++;
    }
    void del(LL x){
        for (x+=BIAS; x<=SIZE; x+=x&-x) u[x]--;
    }
    LL getrank(LL x){
        LL s=0;
        for (x+=BIAS; x; x-=x&-x) s+=U(x);
        return s;
    }
    LL getkth(LL k){    // k can not > u.size()
        for (LL pre=0;;){
            for (LL x=pre+1; x<=SIZE; x+=x&-x){
                if (U(x)>=k){
                    if (x==pre+1) return X(x);
                    k-=U(pre); break;
                }
                pre=x;
            }
        }
    }
};

}}}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct BITmap{
    static const LL SIZE=1ll<<32, BIAS=5;
    unordered_map <LL, LL> u;
    void clear(){ u.clear(); }
    LL U(LL x){
        if (u.find(x)!=u.end()) return u[x];
        return 0;
    }
    LL X(LL x){ return x-BIAS; }
    void add(LL x){
        for (x+=BIAS; x<=SIZE; x+=x&-x) u[x]++;
    }
    void del(LL x){
        for (x+=BIAS; x<=SIZE; x+=x&-x) u[x]--;
    }
    LL getrank(LL x){
        LL s=0;
        for (x+=BIAS; x; x-=x&-x) s+=U(x);
        return s;
    }
    LL getkth(LL k){    // k can not > u.size()
        for (LL pre=0;;){
            for (LL x=pre+1; x<=SIZE; x+=x&-x){
                if (U(x)>=k){
                    if (x==pre+1) return X(x);
                    k-=U(pre); break;
                }
                pre=x;
            }
        }
    }
};