D.构造数组

D.构造数组

题意：
构造一个长度为n的数组A，构造方式如下：
依次进行n次操作，第i次操作在数组A的index[i]位置处插入整数number[i].
最后从左到右输出数组A的元素
题解：
这道题从前向后考虑是不行的，我们从后向前考虑，最后一个插入的数位置肯定是index[n]，然后倒二插入的位置可能是index[n-1]或index[n-1]+1,显然最后一个数的插入影响的倒二的数的位置，其实就是后面插入的数对前面插入的数的位置产生后移，所以每次只要找x-sum(x)=index[i]就行了，最终位置就是x,用树状数组维护前和就好了。
AC代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define lowbit(x) x&(-x)
#define pb push_back
#define iter set<int>::iterator

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e6+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
ll a[N],b[N],ans[N],tree[N],n;
void add(int x,int y){
    while(x<=n){
        tree[x]+=y;
        x+=lowbit(x);
    }
}
ll sum(int x){
    ll sum=0;
    while(x>0){
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
int find(int x){
    int l=1,r=n;
    while(l<r){
        int mid=(l+r)>>1;
        if(mid-sum(mid)<x)l=mid+1;
        else r=mid;
    }
    return l;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    for(int i=n;i>0;i--){
        int x=a[i];
        int k=find(x);
        add(k,1);
        ans[k]=b[i];
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}