约会安排HDU

　　寒假来了，又到了小明和女神们约会的季节。
　　小明虽为屌丝级码农，但非常活跃，女神们常常在小明网上的大段发言后热情回复“呵呵”，所以，小明的最爱就是和女神们约会。与此同时，也有很多基友找他开黑，由于数量实在过于巨大，怎么安排时间便成了小明的一大心事。
　　我们已知小明一共有T的空闲时间，期间会有很多女神或者基友来找小明。
　　作为一个操作系统曾经怒考71分的大神，小明想到了一个算法，即“首次适应算法”，根据操作系统课本的描述，就是找一段最靠前的符合要求的连续空间分配给每个请求，由此小明做出了一个决定：
　　当一个基友来找小明时，小明就根据“首次适应算法”来找一段空闲的时间来和基友约好，如果找到，就说“X,let’s fly”（此处，X为开始时间），否则就说“fly with yourself”；
　　当女神来找小明时，先使用一次“首次适应算法”，如果没有找到，小明就冒着木叽叽的风险无视所有屌丝基友的约定，再次使用“无视基友首次适应算法”，两次只要有一次找到，就说“X,don’t put my gezi”（此处，X为开始时间），否则就说“wait for me”
　　当然，我们知道小明不是一个节操负无穷的人，如果和女神约会完，还有剩余时间，他还是会和原来约好的基友去dota的。（举个例子：小西（屌丝）和小明约好在1~5这个时间单位段内打dota，这时候，女神来和小明预约长度为3的时间段，那么最终就是1~3小明去和女神约会，搞定后在4~5和小西打dota）
　　小明偶尔也会想要学习新知识，此时小明就会把某一个时间区间的所有已经预定的时间全部清空用来学习并且怒吼“I am the hope of chinese chengxuyuan!!”，不过小明一般都是三分钟热度，再有人来预定的话，小明就会按耐不住寂寞把学习新知识的时间分配出去。

Input输入第一行为CASE，表示有CASE组测试数据；
每组数据以两个整数T，N开始，T代表总共的时间，N表示预约请求的个数；
接着的N行，每行表示一个女神或者基友的预约，“NS QT”代表一个女神来找小明约一段长为QT的时间，“DS QT”则代表一个屌丝的长为QT的请求，当然也有可能是小明想学知识了，“STUDY!! L R”代表清空L~R区间内的所有请求。

[Technical Specification]
1. 1 <= CASE <= 30
2. 1 <= T, N <= 100000
3. 1 <= QT <= 110000
4. 1 <= L <= R <=TOutput对于每一个case，第一行先输出“Case C:”代表是第几个case，然后N行，每行对应一个请求的结果(参照描述)。
输出样本(可复制此处)：
“X,let's fly”,”fly with yourself”,”X,don't put my gezi”,”wait for me”,”I am the hope of chinese chengxuyuan!!”
Sample Input

1
5 6
DS 3
NS 2
NS 4
STUDY!! 1 5
DS 4
NS 2

Sample Output

Case 1:
1,let's fly
4,don't put my gezi
wait for me
I am the hope of chinese chengxuyuan!!
1,let's fly
1,don't put my gezi

