Tag:线段树 思维 树状数组
Category:数据结构
Article From:https://www.cnblogs.com/nervendnig/p/9124275.html

meaning of the title

A length $n< =1e5$’s number axis, $m< =1e5$operation.

There are two kinds of operations

$0$  $x$ Put a food in $x$

$1$ A worm eats the nearest food. If there are two foods near, do not eat in the direction.

The worm begins at $0$, and it doesn’t eat.

How far is the end of the worm?

 

The solution:

Using arrays to maintain a few foods at each site.

Using tree arrays to maintain the number axis interval, each time for the left and right between the two regions, find the nearest point and get the minimum value.

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

  

Leave a Reply

Your email address will not be published. Required fields are marked *