cf1208 D Restore Permutation （二分+树状数组）

题意

让你构造一个长度为n的序列，记为p₁……p_n，（这个序列是1~n的全排列的一种）

给你n个数，记为s₁……s_n，s_i_的值为p₁……p_i-1中小于pi的数的和。

思路

显然，应该倒着来，也就是从p_n开始构造，这样的话，当要填p_i的时候，p₁到p_i-1就是所有的还未填的数，那么我们只需要去找哪个前缀和符合就可以了。

比如：现在还没填进去的数是 1,2,3,4,5

而我现在的s_i 是6，那么，对应的p_i 就是4，因为这样无论1,2,3,5怎么排，都符合s_i 为6

（才学疏浅，不怎么会讲）

那么，选完要删除，所以要修改前缀和，考虑用树状数组，查找哪个符合，自然是二分。

代码

#include <stdio.h>

#include <queue>

#include <string>

#include <string.h>

#include <algorithm>

#include <math.h>

#include <set>

using namespace std;

typedef long long int ll;

const int maxn = 2e5 + ;

const int inf = ;

const ll mod = ;

const ll seed = ;

ll s[maxn],c[maxn],ans[maxn],n;

int lowbit(int x)

{

    return x & (-x);

}

void insert(ll x,int i)

{

    while(i <= n){

        c[i] += x;

        i += lowbit(i);

    }

}

ll getsum(int i)

{

    ll sum = ;

    while(i > ){

        sum += c[i];

        i -= lowbit(i);

    }

    return sum;

}

int vis[maxn];

int query(ll x)

{

    int l,r,mid;

    ll res;

    l = ;r = n;

    while(l <= r){

        mid = (l + r) >> ;

        res = getsum(mid);

        if(res == x){

            if(vis[mid + ])

                l = mid + ;

            else

                return mid;

        }

        else if(res < x){

            l = mid + ;

        }

        else{

            r = mid - ;

        }

    }

}

int main()

{

    while(scanf("%d",&n) != EOF){

        memset(vis,,sizeof(vis));

        memset(c,,sizeof(c));

        for(int i = ;i <= n;i++){

            scanf("%lld",&s[i]);

            insert(i,i);

        }

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

            ans[i] = query(s[i]) + ;

            vis[ans[i]] = ;

            insert(-ans[i],ans[i]);

        }

        for(int i = ;i <= n;i++)

            printf("%d ",ans[i]);

        puts("");

    }

    return ;

}

巴特西

cf1208 D Restore Permutation （二分+树状数组）

最新文章

热门文章