AcWing 1242. 修改数组(树状数组+二分)
原题链接
中等
//找到第一个比自己大且没有出现过的数字
#include <iostream>
using namespace std;
const int N=2e6+1;
int a[N];
int lowbit(int x){
return x&(-x);
}
void add(int x,int v){
for(int i=x;i<N;i+=lowbit(i)){
a[i]+=v;
}
return ;
}
int query(int x){
int sum=0;
for(int i=x;i;i-=lowbit(i)){
sum+=a[i];
}
return sum;
}
int main(){
int n; cin>>n;
for(int i=0;i<n;i++){
int x; cin>>x;
int l=x,r=N,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(query(mid)-query(x-1)<(mid-x+1)){
ans=mid; r=mid-1;
}
else l=mid+1;
}
add(ans,1);
cout<<ans<<" ";
}
return 0;
}
check函数真的巧妙
orz
太妙了
妙哉妙哉
orz