「poj 2182」 Lost Cows (Splay / 树状数组+二分 / 线段树)

发表于 | 分类于 | | + s

「poj 2182」 Lost Cows
题意：有$n$头牛，编号为$[1, n]$。 乱序排成一列，已知每头牛前面有多少头牛比它的编号小（从第二头牛开始）。现在要求从前到后，每一头牛的编号。

考虑逆向思考，对于第$n$头牛如果前面有$a_i$头比他小，那他得编号就是$a_i+1$
对于第$n-1$头牛类似，只不过有可能编号在之前用过了，也就是在一个集合中找排名为$a_i+1$的数。
所以我们要维护一个集合支持删除一个数，查询$rnk$，显然线段树和Splay是可行的。
然而这里可以用编码量更小的树状数组+二分。
因为正数前缀和有单调性，所以我们将存在和不存在记为一个二进制01序列，然后可以通过前缀和判断当前为是排名多少的。然后就能二分了。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 8000 + 5;

    int n, hh[MAXN], a[MAXN];

    int lowbit(int x) {return x & (-x);}
    void add(int x, int val) {
        for (int i = x; i <= n; i += lowbit(i)) a[i] += val;
    }
    int query(int x) {
        int ret = 0;
        for (int i = x; i; i -= lowbit(i)) ret += a[i];
        return ret;
    }

    void clean() {
        ms(a, 0);
    }
    int solve() {
        clean();
        cin >> n;
        for (int i = 2; i <= n; ++i) scanf("%d", &hh[i]);
        for (int i = 1; i <= n; ++i) add(i, 1);
        for (int i = n; i >= 2; --i) {
            int l = 1, r = n + 1, pos = 0;
            while (l < r) {
                int mid = (l + r) >> 1;
                int res = query(mid);
                if (res > hh[i] + 1) r = mid; else {
                    if (res == hh[i] + 1) pos = mid, r = mid;
                    else l = mid + 1;
                }
            }
            hh[i] = pos;
            add(pos, -1);
        }
        for (int i = 1; i <= n; ++i) if (query(i)) {hh[1] = i; break ;}
        for (int i = 1; i <= n; ++i) printf("%d\n", hh[i]);
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------