BZOJ 5170: Fable

离散化+树状数组

求当前位之前是否有k位比它大

这样的话它就需要前移k位

剩下的按照原来的顺序依次填入

其实我觉得sort一下就可以做出来了

太久没写树状数组了

所以写了一下树状数组

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2000005;
int n, k;
int bit[maxn];
struct data{
    int x,id;
}a[maxn];
int rk[maxn],f[maxn],ans[maxn];

inline int lowbit(int x){return x & (-x);}
bool cmp(data a, data b){return a.x < b.x;}

void add(int pos, int x)
{
    if(pos < 1) return;
    while(pos <= n){
        bit[pos] += x;
        pos += lowbit(pos);
    }
}

int query(int pos)
{
    int ret = 0;
    while(pos >= 1){
        ret += bit[pos];
        pos -= lowbit(pos);
    }
    return ret;
}

int main()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i].x);
        a[i].id = i;
    }
    sort(a+1,a+n+1,cmp);

    rk[a[1].id]=1;

    for(int i=2;i<=n;i++)
        if(a[i].x==a[i-1].x)rk[a[i].id]=rk[a[i-1].id];
        else rk[a[i].id]=i;

    for(int i=1;i<=n;i++){
        add(rk[i],1);
        f[i]=query(n)-query(rk[i]);
        if(f[i]>k)ans[i-k]=a[rk[i]].x;
    }
    int tmp=1;
    for(int i=1;i<=n;i++)
        if(f[a[i].id]<=k){
            while(tmp<=n&&ans[tmp])++tmp;
            ans[tmp]=a[i].x;
        }
    for(int i=1;i<=n;i++)
        printf("%d
",ans[i]);
    return 0;
}