一開始实在是不知道怎么做，后来经过指导，猛然发现，仅仅须要记录某个区间内是否有值就可以。
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<l||ll>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<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<stack>
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 110000
int 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||l>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<l||ll>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<<ll<<" "<<rr<<" "<<l<<" "<<r<<" "<<flag[rt]<<endl;if(rr<l||ll>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<<l<<" "<<r<<endl;if(l>=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=l;f=1;}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;
}
