POJ

题意:一堆人在排队。有人过来插队( 以位置为索引[1] )。求最后队伍的排列。

解法一

由于最后的位置是一定确定的,所以逆过来处理。
用BIT维护前缀有多少个空位,由此确定接下来的人的位置。二分就可以了。
值得注意的是对BIT进行二分等价于在线段树上直接走。哪种效率高可以自己思考一下。

解法二

裸treap。加入即为找出区间第k大在其后增加节点。效率似乎较低。
本沙茶在弱智细节上一直出错调了一晚上微笑。

BIT 二分

#include <cstdio>
#include <cstdlib>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 2e5 + 100;

int A[maxn] = {0};
int pos[maxn] = {0}, val[maxn] = {0};
int ret[maxn] = {0};
int n;

void add(int a, int x)
{
    for(int i = a; i <= n; i += i & -i)
        A[i] += x;
}

int get(int a)
{
    int ans = 0;
    for(int i = a; i > 0; i -= i & -i)
        ans += A[i];
    return ans;
}

void go(int i)
{
    int l = 1, r = n;
    while(l < r)
    {
        int m = (l + r) / 2, k = get(m);
        if(k >= pos[i] + 1)
            r = m;
        else
            l = m + 1;
    }
    ret[l] = val[i];
    add(l, -1);
}

int main()
{
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n; i++)
            add(i, 1);
        for(int i = 0; i < n; i++)
            read(pos[i], val[i]);
        for(int i = n - 1; i >= 0; i--)
            go(i);
        for(int i = 1; i <= n; i++)
            printf("%d ", ret[i]);
        puts("");
    }
    return 0;
}

treap

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}

const int maxn = 2e5 + 100;
int n;
struct Node
{
    int r;
    int v, p;
    int size;
    int ch[2];
    Node(int a = 0, int b = 0, int c = 0, int d = 0) : r(a), p(b), v(c), size(d) {ch[0] = ch[1] = 0;}
} pool[maxn];
int cnt = 0, root = 1;

inline int cmp(int o, int x){return pool[o].v == x ? -1 : (pool[o].v < x ? 1 : 0);}
inline void maintain(int o){pool[o].size = pool[pool[o].ch[0]].size + pool[pool[o].ch[1]].size + 1;}

inline void rotate(int &o, int d)
{
    int p = pool[o].ch[d ^ 1];
    pool[o].ch[d ^ 1] = pool[p].ch[d];
    pool[p].ch[d] = o;
    maintain(o), maintain(p);
    o = p;
}

void insert(int &o, int p, int v)
{
    if(!o)
        pool[o = ++cnt] = Node(rand(), p, v, 1);
    else
    {
        int d = pool[pool[o].ch[0]].size;
        if(d >= p)
        {
            insert(pool[o].ch[0], p, v);
            maintain(o);
            if(pool[pool[o].ch[0]].r > pool[o].r)
                rotate(o, 1);
        }
        else
        {
            insert(pool[o].ch[1], p - d - 1, v);
            maintain(o);
            if(pool[pool[o].ch[1]].r > pool[o].r)
                rotate(o, 0);
        }
    }
}

void travel(int o)
{
    if(!o)
        return;
    travel(pool[o].ch[0]);
    printf("%d ", pool[o].v);
    travel(pool[o].ch[1]);
}

int main()
{
    srand(233);
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < n; i++)
            pool[i] = Node(); 
        root = 0, cnt = 0;
        for(int i = 0; i < n; i++)
        {
            int pos, val;
            read(pos, val);
            insert(root, pos, val);
        }
        travel(root);
        puts("");
    }
    return 0;
}

1 有别于「以人为索引」。一个是绝对位置,提供位置序号;一个是相对位置,提供人的序号。在琢磨语言准确的同时也可以思考另一种情况的做法。

标签: bit, treap

添加新评论