#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 1e4;
int a[N],b[N];
int n;
template <class T>
struct BIT
{
T c[N];
int sz;
void init(int s)
{
sz = s;
for(int i=1;i<=sz;++i) c[i] = 0;
}
T lowbit(int x)
{
return x&-x;
}
T sum(int x)
{
assert(x <= sz);
T res=0;
while(x) res+=c[x],x-=lowbit(x);
return res;
}
T query(int L, int R)
{
return sum(R) - sum(L-1);
}
void update(int x,int y)
{
assert(x != 0);
while(x<=sz) c[x]+=y,x+=lowbit(x);
}
};
BIT<int> A;
void solve()
{
cin>>n;
A.init(n);
for(int i=2;i<=n;++i) cin>>a[i];
b[n] = a[n]+1;
A.update(b[n],1);
for(int i=n-1;i;--i)
{
int L = 0, R = n+1;
while(L+1<R)
{
int M = (L+R)/2;
//M-1为前面至多有多少小于M,-A.sum(M-1)是后面出现过的数
if(M-1-A.sum(M-1)<=a[i]) L = M;
else R = M;
}
b[i] = L;
A.update(b[i],1);
}
for(int i=1;i<=n;++i) cout<<b[i]<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin>>T;
while(T--)
{
solve();
}
}
标签:typedef,vector,Lost,int,unsigned,long,USACO03Open,Cows
From: https://www.cnblogs.com/ruoye123456/p/18440446