题意
一个长度$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;
}