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; }