题意：可以发现，屌丝无法占用女神时间，女神可以占用屌丝时间，学习最高优先级，这样就是分开用线段树维护。
　　　说起来并不是特别难，但是还是比较烦的，需要一种境界才可以，才能耐心打出这道题目，不适合比赛首选
　　　题，适合平时练，这道题我做的时候读懂了以后打了将近两三个下午，几节自修课，但是还是没有做出来。
下面是自己打的没有ac的代码

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cmath>
  5 #include<map>
  6 #include<queue>
  7 #define MAXN 4000007
  8 char s[17];
  9 int n,m,t,x,y,ans,tt; 
 10 struct fzy
 11 {
 12     int d,n,xue;
 13     int dsl,dsr,dsn;
 14     int nsl,nsr,nsn;
 15 }tree[MAXN];
 16 using namespace std;
 17 void diaosi(int l,int r,int p)
 18 {
 19     tree[p].dsl=tree[p].dsr=tree[p].dsn=0;
 20     tree[p].d=1;
 21 }
 22 void nvshen(int l,int r,int p)
 23 {
 24     tree[p].n=1;
 25     tree[p].d=0;
 26     tree[p].dsl=tree[p].dsr=tree[p].dsn=0;
 27     tree[p].nsl=tree[p].nsn=tree[p].nsr=0;
 28 }
 29 void xuexi(int l,int r,int p)
 30 {
 31     tree[p].d=0;
 32     tree[p].n=0;
 33     tree[p].xue=1;
 34     tree[p].dsl=tree[p].dsr=tree[p].dsn=r-l+1;
 35     tree[p].nsl=tree[p].nsn=tree[p].nsr=r-l+1;
 36 }
 37 void push_down(int l,int r,int p)
 38 {
 39     int m=(l+r)>>1;
 40     if (tree[p].d==1)
 41     {
 42         diaosi(l,m,p*2);
 43         diaosi(m+1,r,p*2+1);
 44         tree[p].d=0;
 45     }
 46     if (tree[p].n==1)
 47     {
 48         nvshen(l,m,p*2);
 49         nvshen(m+1,r,p*2+1);
 50         tree[p].n=0;
 51     }
 52 }
 53 int query_ds(int l,int r,int p,int zhi)
 54 {
 55     if (l==r) return l;
 56     push_down(l,r,p);
 57     int m=(l+r)>>1;
 58     if (tree[p*2].dsn>=zhi) return query_ds(l,m,p*2,zhi);
 59     else if (tree[p*2].dsr+tree[p*2+1].dsl>=zhi) return m-tree[p*2].dsr+1;
 60     else if (tree[p*2+1].dsn>=zhi) return query_ds(m+1,r,p*2+1,zhi);
 61 }
 62 void push_up(int l,int r,int p)
 63 {
 64     int m=(l+r)>>1;
 65     tree[p].dsn=max(tree[p*2].dsn,tree[p*2+1].dsn);
 66     tree[p].dsn=max(tree[p].dsn,tree[p*2].dsr+tree[p*2+1].dsl);
 67     tree[p].dsl=tree[p*2].dsl;
 68     tree[p].dsr=tree[p*2+1].dsr;
 69     if (tree[p*2].dsl==m-l+1) tree[p].dsl+=tree[p*2+1].dsl;
 70     if (tree[p*2+1].dsr==r-m) tree[p].dsr+=tree[p*2].dsr;
 71 
 72     tree[p].nsn=max(tree[p*2].nsn,tree[p*2+1].nsn);
 73     tree[p].nsn=max(tree[p].nsn,tree[p*2].nsr+tree[p*2+1].nsl);
 74     tree[p].nsl=tree[p*2].nsl;
 75     tree[p].nsr=tree[p*2+1].nsr;
 76     if (tree[p*2].nsl==m-l+1) tree[p].nsl+=tree[p*2+1].nsl;
 77     if (tree[p*2+1].nsr==r-m) tree[p].nsr+=tree[p*2].nsr;
 78 }
 79 void into_ds(int l,int r,int p,int L,int R)
 80 {
 81     if (l==L&&R==r)
 82     {
 83         diaosi(l,r,p);
 84         return;
 85     }
 86     push_down(l,r,p);
 87     int m=(l+r)>>1;
 88     if (R<=m) into_ds(l,m,p*2,L,R);
 89     else if (L>m) into_ds(m+1,r,p*2+1,L,R);
 90     else 
 91     {
 92         into_ds(l,m,p*2,L,m);
 93         into_ds(m+1,r,p*2+1,m+1,R);
 94     }
 95     push_up(l,r,p);
 96 }
 97 void into_ns(int l,int r,int p,int L,int R)
 98 {
 99     if (l==L&&R==r)
100     {
101         nvshen(l,r,p);
102         return;
103     }
104     push_down(l,r,p);
105     int m=(l+r)>>1;
106     if (R<=m) into_ns(l,m,p*2,L,R);
107     else if (L>m) into_ns(m+1,r,p*2+1,L,R);
108     else 
109     {
110         into_ns(l,m,p*2,L,m);
111         into_ns(m+1,r,p*2+1,m+1,R);
112     }
113     push_up(l,r,p);
114 }
115 int query_ns(int l,int r,int p,int zhi)
116 {
117     if (l==r) return l;
118     push_down(l,r,p);
119     int m=(l+r)>>1;
120     if (tree[p*2].nsn>=zhi) return query_ns(l,m,p*2,zhi);
121     else if (tree[p*2].nsr+tree[p*2+1].nsl>=zhi) return m-tree[p*2].nsr+1;
122     else if (tree[p*2+1].nsn>=zhi) return query_ns(m+1,r,p*2+1,zhi);
123 }
124 void study(int l,int r,int p,int L,int R)
125 {
126     if (l==L&&R==r)
127     {
128         xuexi(l,r,p);
129         return;
130     }
131     push_down(l,r,p);
132     int m=(l+r)>>1;
133     if (R<=m) study(l,m,p*2,L,R);
134     else if (L>m) study(m+1,r,p*2+1,L,R);
135     else 
136     {
137         study(l,m,p*2,L,m);
138         study(m+1,r,p*2+1,m+1,R);
139     }
140     push_up(l,r,p);
141 }
142 int main()
143 {
144     scanf("%d",&t);tt=0;
145     while (t--)
146     {
147         cout<<"Case "<<++tt<<":"<<endl;
148         scanf("%d%d",&n,&m);
149         study(1,n,1,1,n);
150         for (int i=1;i<=m;i++)
151         {
152             scanf("%s%d",s,&x);
153             switch (s[0])
154             {
155                 case ('D'):
156                 {
157                     if (tree[1].dsn<x) cout<<"fly with yourself"<<endl;
158                     else 
159                     {
160                         ans=query_ds(1,n,1,x);
161                         into_ds(1,n,1,ans,ans+x-1);
162                         cout<<ans<<",let's fly"<<endl;
163                     }
164                     break;
165                 }
166                 case ('N'): 
167                 {
168                     if (tree[1].dsn<x) 
169                     {
170                         if (tree[1].nsn<x) cout<<"wait for me"<<endl;
171                         else 
172                         {
173                             ans=query_ns(1,n,1,x);
174                             cout<<ans<<endl;
175                             into_ns(1,n,1,ans,ans+x-1);
176                             cout<<ans<<",don't put my gezi"<<endl;
177                         }
178                     } 
179                     else 
180                     {
181                         ans=query_ds(1,n,1,x);
182                         into_ns(1,n,1,ans,ans+x-1);
183                         cout<<ans<<",don't put my gezi"<<endl;
184                     }
185                     break;
186                 }
187                 case ('S'):
188                 {
189                     scanf("%d",&y);
190                     study(1,n,1,x,y);
191                     cout<<"I am the hope of chinese chengxuyuan!!"<<endl;
192                     break;
193                 }
194             }    
195         }    
196     }    
197 }

