【bzoj5170】Fable（树状数组）

　　题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=5170

　　我们会发现，经过一轮冒泡后，若a[i]的前面有比它大的数，就一定会有一个被丢到后面去，即a[i]会前移一位。而那些前面没有能被丢的数，它们是按照顺序从小到大排序好的。于是我们可以用树状数组处理出在他前面比他大的数个数>=k的数先插到前移k位的位置上，然后剩下的数从小到大插进空位。

　　代码：

#include<cstdio>

#include<algorithm>

#define ll long long

#define maxn 200010

ll read()

{

    ll x=; char f=,c=getchar();

    for(;c<''||''<c;c=getchar())f=(c=='-'?:f);

    for(;''<=c&&c<='';c=getchar())x=x*+c-'';

    return f?x:-x;

}

using namespace std;

int bit[maxn];

struct data{

    int x,id;

}a[maxn];

int rk[maxn],f[maxn],ans[maxn];

int n,k;

bool cmp(data a,data b){return a.x<b.x;}

void add(int x,int k){for(;x<=n;x+=x&(-x))bit[x]+=k;}

int getsum(int x){int sum=; for(;x;x-=x&(-x))sum+=bit[x]; return sum;}

int main()

{

    n=read(); k=read();

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

        a[i].x=read(),a[i].id=i;

    sort(a+,a+n+,cmp);

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

//        printf("%d %d %d\n",i,a[i].x,a[i].id);

    rk[a[].id]=;

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

        if(a[i].x==a[i-].x)rk[a[i].id]=rk[a[i-].id];

        else rk[a[i].id]=i;

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

        add(rk[i],);

        f[i]=getsum(n)-getsum(rk[i]);

        if(f[i]>k)ans[i-k]=a[rk[i]].x;

    }

    int tmp=;

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

        if(f[a[i].id]<=k){

            while(tmp<=n&&ans[tmp])++tmp;

            ans[tmp]=a[i].x;

        }

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

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

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

//        printf("%d %d %d\n",i,rk[i],f[i]);

}

bzoj5170

巴特西

【bzoj5170】Fable（树状数组）

最新文章

热门文章