daily 1

2023/3/24 daily

今天又只做了一题，因为熬夜面阿里，把我搞的浑身难受，明天绝对要恢复333333333

CF 900C

树状数组+思维

一个数如果前面有i-2个数比他小，那么删除那个最大的，可以多获得一个record

如果i-1个数比他小，那么删除最大的，会减少一条记录，我们遍历一下就好了

#define lowbit(x) x&-x
void solve(){
  int n;
  cin>>n;
  vector<int>a(n);
  for(int i=0;i<n;++i){
    cin>>a[i];
  }
  vector<int>tree(n+1);
  auto add=[&](int x,int v){
    while(x<=n){
        tree[x]+=v;
        x+=lowbit(x);
    }
  };
  auto sum=[&](int x){
    ll ans=0;
    while(x){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
  };
  int maxx=0,ans=-1;
  vector<int>cnt(n+1);
  for(int i=0;i<n;++i){
    maxx=max(a[i],maxx);
    int res=sum(a[i]);
    if(res==i-1){
        cnt[maxx]++;
    }else if(res==i){
        cnt[maxx]--;
    }
    add(a[i],1);
  }
  int ansi=1;
  for(int i=1;i<=n;++i){
    if(cnt[i]>ans){
        ans=cnt[i];
        ansi=i;
    }
  }
  cout<<ansi<<'\n';
  return;
}

LOADING

daily 1