标准代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct node
{
    int d,n,s;
    int ls,rs,ms;
    int nsl,nsr,nsm;
} tt[400005];

void diaosi(int l,int r,int i)
{
    tt[i].d = 1;
    tt[i].ls = tt[i].rs = tt[i].ms = 0;
}

void nvshen(int l,int r,int i)
{
    tt[i].n = 1;
    tt[i].d = 0;
    tt[i].ls = tt[i].rs = tt[i].ms = 0;
    tt[i].nsl = tt[i].nsr = tt[i].nsm = 0;
}

void xuexi(int l,int r,int i)
{
    tt[i].s = 1;
    tt[i].d = tt[i].n = 0;
    tt[i].ls = tt[i].rs = tt[i].ms = r-l+1;
    tt[i].nsl = tt[i].nsr = tt[i].nsm = r-l+1;
}

void pushup(int l,int r,int u)
{
    int mid = (l+r)>>1;
    tt[u].ms = max(tt[u<<1].ms,tt[u<<1|1].ms);
    tt[u].ms = max(tt[u].ms,tt[u<<1].rs+tt[u<<1|1].ls);
    tt[u].ls = tt[u<<1].ls;
    if(tt[u<<1].ls == mid-l+1)
        tt[u].ls+=tt[u<<1|1].ls;
    tt[u].rs = tt[u<<1|1].rs;
    if(tt[u<<1|1].rs == r-mid)
        tt[u].rs+= tt[u<<1].rs;
    tt[u].nsm = max(tt[u<<1].nsm,tt[u<<1|1].nsm);
    tt[u].nsm = max(tt[u].nsm,tt[u<<1].nsr+tt[u<<1|1].nsl);
    tt[u].nsl = tt[u<<1].nsl;
    if(tt[u<<1].nsl == mid-l+1)
        tt[u].nsl+=tt[u<<1|1].nsl;
    tt[u].nsr = tt[u<<1|1].nsr;
    if(tt[u<<1|1].nsr == r-mid)
        tt[u].nsr+= tt[u<<1].nsr;
}

