**题意：

      一条蛇生活在一个管子里，然后管子上面的某些位置会一次出现食物，每次蛇都会吃最近的食物，吃完之后就原地不动，等待下一次吃食物，如果有两个食物距离蛇一样远并且都是最近的，那么蛇不会掉头，而是直接按他最后停留的方向走，去吃自己前方的食物，最后给一些命令，问蛇一共走了多少路。

思路：
**

看完一下就想到了set,结果果断用set过了，后来听说这个题目可以用线段树来做，自己想了下，用线段树也不是很难，结果又写了个线段树，也AC了，set用时359ms，线段树用了515ms，无论是哪个方法，这个题目就是要迅速的找到比当前值大的最小的那个数，和比当前值小的最大的那个数（或者当前值本身），如果是找大于等于的第一个数在set里可以直接 *my_set.lower_bound(now);,如果是小于等于也用同样的方法，只不过是吧所有的数都存成负数就行了，对于线段树也比较好写，每个节点有两个权值，一个是当前区间的最大值，一个是最小值，然后就是简单的更新和查找了，要有一个就是这个题目同一个点可能同时存在多个食物，所以开个数组记录每个节点的食物个数，吃了就--，如果是0就直接删除就行了，具体的看代码。

SET 359ms

#include
#include

#define INF 1000000000
using namespace std;

setlow ,up; int num[110000**];

int** abss(int x) { return x < 0 ? -x : x**;
}

int main ()
{
int** t ,n ,m; int a ,b ,cas = 1;
scanf("%d" ,&t); while(t--) {
scanf("%d %d" ,&n ,&m);
low.clear() ,up.clear();
memset(num ,0 ,sizeof(num));
up.insert(INF);
low.insert(INF); int now = 0; int sum = 0; int fx = 1; while(m--) {
scanf("%d" ,&a); if(!a) {
scanf("%d" ,&b);
up.insert(b);
low.insert(-b);
num[b] ++; } else {
a = *up.lower_bound(now);
b = *low.lower_bound(-now); if(b != INF) b = -b; if(a == INF && b == INF) continue; if(!abss(a - now)) { if(!--num[a])
up.erase(a) ,low.erase(-a); continue; } if(!abss(b - now)) { if(!--num[b])
up.erase(b) ,low.erase(-b**);
continue;
}

         if(**abss**(**a **-** now**) <** abss**(**b **-** now**))  
         {**  
            sum **+=** abss**(**a **-** now**);  
            if(**now **<** a**)** fx **=** 1**;  
            else** fx **=** 2**;**  
            now **=** a**;  
           if(!--**num**\[**a**\])**  
           up**.**erase**(**a**) ,**low**.**erase**(-**a**);  
         }  
         else if(**abss**(**a **-** now**) >** abss**(**b **-** now**))  
         {**  
            sum **+=** abss**(**b **-** now**);  
            if(**now **<** b**)** fx **=** 1**;  
            else** fx **=** 2**;**  
            now **=** b**;  
            if(!--**num**\[**b**\])**  
            up**.**erase**(**b**) ,**low**.**erase**(-**b**);  
         }  
         else  
         {**  
             sum **+=** abss**(**a **-** now**);  
             if(**fx **==** 1 **&&** now **<** a **||** fx **==** 2 **&&** now **>** a**)  
             {**  
                 now **=** a**;  
                 if(!--**num**\[**a**\])**  
                 up**.**erase**(**a**) ,**low**.**erase**(-**a**);  
             }  
             else  
             {**  
                 now **=** b**;  
                if(!--**num**\[**b**\])**  
                up**.**erase**(**b**) ,**low**.**erase**(-**b**);

             }  
         }  
      }  
   }**  
   printf**(**"Case %d: %d\\n" **,**cas **++ ,**sum**);  
}  
return** 0**;  

}**

字典树 515ms

#include
#include

#define lson l ,mid ,t << 1
#define rson mid + 1 ,r ,t << 1 | 1
#define INF 100000000
int max[440000] ,min[440000]; int num[110000**];

int** maxx(int x ,int y) { return x > y ? x : y**;
}

