HDU4553(约会安排)

链接：https://vjudge.net/contest/260644#problem/M
思路：这道题题目意思很好懂，就是屌丝和女神有相同的安排时间的方法，但是如果女神没法安排时可以占用屌丝的时间，然后包含一个清空操作。一开始拿到题目无从下手，我们还是慢慢解剖整个思路，我们对于一个安排时间的操作我们需要知道哪一个时间段刚好有连续的长度为t的时间，这不跟前面一个询问某个点的最长连续区间是一样的道理嘛，对于每个区间维护一个左连续区间，右连续区间和最大连续区间，然后寻找区间时优先看左子树的最大连续区间长度是否大于等于t，如果否的话就看中间合并的一段，如果还否的话就看右子树，这样就可以解决安排的问题。对于女神和屌丝的不同操作，首先屌丝是不能占用之前屌丝的安排时间，所以屌丝和女神的区间信息我们考虑单独维护，屌丝就直接按上述步骤查看屌丝区间即可，女神的话先查看屌丝区间，如果有空的话优先占用屌丝区间（这样不冲突），否则再查看女神区间，如果有空的话占用并更新屌丝区间信息。注意处理女神区间时所有的屌丝标记也要随之改变，所以我们应该优先处理清空标记，然后是屌丝标记，最后才是女神标记，还是跟之前一样的思路，因为区间内信息是离散的，所以我们要通过和去确定唯一的确定区间，然后update直接覆盖整个区间并打上标记。细节问题很多看注释。还是那句总结：对于离散的区间信息我们可以通过维护一些总体信息（比如区间和）来确定出准确的区间位置，然后再把整个区间直接更新，这样可以避免离散区间信息没法维护的问题。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5+10;
int dsum[maxn<<2],nsum[maxn<<2],dl[maxn<<2],dr[maxn<<2],nl[maxn<<2],nr[maxn<<2];
int clear[maxn<<2],tagd[maxn<<2],tagn[maxn<<2];
int n,q;

void pushup(int o,int m){
    if(dl[o<<1]==m-(m>>1))dl[o] = dl[o<<1] + dl[o<<1|1];
//左连续区间覆盖左子树则要和右子树的左区间合并
    else dl[o] = dl[o<<1];
    if(dr[o<<1|1]==(m>>1))dr[o] = dr[o<<1|1] + dr[o<<1];
//右连续区间覆盖左子树则要和左子树的右区间合并
    else dr[o] = dr[o<<1|1];
    dsum[o] = max(dsum[o<<1],max(dsum[o<<1|1],dr[o<<1]+dl[o<<1|1]));
//一定记住最大值是左子树最大值，右子树最大值或者中间合并后的三者之一！！！不要再写错了！！！
    if(nl[o<<1]==m-(m>>1))nl[o] = nl[o<<1] + nl[o<<1|1];
    else nl[o] = nl[o<<1];
    if(nr[o<<1|1]==(m>>1))nr[o] = nr[o<<1|1] + nr[o<<1];
    else nr[o] = nr[o<<1|1];
    nsum[o] = max(nsum[o<<1],max(nsum[o<<1|1],nr[o<<1]+nl[o<<1|1]));
}

void pushdown(int o,int m){
    if(clear[o]){//清空标记，最先考虑
        clear[o<<1] = clear[o<<1|1] = clear[o];
        nsum[o<<1] = nl[o<<1] = nr[o<<1] = m-(m>>1);
        nsum[o<<1|1] = nl[o<<1|1] = nr[o<<1|1] = (m>>1); 
        dsum[o<<1] = dl[o<<1] = dr[o<<1] = m-(m>>1);
        dsum[o<<1|1] = dl[o<<1|1] = dr[o<<1|1] = (m>>1);
        clear[o] = 0;
        tagd[o<<1] = tagd[o<<1|1] = tagn[o<<1] = tagn[o<<1|1] = 0; 
    }
    if(tagd[o]){//因为女神标记会影响屌丝标记，所以优先考虑屌丝标记
        tagd[o<<1] = tagd[o<<1|1] = tagd[o];
        dsum[o<<1] = dl[o<<1] = dr[o<<1] = 0;
        dsum[o<<1|1] = dl[o<<1|1] = dr[o<<1|1] = 0;
        tagd[o] = 0;
    }
    if(tagn[o]){//女神标记，注意更新时更新子区间所有的屌丝标记以及屌丝区间的值
        tagn[o<<1] = tagn[o<<1|1] = tagn[o];
        tagd[o<<1] = tagd[o<<1|1] = 0;
        nsum[o<<1] = nl[o<<1] = nr[o<<1] = 0;
        nsum[o<<1|1] = nl[o<<1|1] = nr[o<<1|1] = 0;
        dsum[o<<1] = dl[o<<1] = dr[o<<1] = 0;
        dsum[o<<1|1] = dl[o<<1|1] = dr[o<<1|1] = 0;
        tagn[o] = 0;
    }
}

