HDU4302 Holedox Eating(单点修改&&最大值最小值查询）

题目大意

给定一个长为L的水管，可以进行以下两种操作，小动物初始位置为0：

1、在位置a的水管处添加一个食物

2、让小动物吃掉一个离它最近的食物，如果左右两个方向离它最近的食物的距离相等，则选择与它朝向相同的方向的食物吃掉

题解

操作一就是单点修改，对于操作二，维护一个区间最大值和最小值，然后每次查询小动物左边的最大值和右边的最小值，然后进行选择，有一个坑爹的地方就是如果没有食物吃则呆在原地不动

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson l,m,s<<1
#define rson m+1,r,s<<1|1
#define MAXN 100005
#define INF 1000000
using namespace std;
int sumv[MAXN<<2],maxv[MAXN<<2],minv[MAXN<<2];
int L,mins,maxs;
void PushUp(int s)
{
    maxv[s]=max(maxv[s<<1],maxv[s<<1|1]);
    minv[s]=min(minv[s<<1],minv[s<<1|1]);
}
void build(int l,int r,int s)
{
    sumv[s]=0;
    maxv[s]=-INF;
    minv[s]=INF;
    if(l==r)
        return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void update(int p,int l,int r,int s,int d)
{
    if(l==r)
    {
        sumv[s]+=d;
        if(sumv[s])
        {
            maxv[s]=r;
            minv[s]=r;
        }
        else
        {
            maxv[s]=-INF;
            minv[s]=INF;
        }
        return;
    }
    int m=(l+r)>>1;
    if(p<=m) update(p,lson,d);
    else update(p,rson,d);
    PushUp(s);
}
void query(int ql,int qr,int l,int r,int s)
{
    if(ql<=l&&r<=qr)
    {
        mins=min(mins,minv[s]);
        maxs=max(maxs,maxv[s]);
        return;
    }
    int m=(l+r)>>1;
    if(ql<=m) query(ql,qr,lson);
    if(qr>m)   query(ql,qr,rson);
}
int main(void)
{
    int T,n,a,b,t,dr,p=0,total;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&L,&n);
        total=0;
        build(0,L,1);
        t=0;
        dr=1;
        while(n--)
        {
            scanf("%d",&a);
            if(!a)
            {
                scanf("%d",&b);
                update(b,0,L,1,1);
            }
            else
            {
                int dmax=-INF,dmin=INF;
                mins=INF;
                maxs=-INF;
                query(0,t,0,L,1);
                dmax=maxs;
                if(t==dmax)
                {
                    update(t,0,L,1,-1);
                    continue;
                }
                mins=INF;
                maxs=-INF;
                query(t+1,L,0,L,1);
                dmin=mins;
                if(dmax==(-INF)&&dmin==INF) continue;
                if(t-dmax<dmin-t)
                {
                    dr=-1;
                    total+=(t-dmax);
                    t=dmax;
                    update(t,0,L,1,-1);
                }
                else if(t-dmax==dmin-t)
                {
                    if(dr==1)
                    {
                        total+=dmin-t;
                        t=dmin;
                        update(t,0,L,1,-1);

                    }
                    else
                    {
                        total+=t-dmax;
                        t=dmax;
                        update(t,0,L,1,-1);
                    }
                }
                else
                {
                    total+=dmin-t;
                    dr=1;
                    t=dmin;
                    update(t,0,L,1,-1);
                }
            }
        }
        printf("Case %d: %d\n",++p,total);
    }
    return 0;
}