poj 2828逆シーケンスのセグメントツリー

1458 ワード

なぜ先に後ろから行うのかというと、最後に挿入する位置は変わらないので、最初に挿入する点は後ろの点の挿入によって後ろに移動する可能性があるので、先に後ろの店面から行います
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=222222;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[maxn<<2];
int id;
int a[maxn];
void PushUp(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){
    sum[rt]=r-l+1;
    if(l==r) return ;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}

void update(int p,int l,int r,int rt){

    if(l==r){
        sum[rt]--;
        id=l;
        return ;
    }
    int m=(l+r)>>1;
    if(p<=sum[rt<<1]) update(p,lson);
    else update(p-sum[rt<<1],rson);
    PushUp(rt);
}
int b[maxn];
int val[maxn];
int main(){
    //freopen("aaa.txt","r",stdin);
    int n;
    while(cin>>n){
        build(1,n,1);

        for(int i=0;i<n;i++)
            scanf("%d%d",&b[i],&val[i]);
        for(int i=n-1;i>=0;i--){
            // 
            update(b[i]+1,1,n,1);
            a[id]=val[i];
            //cout<<"id:"<<id<<" val:"<<val[i]<<endl;
        }

        for(int i=1;i<=n;i++) printf("%d ",a[i]);
        puts("");

    }
    return 0;
}