线段树

找到第a个空位 插入

线段树nlogn

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<set>
#include<string>
#include<map>

using namespace std;
typedef long long LL;

#define inf  2000000000
#define MAXN 200010

struct node
{
    int l,r,w;
}tree[MAXN<<2];
int x[MAXN];

void Build(int l,int r,int a)
{
    tree[a].l=l;
    tree[a].r=r;
    tree[a].w=r-l+1;
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    Build(l,mid,a<<1);
    Build(mid+1,r,a<<1|1);
}

void Insert(int l,int r,int w,int num,int a)
{
    printf("%d %d
",l,r);
    if(l==r)
    {
        printf("%d
",l);
        tree[a].w=0;
        x[l]=num;
        return ;
    }
    int mid=(l+r)>>1;
    if(tree[a<<1].w>=w)
        Insert(l,mid,w,num,a<<1);
    else
        Insert(mid+1,r,w-tree[a<<1].w,num,a<<1|1);
    tree[a].w=tree[a<<1].w+tree[a<<1|1].w;
}

int main()
{
    int n;
    scanf("%d",&n);
    Build(1,n,1);
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int a;
        scanf("%d",&a);
        Insert(1,n,a,i,1);
    }
    for(int i=1;i<=n;i++)
        printf("%d ",x[i]);
    return 0;
}
/*
10
5
2 3 4 5 1

*/