hdu-4302-Holedox Eating-线段树-单点更新，有策略的单点查询

一开始实在是不知道怎么做，后来经过指导，猛然发现，只需要记录某个区间内是否有值即可。

flag[i]:代表i区间内，共有的蛋糕数量。

放置蛋糕的时候很好操作，单点更新。

ip：老鼠当前的位置

寻找吃哪一个蛋糕的时候：

1，要寻找0-ip这个区间内，位置最大的一个蛋糕的位置，记为ll。

2，要寻找ip-n这个区间内，位置最小的一个蛋糕的位置，记为rr。

找到ll，rr之后，就可以根据ll，rr跟ip的关系来确定该吃ll还是rr了。

如何寻找ll呢？

如果在某个区间的右半边区间找到了一个数，那么，这个区间的左半边区间肯定就不用寻找了。

如果这个区间的大小为1，那么这个区间内需要的数就肯定是这个数了。

如果某个区间的flag为0，那么这个区间肯定不存在蛋糕。

如果某个区间不包含0-ip，那么这个区间也肯定找不到ll。

于是，我们写出了寻找ll的函数：

int query(int ll,int rr,int l,int r,int rt)
{
    if(rr
  
   r)return -INF;
    if(flag[rt]==0)return -INF;
    if(l==r)
    {
        if(flag[rt])return l;
        else return -INF;
    }
    int ans=-INF;
    ans=query(ll,rr,rson);
    if(ans==-INF)ans=query(ll,rr,lson);
    return ans;
}
  

总体代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; #define INF 99999999 #define lmin 0 #define rmax n #define lson l,(l+r)/2,rt<<1 #define rson (l+r)/2+1,r,rt<<1|1 #define root lmin,rmax,1 #define maxn 110000 int flag[maxn*4]; void push_up(int rt) { flag[rt]=flag[rt<<1]+flag[rt<<1|1]; } void push_down(int rt) { } void creat(int l,int r,int rt) { flag[rt]=0; if(l!=r) { creat(lson); creat(rson); } } void update(int st,int x,int l,int r,int rt) { if(r
        
         st)return; if(l==r&&l==st) { flag[rt]+=x; return; } update(st,x,lson); update(st,x,rson); push_up(rt); } int query(int ll,int rr,int l,int r,int rt) { if(rr
         
          r)return -INF; if(flag[rt]==0)return -INF; if(l==r) { if(flag[rt])return l; else return -INF; } int ans=-INF; ans=query(ll,rr,rson); if(ans==-INF)ans=query(ll,rr,lson); return ans; } int query1(int ll,int rr,int l,int r,int rt) { // cout<
          
           r)return INF; if(flag[rt]==0)return INF; if(l==r) { if(flag[rt])return l; else return INF; } int ans=INF; ans=query1(ll,rr,lson); if(ans==INF)ans=query1(ll,rr,rson); return ans; } int main() { int cas,T; int n,m; int l,r,mid; int k,a,b,c; int m1,m2; scanf("%d",&T); cas=0; while(T--) { cas++; int sum=0; scanf("%d%d",&n,&m); creat(root); int ip=0; int f=0; while(m--) { scanf("%d",&k); if(k==1) { int l=query(0,ip,root); int r=query1(ip,n,root); // cout<
           
            =0||r<=n) { int ll=ip-l; int rr=r-ip; if(ll==rr&&f==1)mid=l; else if(ll==rr&&f==0)mid=r; else if(ll
            
             rr) { mid=r; f=0; } int cha=mid-ip; if(cha<0)cha=-cha; sum+=cha; ip=mid; update(mid,-1,root); } } else { scanf("%d",&a); update(a,1,root); } } printf("Case %d: %d\n",cas,sum); } return 0; }