pku 2182 线段树 从逆序数到数列.txt

NUAA ACM OJ源码

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

//PKU 2182 线段树 从逆序数到数列 
#define PI 3.1415926
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back
#define NMAX 8050

typedef struct ooptree
{
    int left;
    int right;
    int value;//value为-1，是非叶子结点，>=1,为叶子结点的值
    int sum;//子树（包括自己）含有的未出现的数
}ooptree;

ooptree tree[NMAX*3];
int a[NMAX];
int ans[NMAX];

void build(int p,int l,int r)
{
    tree[p].left=l;
    tree[p].right=r;
    if(r-l>=1) tree[p].value=-1;
    else tree[p].value=r;
    tree[p].sum=r-l+1;
    if(r-l>=1)
    {
        build(2*p,l,(l+r)/2);
        build(2*p+1,(l+r)/2+1,r);
    }
}

int find(int k)
{//查找已有元素中第K大的数
    int p=1;
    while(tree[p].value==-1)
    {
        if(k<=tree[2*p].sum) p=2*p;
        else {k-=tree[2*p].sum; p=2*p+1;}
    }
    return p;//注意返回的是结点号
}

void del(int p)
{
    while(p>=1) { tree[p].sum--; p=p/2;}
}

void print_tree()
{
     int i;
     for(i=1;i<=7;i++) 
     {
        printf("(%d,%d)",tree[i].value,tree[i].sum);
        if(i==1 || i==3 || i==7) printf("\n");                  
     }
}
void solve(int num)
{
    int i,p;
    build(1,1,num);
    for(i=num-1;i>=1;i--)
    {
     p=find(a[i]+1);
     ans[i+1]=tree[p].value;
     del(p);
    }
    p=find(1);
    ans[1]=tree[p].value;
    del(p);
    for(i=1;i<=num;i++) printf("%d\n",ans[i]);
}

int main()
{
    int i,num;
    scanf("%d",&num);
    for(i=1;i<=num-1;i++) scanf("%d",&a[i]);
    solve(num);
    return 0;
}