HDU 4302 线段树单点更新，维护区间最大最小值

/**
HDU 4032 线段树单点更新保护区间最小最大值；
题目大意：在x轴上有些点，在接下来的时刻会进行以下操作：在x点处掉下1个馅饼，或吃掉1个离当前距离最小的馅饼，如果距离相同则不转向优先（上次是向右移动，这次也是为不转向）
          若没有馅饼可吃，则呆在原地不动，问最后走的距离是多少。
解题思路：
         线段树保护区间最小最大值便可。
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn=100010;
const int INF=0x3f3f3f3f;

struct node
{
    int l,r;
    int t;
    int minn,maxx;
} tree[maxn*3];

void build(int i,int l,int r)
{
    tree[i].l=l;
    tree[i].r=r;
    tree[i].t=0;
    if(l==r)
    {
        tree[i].minn=INF;
        tree[i].maxx=⑴;
        return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tree[i].maxx=max(tree[i<<1].maxx,tree[i<<1|1].maxx);
    tree[i].minn=min(tree[i<<1].minn,tree[i<<1|1].minn);
}

void add(int i,int t)
{
    if(tree[i].l==t&&tree[i].r==t)
    {
        tree[i].maxx=tree[i].minn=t;
        tree[i].t++;
        return;
    }
    int mid=(tree[i].l+tree[i].r)>>1;
    if(t<=mid)
        add(i<<1,t);
    else
        add(i<<1|1,t);
    tree[i].maxx=max(tree[i<<1].maxx,tree[i<<1|1].maxx);
    tree[i].minn=min(tree[i<<1].minn,tree[i<<1|1].minn);
}

void del(int i,int t)
{
    if(tree[i].l==t&&tree[i].r==t)
    {
        tree[i].t--;
        if(tree[i].t==0)
        {
            tree[i].minn=INF;
            tree[i].maxx=⑴;
        }
        return;
    }
    int mid=(tree[i].l+tree[i].r)>>1;
    if(t<=mid)
        del(i<<1,t);
    else
        del(i<<1|1,t);
    tree[i].maxx=max(tree[i<<1].maxx,tree[i<<1|1].maxx);
    tree[i].minn=min(tree[i<<1].minn,tree[i<<1|1].minn);
}
int query1(int i,int l,int r)
{
    if(tree[i].l==l&&tree[i].r==r)
        return tree[i].maxx;
    int mid=(tree[i].l+tree[i].r)>>1;
    if(r<=mid)
        return query1(i<<1,l,r);
    else if(l>mid)
        return query1(i<<1|1,l,r);
    else
        return max(query1(i<<1,l,mid),query1(i<<1|1,mid+1,r));
}
int query2(int i,int l,int r)
{
    if(tree[i].l==l&&tree[i].r==r)
        return tree[i].minn;
    int mid=(tree[i].l+tree[i].r)>>1;
    if(r<=mid)
        return query2(i<<1,l,r);
    else if(l>mid)
        return query2(i<<1|1,l,r);
    else
        return min(query2(i<<1,l,mid),query2(i<<1|1,mid+1,r));

}
int main()
{
    int T,tt=0;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        build(1,0,n);
        int pre=1,x=0,ans=0;
        while(m--)
        {
            int a,b;
            scanf("%d",&a);
            if(a==0)
            {
                scanf("%d",&b);
                add(1,b);
            }
            else
            {
                int t1=query1(1,0,x);
                int t2=query2(1,x,n);
                if(t1==⑴&&t2!=INF)
                {
                    ans+=t2-x;
                    x=t2;
                    del(1,t2);
                    pre=1;
                }
                else if(t1!=⑴&&t2==INF)
                {
                    ans+=x-t1;
                    x=t1;
                    del(1,t1);
                    pre=⑴;
                }
                else if(t1!=⑴&&t2!=INF)
                {
                    if(x-t1>t2-x)
                    {
                        ans+=t2-x;
                        x=t2;
                        del(1,t2);
                        pre=1;
                    }
                    else if(x-t1<t2-x)
                    {
                        ans+=x-t1;
                        x=t1;
                        del(1,t1);
                        pre=⑴;
                    }
                    else
                    {
                        if(pre==1)
                        {
                            ans+=t2-x;
                            x=t2;
                            del(1,t2);
                            pre=1;
                        }
                        else
                        {
                            ans+=x-t1;
                            x=t1;
                            del(1,t1);
                            pre=⑴;
                        }
                    }
                }
            }
        }
        printf("Case %d: %d
",++tt,ans);
    }
    return 0;
}