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]);

补充：软件开发 , Java ,