Holedox Eating HDU - 4302 2012多校C 二分查找+树状数组/线段树优化

题意

一个长度$n<=1e5$的数轴,$m<=1e5$个操作

有两种一些操作

$0$ $x$ 在$x$放一个食物

$1$ 一个虫子去吃最近的食物,如果有两个食物一样近,不转变方向的去吃

虫子一开始在$0$点,没吃的就不动

求最终虫子跑了多远?

解法:

用数组维护每个地点有几个食物,

用树状数组维护数轴区间和,每次对于左右进行二分区间求和,找到左右最近的那个点,取最小值即可

#include <bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pp pair<int,int>
#define rep(ii,a,b) for(int ii=a;ii<=b;ii++)
#define per(ii,a,b) for(int ii=a;ii>=b;ii--)
#define show(x) cout<<#x<<"="<<x<<endl
#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define showa(a,b) cout<<#a<<'['<<#b<<"]="<<a[b]<<endl
using namespace std;
const int maxn=1e5+10;
const int maxm=1e6+10;
const int INF=0x3f3f3f3f;
int casn,n,m,k;
#define lb(x) (x&(-x))
int bt[maxn];
inline void upd(int pos,int x){
  while(pos<=n)
    bt[pos]+=x,pos+=lb(pos);
}
inline int psum(int pos,int sum=0){
  while(pos)
    sum+=bt[pos],pos-=lb(pos);return sum;
}
inline int rsum(int l,int r){
//  show2(l,r);
  return psum(r)-psum(l);
}

int main(){
//#define test
#ifdef test
  freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endif
IO;
  cin>>casn;
  int t=0;
  while(casn--){
    int ans=0;
    cin>>n>>m;
    n++;
    memset(bt,0,sizeof bt);
    int pos=1,dir=1;
    for(int i=0;i<m;i++){
      int a,b;
      cin>>a;
      if(a==0){
        cin>>b;
        b++;
       upd(b,1);
      }else {
        if(rsum(pos-1,pos)){
          upd(pos,-1);
//          show(1);
        }else {
          int l=1,r=pos-1;
          int x1=INF,x2=INF;
          if(pos>1&&rsum(0,pos)!=0){
              while(l<r){
              int mid=(l+r)>>1;
              if(rsum(mid,pos)>0){
                l=mid+1;
              }else r=mid;
            }
            x1=pos-l;
          }
          if(pos<n&&rsum(pos,n)){
            l=pos+1,r=n;
            while(l<r){
              int mid=(l+r)>>1;
              if(rsum(pos,mid)>0){
                r=mid;
              }else l=mid+1;
            }
            x2=l-pos;
          }
        if(x1==x2&&x1==INF){
//            show(1);
          continue;
        }
        if(x1==x2){
          ans+=x1;
          pos+=dir*x1;
          upd(pos,-1);
        }else {
          ans+=min(x1,x2);
          if(x1<x2){
            pos-=x1;
            dir=-1;
            upd(pos,-1);
          }else{
            pos+=x2;
            dir=1;
            upd(pos,-1);
          }
        }
//        show2(x1,x2);
        }
      }
//      show(ans);
    }
    cout<<"Case "<<++t<<": ";
    cout<<ans<<endl;
  }



#ifdef test
  fclose(stdin);fclose(stdout);system("out.txt");
#endif
  return 0;
}