hdu 4302 Holedox Eating 线段树去维护蛋糕！！
好囧啊！！打完貌似很快可调试一整天，太伤了，要是没有驴薛的对拍程序，我估计要整的没完没了，吐血了！！
不知到怎么想的，上来就想吃完蛋糕在走道，可题意分明是先找到蛋糕再吃！！貌似大家都不知道我在说什么，小小的吐曹一下！！
总之，思路不清晰千万不开始打代码！！！后换无穷啊！！！！！
#include<iostream>#include<cstdio>using namespace std;#define max1 100005#define inf 0xFFFFFFstruct node{ int l,r,ml,mr,cnt;//ml是这个线段的最左面的蛋糕，mr是这个线段最右面的蛋糕}a[max1*5];int x,y,s,sign1;int ab(int x){//计算绝对值 if(x<0) return x*(-1); return x;}void build(int left,int right ,int i){ a[i].cnt=0;//记录线段里蛋糕的个数 a[i].l=left; a[i].r=right; a[i].ml=inf;//初始化左面是最大的，右面最小的 a[i].mr=(-1)*inf; if(a[i].l==a[i].r) return ; int mid=(left+right)>>1; build(left,mid,2*i); build(mid+1,right,2*i+1);}void insert(int k,int i){ if(a[i].ml>k) a[i].ml=k; if(a[i].mr<k) a[i].mr=k; a[i].cnt++; if(a[i].l==a[i].r) return ; int mid=(a[i].l+a[i].r)>>1; if(k<=mid) insert(k,i*2); else insert(k,i*2+1);}void delete_num(int k,int i){ if(a[i].cnt!=0) a[i].cnt--; if(a[i].l==a[i].r){ if(a[i].cnt==0) {//如果最后一个线段的没有点了，就将其线段的表上初始值 a[i].ml=inf; a[i].mr=(-1)*inf; } return ; } int mid=(a[i].l+a[i].r)>>1; if(k<=mid) delete_num(k,i*2); else delete_num(k,i*2+1); a[i].ml=a[i*2].ml<a[i*2+1].ml ? a[i*2].ml:a[i*2+1].ml;//更新父亲节点区左右孩子的ml的最大值 a[i].mr=a[i*2].mr>a[i*2+1].mr ? a[i*2].mr:a[i*2+1].mr;//更新父亲节点区左右孩子的mr的最校值}void querry(int k,int i){ int mid=(a[i].l+a[i].r)>>1; if(a[i].l==a[i].r){ if(a[i].cnt>=1) sign1=1;//标记是否这个点还有蛋糕，如果a[i].cnt>=1，则要原地不动 return ; } if(k<=mid){ if(a[i*2+1].cnt) y=a[i*2+1].ml;//向左移动的时取右面线段的最左面的蛋糕 querry(k,i*2); } else{ if(a[i*2].cnt) x=a[i*2].mr;//向右移动的时取左面线段的最右面的蛋糕 querry(k,i*2+1); }}int main(){ int n,q,p,k,l,pp=1; scanf("%d",&n); while(n--){ int sign;//标记方向 s=0; long long sum=0;//注意L可以为100000，次数也可一100000，也就是说sum可以达到10^10 scanf("%d%d",&q,&p); build(0,q+1,1); while(p--){ scanf("%d",&k); if(k==0){ scanf("%d",&l); insert(l,1); } else{ sign1=0; x=inf;y=(-1)*inf; querry(s,1); if(sign1==1){//如果自己所在的点就有蛋糕的话就不用移动啦！！直接删除就可一 delete_num(s,1); continue; } if(x==inf && y==inf*(-1))//防止你一直输入1，都没有蛋糕啦 continue; int ta=ab(x-s); int te=ab(y-s); if(ta>te){ s=y;sum+=te;sign=1; } else if(ta<te){ s=x;sum+=ta;sign=0; } else{ if(sign==0) { s=x;sum+=ta; } if(sign==1) { s=y;sum+=te; } } delete_num(s,1); } } printf("Case %d: ",pp++); cout<<sum<<endl; }}