一開始实在是不知道怎么做，后来经过指导，猛然发现，仅仅须要记录某个区间内是否有值就可以。
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
",cas,sum);
}
return 0;
}