void build(int o,int l,int r){//初始sum全部为区间长度
  dsum[o] = nsum[o] = dl[o] = dr[o] = nl[o]  = nr[o] = r-l+1;
  clear[o] = tagd[o] = tagn[o] = 0; 
  if(l<r){
    int mid = l+r>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o,r-l+1);
  }
}

void update(int o,int tl,int tr,int l,int r,int v){
    if(tr<l||r<tl)return;
    if(l<=tl&&tr<=r){
    if(v==1){//以屌丝身份更新屌丝区间的信息
        dsum[o] = dl[o] = dr[o] = 0;
        tagd[o] = 1;
        return ;
    }
    if(v==2){//以女神身份更新女神区间的信息同时覆盖屌丝区间的信息，更新屌丝的标记
        nsum[o] = nl[o] = nr[o] = 0;
        dsum[o] = dl[o] = dr[o] = 0;
        tagd[o] = 0;
        tagn[o] = 1;
        return;
    }
    if(v==0){//清空信息并打上标记
        nsum[o] = nl[o] = nr[o] = tr-tl+1;
        dsum[o] = dl[o] = dr[o] = tr-tl+1;
        tagd[o] = tagn[o] = 0;
        clear[o] = 1;
        return ;
    }
  }
  pushdown(o,tr-tl+1);
  int mid = (tl+tr)>>1;
  update(o<<1,tl,mid,l,r,v);
  update(o<<1|1,mid+1,tr,l,r,v);
  pushup(o,tr-tl+1);
} 

int query(int o,int tl,int tr,int l,int r,int v,int t){
//这一段我感觉不太好理解，首先对于当前区间，先查看左子树能不能满足情况，能的话在左子树里面找，否则的话看中间合并后能不能满足情况，能的话我们可以直接得到区间左端点的值，最后看右子树，可以证明最后一定会递归到某个单点或者区间合并的时候(一直向左就是某个点，中间的话就是区间合并的时候)，所以一定能够得到左端点的位置。还是要分女神区间和屌丝区间
  if(tl==tr){
      return tl;
  }
  pushdown(o,tr-tl+1);
  int mid = (tl+tr)>>1;
  if(v==1){
      if(dsum[o<<1]>=t)return query(o<<1,tl,mid,l,r,v,t);
      else if(dr[o<<1]+dl[o<<1|1]>=t)return mid-dr[o<<1]+1;
      else return query(o<<1|1,mid+1,tr,l,r,v,t);
  }
  else{
       if(nsum[o<<1]>=t)return query(o<<1,tl,mid,l,r,v,t);
      else if(nr[o<<1]+nl[o<<1|1]>=t)return mid-nr[o<<1]+1;
      else return query(o<<1|1,mid+1,tr,l,r,v,t);
  }
}

int T;

int main(){
    scanf("%d",&T);
    int kase = 0;
  while(T--){
      scanf("%d%d",&n,&q);
      printf("Case %d:\n",++kase);
    build(1,1,n);
    char ch[100];
    int p,o;
    for(int i=1;i<=q;i++){
      scanf("%s",ch);
      if(ch[0]=='D'){
          scanf("%d",&p);
          if(dsum[1]<p)printf("fly with yourself\n");//查看最大的剩余量，判断是否存在解
          else{
          int tt = query(1,1,n,1,n,1,p);
          update(1,1,n,tt,tt+p-1,1);
          printf("%d,let's fly\n",tt);
          }
      }
      else if(ch[0]=='N'){
          scanf("%d",&p);
          if(dsum[1]<p){//先看屌丝区间能不能满足分配情况
              if(nsum[1]<p){//屌丝区间不能则看女神区间
                  printf("wait for me\n");
              }
              else{
                  int tt = query(1,1,n,1,n,2,p);//以女神身份寻找女神区间的左端点
                  update(1,1,n,tt,tt+p-1,2);//确定具体区间以女神身份更新区间信息
                  printf("%d,don't put my gezi\n",tt);
              }
          }
          else{//屌丝区间能够满足，优先考虑
              int tt = query(1,1,n,1,n,1,p);//以屌丝身份查看屌丝区间的信息
              update(1,1,n,tt,tt+p-1,2);//以女神身份更新女神区间信息以及屌丝区间信息
              printf("%d,don't put my gezi\n",tt);
          }
      }
      else{
          scanf("%d%d",&p,&o);
          update(1,1,n,p,o,0);//清空区间信息
          printf("I am the hope of chinese chengxuyuan!!\n");
      }
    }
  }
  return  0;
}