【POJ 2182】Lost Cows

【题目链接】

http://poj.org/problem?id=2182

【算法】

树状数组 + 二分

【代码】

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 8010

int i,n;

int a[MAXN],ans[MAXN],c[MAXN];

inline int lowbit(int x)

{

        return x & (-x);

}

inline void modify(int pos,int val)

{

        int i;

        for (i = pos; i <= n; i += lowbit(i)) c[i] += val;

}

inline int query(int pos)

{

        int i;

        int ret = ;

        for (i = pos; i; i -= lowbit(i)) ret += c[i];

        return ret;

}

inline int get(int k)

{

        int l = ,r = n,mid;

        int ret;

        while (l <= r)

        {

                mid = (l + r) >> ;

                if (query(mid) >= k)

                {

                        ret = mid;

                        r = mid - ;

                } else l = mid + ;

        }

        return ret;

}

int main()

{

        scanf("%d",&n);

        for (i = ; i <= n; i++) scanf("%d",&a[i]);

        for (i = ; i <= n; i++) c[i] = lowbit(i);

        for (i = n; i >= ; i--)

        {

                ans[i] = get(a[i]+);

                modify(ans[i],-);

        }

        for (i = ; i <= n; i++) printf("%d\n",ans[i]);

        return ;

}