int** minn(int x ,int y) { return x < y ? x : y**;
}

int** abss(int x) { return x < 0 ? -x : x**;
}

void** Pushup(int t) {
max[t] = maxx(max[t<<1] ,max[t<<1|1]);
min[t] = minn(min[t<<1] ,min[t<<1|1**]);
return ;
}

void** BuidTree(int n) { for(int i = 1 ;i <= n * 4 ;i ++)
max[i] = -INF ,min[i] = INF;
memset(num ,0 ,sizeof(num**));
return;
}

void** Update(int l ,int r ,int t ,int a ,int b ,int c) { if(l == r) {
max[t] = b ,min[t] = c; return ; } int mid = (l + r) >> 1; if(a <= mid) Update(lson ,a ,b ,c); else Update(rson ,a ,b ,c);
Pushup(t**);
return ;
}

int** Query_max(int l ,int r ,int t ,int a ,int b) { if(a <= l && b >= r) return max[t]; int mid = (l + r) >> 1; int ans = 0; if(a <= mid) ans = Query_max(lson ,a ,b); if(b > mid) ans = maxx(ans ,Query_max(rson ,a ,b)); return ans**;
}

int** Query_min(int l ,int r ,int t ,int a ,int b) { if(a <= l && b >= r) return min[t]; int mid = (l + r) >> 1; int ans = INF; if(a <= mid) ans = Query_min(lson ,a ,b); if(b > mid) ans = minn(ans ,Query_min(rson ,a ,b)); return ans**;
}

int main ()
{
int** t ,m ,n ,i ,a ,b ,sum ,now ,fx ,cas = 1;
scanf("%d" ,&t); while(t--) {
scanf("%d %d" ,&n ,&m);
n++ ,now = 1 ,sum = 0 ,fx = 1;
BuidTree(n); while(m--) {
scanf("%d" ,&a); if(!a) {
scanf("%d" ,&b);
num[++b] ++; if(num[b] == 1)
Update(1 ,n ,1 ,b ,b ,b**);
continue;
}

       if(**num**\[**now**\])  
       {**  
           sum **+=** 0**;  
           if(!--**num**\[**now**\])**  
           Update**(**1 **,**n **,**1 **,**now **,-**INF **,**INF**);  
           continue;  
       }

       if(**now **==** 1**)** a **= -**INF**;  
       else** a **=** Query\_max**(**1 **,**n **,**1 **,**1 **,**now **-** 1**);  
       if(**now **==** n**)** b **=** INF**;  
       else** b **=** Query\_min**(**1 **,**n **,**1 **,**now **+** 1 **,**n**);  
       if(**a **== -**INF **&&** b **==** INF**) continue;

       if(**abss**(**a **-** now**) <** abss**(**b **-** now**))  
       {**  
           sum **+=** abss**(**a **-** now**);**  
           fx **=** a **<** now **?**  1 **:**  2**;**  
           now **=** a**;  
           if(!--**num**\[**now**\])**  
           Update**(**1 **,**n **,**1 **,**now **,-**INF **,**INF**);  
       }  
       else if(**abss**(**a **-** now**) >** abss**(**b **-** now**))  
       {**  
           sum **+=** abss**(**b **-** now**);**  
           fx **=** b **<** now **?**  1 **:**  2**;**  
           now **=** b**;  
           if(!--**num**\[**now**\])**  
           Update**(**1 **,**n **,**1 **,**now **,-**INF **,**INF**);  
       }  
       else  
       {**  
           sum **+=** abss**(**a **-** now**);  
           if(**fx **==** 1 **&&** a **<** now **||** fx **==** 2 **&&** a **>** now**)  
           {**  
               now **=** a**;  
               if(!--**num**\[**now**\])**  
               Update**(**1 **,**n **,**1 **,**now **,-**INF **,**INF**);  
           }  
           else  
           {**  
               now **=** b**;  
               if(!--**num**\[**now**\])**  
               Update**(**1 **,**n **,**1 **,**now **,-**INF **,**INF**);  
           }  
       }  
  }**  
  printf**(**"Case %d: %d\\n" **,**cas **++ ,**sum**);  

}
return** 0; }