一開始实在是不知道怎么做，后来经过指导，猛然发现，仅仅须要记录某个区间内是否有值就可以。

flag[i]:代表i区间内，共同拥有的蛋糕数量。

放置蛋糕的时候非常好操作，单点更新。

ip：老鼠当前的位置

寻找吃哪一个蛋糕的时候：

1，要寻找0-ip这个区间内，位置最大的一个蛋糕的位置，记为ll。

2，要寻找ip-n这个区间内，位置最小的一个蛋糕的位置，记为rr。

找到ll，rr之后，就能够依据ll，rr跟ip的关系来确定该吃ll还是rr了。

怎样寻找ll呢？

假设在某个区间的右半边区间找到了一个数，那么，这个区间的左半边区间肯定就不用寻找了。

假设这个区间的大小为1，那么这个区间内须要的数就肯定是这个数了。

假设某个区间的flag为0，那么这个区间肯定不存在蛋糕。

假设某个区间不包括0-ip，那么这个区间也肯定找不到ll。

于是，我们写出了寻找ll的函数：

int query(int ll,int rr,int l,int r,int rt){    if(rr
     
      r)return -INF;    if(flag[rt]==0)return -INF;    if(l==r)    {        if(flag[rt])return l;        else return -INF;    }    int ans=-INF;    ans=query(ll,rr,rson);    if(ans==-INF)ans=query(ll,rr,lson);    return ans;}
     

寻找rr的原理与寻找ll的原理同样。

整体代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define INF 99999999#define lmin 0#define rmax n#define lson l,(l+r)/2,rt<<1#define rson (l+r)/2+1,r,rt<<1|1#define root lmin,rmax,1#define maxn 110000int flag[maxn*4];void push_up(int rt){ flag[rt]=flag[rt<<1]+flag[rt<<1|1];}void push_down(int rt){}void creat(int l,int r,int rt){ flag[rt]=0; if(l!=r) { creat(lson); creat(rson); }}void update(int st,int x,int l,int r,int rt){ if(r
           
            st)return; if(l==r&&l==st) { flag[rt]+=x; return; } update(st,x,lson); update(st,x,rson); push_up(rt);}int query(int ll,int rr,int l,int r,int rt){ if(rr
            
             r)return -INF; if(flag[rt]==0)return -INF; if(l==r) { if(flag[rt])return l; else return -INF; } int ans=-INF; ans=query(ll,rr,rson); if(ans==-INF)ans=query(ll,rr,lson); return ans;}int query1(int ll,int rr,int l,int r,int rt){ // cout<
             
              <<" "<
              
               <<" "<
               
                <<" "<
                
                 <<" "<
                 
                  <
                  
                   r)return INF; if(flag[rt]==0)return INF; if(l==r) { if(flag[rt])return l; else return INF; } int ans=INF; ans=query1(ll,rr,lson); if(ans==INF)ans=query1(ll,rr,rson); return ans;}int main(){ int cas,T; int n,m; int l,r,mid; int k,a,b,c; int m1,m2; scanf("%d",&T); cas=0; while(T--) { cas++; int sum=0; scanf("%d%d",&n,&m); creat(root); int ip=0; int f=0; while(m--) { scanf("%d",&k); if(k==1) { int l=query(0,ip,root); int r=query1(ip,n,root); // cout<
                   
                    <<" "<
                    
                     <
                     
                      =0||r<=n) { int ll=ip-l; int rr=r-ip; if(ll==rr&&f==1)mid=l; else if(ll==rr&&f==0)mid=r; else if(ll
                      
                       rr) { mid=r; f=0; } int cha=mid-ip; if(cha<0)cha=-cha; sum+=cha; ip=mid; update(mid,-1,root); } } else { scanf("%d",&a); update(a,1,root); } } printf("Case %d: %d\n",cas,sum); } return 0;}