Holedox Eating
Problem Description
Holedox在一条长度为L的线上. Holedox能在线上移动，线上会时不时的出现蛋糕（保证是整点）。Holedox会在想吃蛋糕时去最近的有蛋糕的点吃，如果左右的最近蛋糕与它的距离相等，它会按上一次行走的方向，如果没有蛋糕，它会呆在原地。
Input
第一行为数据组数T (1 <= T <= 10)
对每组数据，第一行有2个整数L,n(1<=L,n<=100000)表示线段长度和事件数。
接下来n行，每行一个事件：‘0 x'表示在x的位置出现一块蛋糕，’1‘表示Holedox去吃1块蛋糕
Holedox一开始在0点。
Output
对每组数据，输出一行‘Case i: dis',dis表示Holedox的移动距离。
Sample Input
3 10 8 0 1 0 5 1 0 2 0 0 1 1 1 10 7 0 1 0 5 1 0 2 0 0 1 1 10 8 0 1 0 1 0 5 1 0 2 0 0 1 1
Sample Output
Case 1: 9 Case 2: 4 Case 3: 2
这题是单点修改+区间最值的zkw线段树（a[]表示数量）
这题有几个技巧：
1.线段树多开；
2.'0'点的包含（把所有数字+1，显然不影响Holedox的移动距离）
3.额外信息的记录（为了把这题转换成线段树）
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
using namespace std;
#define MAXT (10+10)
#define MAXN (100000+10)
#define MAXm (100000+10)
#define INF (2139062143)
int n,m,M,T,now,direction,ans;
int t[2][MAXN*10]; //0->max 1->min
int a[MAXN];
void dec(int x)
{
a[x]--;
if (a[x]==0)
{
x+=M;
t[0][x]=0;t[1][x]=INF;
for (x>>=1;x;x>>=1)
{
t[0][x]=max(t[0][x<<1],t[0][(x<<1)^1]);
t[1][x]=min(t[1][x<<1],t[1][(x<<1)^1]);
}
}
}
void go_left(int Lans)
{
ans+=now-Lans;
now=Lans;direction=-1;
dec(now);
}
void go_right(int Rans)
{
ans+=Rans-now;
now=Rans;direction=1;
dec(now);
}
int main()
{
freopen("Holding.in","r",stdin);
scanf("%d",&T);
for (int k=1;k<=T;k++)
{
memset(t[0],0,sizeof(t[0]));ans=0;
memset(t[1],127,sizeof(t[1]));
memset(a,0,sizeof(a));now=1;direction=1; //1->right -1->left
scanf("%d%d",&n,&m);n+=2;
M=1;while (M-2<n) M<<=1;
for (int i=1;i<=m;i++)
{
int p1,p2;
scanf("%d",&p1);
if (p1==0)
{
scanf("%d",&p2);p2+=1;
a[p2]++;
if (a[p2]==1)
{
p2+=M;t[0][p2]=t[1][p2]=p2-M;
int p=p2;
for (p>>=1;p;p>>=1) t[0][p]=max(t[0][p<<1],t[0][(p<<1)^1]);
for (p2>>=1;p2;p2>>=1) t[1][p2]=min(t[1][p2<<1],t[1][(p2<<1)^1]);
}
}
else
{
//(0,now+1)->[1,now]
int l=M,r=now+1+M,Lans=0,Rans=INF;
while (l^r^1)
{
if (~l&1) Lans=max(Lans,t[0][l+1]);
if (r&1) Lans=max(Lans,t[0][r-1]);
l>>=1;r>>=1;
}
//(now-1,n)->[now,n-1]
l=now-1+M;r=n+M;
while (l^r^1)
{
if (~l&1) Rans=min(Rans,t[1][l+1]);
if (r&1) Rans=min(Rans,t[1][r-1]);
l>>=1;r>>=1;
}
if (Lans==0&&Rans==INF) continue;
else if (Lans==0) go_right(Rans);
else if (Rans==INF) go_left(Lans);
else if (now-Lans<Rans-now) go_left(Lans);
else if (now-Lans>Rans-now) go_right(Rans);
else if (now-Lans==0) dec(now);
else if (direction==1) go_right(Rans);
else go_left(Lans);
}
/*
for (int j=1;j<=M*2;j++) if (t[0][j]) cout<<j<<":"<<t[0][j]<<' ';
cout<<endl;
for (int j=1;j<=M*2;j++) if (t[1][j]<INF) cout<<j<<":"<<t[1][j]<<' ';
cout<<endl;
*/
}
printf("Case %d: %dn",k,ans);
}
return 0;
}
