HDU 4302 Holedox Eating （二分+树状数组维护）

题意：一个小孩吃蛋糕，他的起始点在0位置，现在有m个操作，0 x 代表在x位置出现一个蛋糕； 1 代表小孩要去离他最近的点吃蛋糕，如果与他距离最小的点有两个，则去与他上次走的方向相同的点； 如果没有蛋糕，他就不动。 询问m次操作过后，小孩走了多少距离。

每一次，用二分判断，他右边离他最近的蛋糕点，和左边离他最近的蛋糕点。如何判断呢，只需用树状数组维护蛋糕总数，判断小孩当前位置pos 与 mid之间的蛋糕数是否大于等1，是的话可以尝试逼近，否则就远离。

需要注意线段是1 --- L ，而小孩起始点在0，所以有L + 1 个点。

#include <iostream>#include <algorithm>#include <cmath>#include<functional>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <vector>#include <set>#include <queue>#include <stack>#include <climits>//形如INT_MAX一类的#define MAX 100050#define INF 0x7FFFFFFFusing namespace std;int n,m;int c[MAX];int lowbit(int x) {    return x & (-x);}void update(int x,int va) {    while(x < n + 2) {        c[x] += va;        x += lowbit(x);    }}int query(int x) {    int sum = 0;    while(x > 0) {        sum += c[x];        x -= lowbit(x);    }    return sum;}int judge(int p,int rp,int lp,int flag) {    if(rp == -1 && lp == -1) return -1;    if(rp == -1) return 0;    if(lp == -1) return 1;    if(rp - p > p - lp) return 0;    if(rp - p < p - lp) return 1;    if(flag == 0) return 0;    return 1;}int find(int pos,int l,int r,int kind) {    int mid , des;    if(kind == 1) des = INF;    else des = -1;    while(l <= r) {        mid = (l + r) >> 1;        if(kind == 1) {            if(query(mid) - query(pos - 1) >= 1) {                des = min(des,mid);                r = mid - 1;            } else l = mid + 1;        } else {            if(query(pos) - query(mid - 1) >= 1) {                des = max(des,mid);                l = mid + 1;            } else r = mid - 1;        }//        cout << l << ' ' << mid << ' ' << r << endl;    }    if(des == INF) return -1;    return des;}int main() {    int T;    cin >> T;    int ca = 1;    while(T--) {        scanf("%d%d",&n,&m);        memset(c,0,sizeof(c));        int a,b;        int pos = 1, flag = 1; //flag 1:right  0: left        __int64 dis = 0;        for(int i=0; i<m; i++) {            scanf("%d",&a);            if(a == 1) {                int rpos = find(pos,pos,n+1,1);                int lpos = find(pos,1,pos,0);                int dir = judge(pos,rpos,lpos,flag);                if(dir == -1) continue;                if(dir == 1) {                    dis += rpos - pos;                    pos = rpos;                    flag = 1;                } else {                    dis += pos - lpos;                    pos = lpos;                    flag = 0;                }                update(pos,-1);            } else {                scanf("%d",&b);                update(b+1,1);            }        }        printf("Case %d: %d\n",ca ++,dis);    }    return 0;}