HDU 4302(zkw线段树-单点修改区间最值）

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.额外信息的记录（为了把这题转换成线段树）

[cpp]
#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; 
                }  www.2cto.com
                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: %d\n",k,ans); 
         
    } 
    return 0; 
}