void pushdown(int l,int r,int u)
{
    int mid = (l+r)>>1;
    if(tt[u].s)
    {
        xuexi(l,mid,u<<1);
        xuexi(mid+1,r,u<<1|1);
        tt[u].s = 0;
    }
    if(tt[u].d)
    {
        diaosi(l,mid,u<<1);
        diaosi(mid+1,r,u<<1|1);
        tt[u].d = 0;
    }
    if(tt[u].n)
    {
        nvshen(l,mid,u<<1);
        nvshen(mid+1,r,u<<1|1);
        tt[u].n = 0;
    }
}

void study(int u,int L,int R,int l,int r)
{
    if(L == l && R == r)
    {
        xuexi(l,r,u);
        return ;
    }
    int mid  = (l+r)>>1;
    pushdown(l,r,u);
    if(R<=mid)
        study(u<<1,L,R,l,mid);
    else if(L>mid)
        study(u<<1|1,L,R,mid+1,r);
    else
    {
        study(u<<1,L,mid,l,mid);
        study(u<<1|1,mid+1,R,mid+1,r);
    }
    pushup(l,r,u);
}


void insert(int u,int flag,int L,int R,int l,int r)
{
    if(l == L && r == R)
    {
        if(!flag)
            diaosi(l,r,u);
        else
            nvshen(l,r,u);
        return ;
    }
    int mid  = (l+r)>>1;
    pushdown(l,r,u);
    if(R<=mid)
        insert(u<<1,flag,L,R,l,mid);
    else if(L>mid)
        insert(u<<1|1,flag,L,R,mid+1,r);
    else
    {
        insert(u<<1,flag,L,mid,l,mid);
        insert(u<<1|1,flag,mid+1,R,mid+1,r);
    }
    pushup(l,r,u);
}

int query(int u,int flag,int t,int l,int r)
{
    if(l==r)
        return l;
    int mid = (l+r)>>1;
    pushdown(l,r,u);
    if(!flag)
    {
        if(tt[u<<1].ms>=t)
            return query(u<<1,flag,t,l,mid);
        else if(tt[u<<1].rs+tt[u<<1|1].ls>=t)
            return mid-tt[u<<1].rs+1;
        else
            return query(u<<1|1,flag,t,mid+1,r);
    }
    else
    {
        if(tt[u<<1].nsm>=t)
            return query(u<<1,flag,t,l,mid);
        else if(tt[u<<1].nsr+tt[u<<1|1].nsl>=t)
            return mid-tt[u<<1].nsr+1;
        else
            return query(u<<1|1,flag,t,mid+1,r);
    }
}


int main()
{
    int t,cas = 1;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        int ans;
        scanf("%d%d",&n,&m);
        printf("Case %d:
",cas++);
        study(1,1,n,1,n);
        while(m--)
        {
            char str[15];
            scanf("%s",str);
            int x,y;
            if(str[0] == 'D')
            {
                scanf("%d",&x);
                if(tt[1].ms<x)
                    printf("fly with yourself
");
                else
                {
                    ans = query(1,0,x,1,n);
                    insert(1,0,ans,ans+x-1,1,n);
                    printf("%d,let's fly
",ans);
                }
            }
            else if(str[0] == 'N')
            {
                scanf("%d",&x);
                if(tt[1].ms<x)
                {
                    if(tt[1].nsm<x)
                        printf("wait for me
");
                    else
                    {
                        ans = query(1,1,x,1,n);
                        insert(1,1,ans,ans+x-1,1,n);
                        printf("%d,don't put my gezi
",ans);
                    }
                }
                else
                {
                    ans = query(1,0,x,1,n);
                    insert(1,1,ans,ans+x-1,1,n);
                    printf("%d,don't put my gezi
",ans);
                }
            }
            else
            {
                scanf("%d%d",&x,&y);
                study(1,x,y,1,n);
                printf("I am the hope of chinese chengxuyuan!!
");
            }
        }
    }
    return 0;
}