难点在于如何转化问题
假设当前是第k个人 前面的人对我们没有影响,只需要考虑后面的人对我们的影响,所以我们倒序去求
但我们发现不能直接用ask(k[i])去统计插入位置比我们靠前的人,我们的位置也有可能被插入位置靠后的人顶掉
于是我们想到维护位置,当一个位置被占用了就在树状数组里减去,等价于在第k个人时后面的人还没出现在队列里
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 2e5+10;
int p[N],v[N];
int n;
int tr[N];
int mp[N];
inline int lowbit(int x){
return x&-x;
}
void add(int x,int y){
for(;x<=n;x+=lowbit(x))tr[x]+=y;
}
int ask(int x){
int ans = 0;
for(;x;x-=lowbit(x))ans += tr[x];
return ans;
}
void solve(){
memset(mp,0,sizeof(mp));
for(int i=1;i<=n;i++)tr[i]=lowbit(i);
for(int i=1;i<=n;i++){
scanf("%d%d",&p[i],&v[i]);
p[i]++;
}
for(int i=n;i>=1;i--){
int l=1,r=n;
while(l<r){
int mid = (l+r)>>1;
if(ask(mid)<p[i])l=mid+1;
else r=mid;
}
mp[l]=v[i];
add(l,-1);
}
for(int i=1;i<=n;i++)
cout<<mp[i]<<" ";
cout<<endl;
}
int main(){
while(cin>>n)solve();
}
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 2e5+10;
int p[N],v[N];
int n;
int tr[N];
int mp[N];
inline int lowbit(int x){
return x&-x;
}
void add(int x,int y){
for(;x<=n;x+=lowbit(x))tr[x]+=y;
}
int ask(int x){
int ans = 0;
for(;x;x-=lowbit(x))ans += tr[x];
return ans;
}
void solve(){
memset(mp,0,sizeof(mp));
for(int i=1;i<=n;i++)tr[i]=lowbit(i);
for(int i=1;i<=n;i++){
scanf("%d%d",&p[i],&v[i]);
}
int q = log2(n);
for(int i=n;i;i--){
int ans = 0,sum = 0;
for(int j=q;j>=0;j--){
int tmp = 1<<j;
if(ans+tmp<=n && sum + tr[ans+tmp]<=p[i]){
ans+=tmp;sum+=tr[ans];
}
}
add(ans+1,-1);
mp[ans+1]=v[i];
}
for(int i=1;i<=n;i++)
cout<<mp[i]<<" ";
cout<<endl;
}
int main(){
while(cin>>n)solve();
}
请问ans为什么要+1