POJ 2828

POJ 2828

November 14, 2019

1413views

333 words

## 树状数组

我们可以倒序枚举,然后求解答案。显然最后一个人的位置是$a[n] + 1$, 这个位置已经有人了，然后我们把这个位置删去。我们可以发现每个人的位置就是$1-n$中未被使用的位置中第$a[i] + 1$个数，我们可以用树状数组来维护位置每个位置的使用情况，我们每次查询既是查询最小的$pos$，使得$sum[pos]>=a[i]+1$ (sum是前缀和),这个可以用树状数组+二分来解决，复杂度 $O(n*log^2_n)$ ,不过我们可以利用树状数组的性质，用倍增来处理查询。
我们都知道树状数组$c[i]$代表原数组中 $a[i-lowbit(i)+1,i]$ 的和，我们也知道一个数可以拆分成若干个二进制的和。所以我们用倍增思想来找到 $<a[i]+1$ 的最大的数x，注意这里一定要写小于，最终x+1就是答案。复杂度$O(n*log_n)$。

虽然复杂度差个log，但是跑起来时间差不多,23333.

```cpp
#include<cstdio>
using namespace std;
#define lowbit(x) (x&(-x))
const int N=2e5+10;
int a[N],n,c[N],b[N],ans[N];
int up = 20;
void add(int x,int val)
{
    while(x<=n)
    {
        c[x]+=val;
        x+=lowbit(x);
    }
}
int ask(int x)
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
int query(int k)
{
    int sum = 0 ,ans =0;
    for(int i = up ; i>=0 ;--i)
    {
        if(ans + (1<<i) <= n && sum + c[ans + (1<<i)] < k )
        {
            ans += (1<<i) ;
            sum += c[ans] ;
        }
    }
    return ans + 1;
   
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i],&b[i]);
            add(i,1);
        }
        for(int i=n;i>=1;i--)
        {
            int pos=query(a[i]+1);
            ans[pos]=b[i];
            add(pos,-1);
        }
        for(int i=1;i<=n;i++)
            printf("%d ",ans[i]);
        puts("");
        for(int i = 0;i<=n;++i) c[i] = 0;
    }
    return 0;
}

````

Last modification：November 14th, 2019 at 05:22 pm

如果觉得我的文章对你有用，请随意赞赏

POJ 2828