【JZOJ 5456】【NOIP2017提高A组冲刺11.6】奇怪的队列 (线段树)

问题描述
nodgd的粉丝太多了，每天都会有很多人排队要签名。
今天有��个人排队，每个人的身高都是一个整数，且互不相同。很不巧，nodgd今天去忙别的事情去了，就只好让这些粉丝们明天再来。同时nodgd提出了一个要求，每个人都要记住自己前面与多少个比自己高的人，以便于明天恢复到今天的顺序。
但是，粉丝们或多或少都是有些失望的，失望使她们晕头转向、神魂颠倒，已经分不清楚哪一边是“前面”了，于是她们可能是记住了前面比自己高的人的个数，也可能是记住了后面比自己高的人的个数，而且他们不知道自己记住的是哪一个方向。
nodgd觉得，即使这样明天也能恢复出一个排队顺序，使得任意一个人的两个方向中至少有一个方向上的比他高的人数和他记住的数字相同。可惜��比较大，显然需要写个程序来解决，nodgd很忙，写程序这种事情就交给你了。
输入
第一行输入一个整数��，表示指令的条数。
接下来��行，每行两个整数����,����，表示一个人的身高和她记住的数字，保证身高互不相同。
输出
输出一行，这个队列里从前到后的每个人的身高。如果有多个答案满足题意，输出字典序最小。如果不存在满足题意的排列，输出“impossible”（不含引号）。
样例输入
输入1：
4
4 1
3 1
6 0
2 0
输入2：
6
1 5
8 0
3 1
4 0
2 0
6 0
样例输出
输出1：
2 4 3 6
输出2：
1 2 4 3 6 8
算法讨论

#include <cstdio>
#include <algorithm>
#define MAX_N 100006
using namespace std;
struct arr
{
    int a,b,c;
}a[MAX_N];
struct arrr
{
    int l,r,w;
}t[MAX_N*4];
int ta[MAX_N],n,m;

bool cmp(arr x,arr y)
{
    return x.a<y.a;
}

int min(int x,int y)
{
    return x<y?x:y;
}

void build(int p,int l,int r)
{
    t[p].l=l; t[p].r=r;
    if (l==r)
    {
        t[p].w=1;
        return;
    }
    int mid=(l+r) / 2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].w=t[p*2].w+t[p*2+1].w;
}

void find(int p,int l,int r,int k)
{
    if (l==r)
    {
        m=l;
        return;
    }
    int mid=(l+r) / 2;
    if (t[p*2].w>=k)
        find(p*2,l,mid,k);
    else
        find(p*2+1,mid+1,r,k-t[p*2].w);
}

void del(int p,int x)
{
    if (t[p].l==t[p].r)
    {
        t[p].w--;
        return;
    }
    int mid=(t[p].l+t[p].r) / 2;
    if (x<=mid)
        del(p*2,x);
    else
        del(p*2+1,x);
    t[p].w=t[p*2].w+t[p*2+1].w;
}

int main()
{
    freopen("queue.in","r",stdin);
    freopen("queue.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&a[i].a,&a[i].b);
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++)
    {
        a[i].c=n-i;
        if (a[i].c<a[i].b)
        {
            printf("impossible");
            fclose(stdin); fclose(stdout);
            return 0;
        }
    }
    build(1,1,n);
    for (int i=1;i<=n;i++)
    {
        find(1,1,n,min(a[i].b+1,a[i].c-a[i].b+1));
        ta[m]=a[i].a;
        del(1,m);
    }
    for (int i=1;i<=n;i++)
        printf("%d ",ta[i]);
    fclose(stdin); fclose(stdout);
}