约会安排 HDU - 4553（线段树区间查询，区间修改，区间合并）

我会带着你远行 2021-10-29 09:30 287阅读 0赞

### 题目： ###

寒假来了，又到了小明和女神们约会的季节。  
　　小明虽为屌丝级码农，但非常活跃，女神们常常在小明网上的大段发言后热情回复“呵呵”，所以，小明的最爱就是和女神们约会。与此同时，也有很多基友找他开黑，由于数量实在过于巨大，怎么安排时间便成了小明的一大心事。  
　　我们已知小明一共有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 <=T

Output

对于每一个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

分析：（大一以来见过的最长的代码，网上都是200+，带着崩溃硬是被我压到了150+，太麻烦了。。。）这个题麻烦的就是区间查询如何找到从左边开始的第一个空闲区间。具体实现见代码>>

代码：

1 #include <bits/stdc++.h>/有史以来写过的代码最长的题目，mygod！
      2 using namespace std;
      3 const int maxn = 1e5 + 10;
      4 struct node
      5 {
      6     int l, r;
      7     int rm, mm, lm;屌丝
      8     int rm1, mm1, lm1;/女神
      9     void ini() { rm = mm = lm = 0; }
     10     void full() { rm = mm = lm = r - l + 1; }
     11     void ini1() { rm1 = mm1 = lm1 = 0; }
     12     void full1() { rm1 = mm1 = lm1 = r - l + 1; }
     13 }t[maxn << 2];
     14 int n, m;
     15 
     16 void pushdown(int tar)
     17 {
     18     if (t[tar].mm == 0)
     19         t[tar << 1].ini(), t[tar << 1 | 1].ini();
     20     if (t[tar].mm == t[tar].r - t[tar].l + 1)
     21         t[tar << 1].full(), t[tar << 1 | 1].full();
     22     if(t[tar].mm1 == 0)
     23         t[tar << 1].ini1(), t[tar << 1 | 1].ini1();
     24     if (t[tar].mm1 == t[tar].r - t[tar].l + 1)
     25         t[tar << 1].full1(), t[tar << 1 | 1].full1();
     26 }
     27 
     28 void pushup(int tar)
     29 {
     30     t[tar].lm = t[tar << 1].lm;
     31     t[tar].rm = t[tar << 1 | 1].rm;
     32     t[tar].mm = max(t[tar << 1].mm, t[tar << 1 | 1].mm);
     33     t[tar].mm = max(t[tar].mm, t[tar << 1].rm + t[tar << 1 | 1].lm);
     34     if (t[tar << 1].lm == t[tar << 1].r - t[tar << 1].l + 1)
     35         t[tar].lm += t[tar << 1 | 1].lm;
     36     if (t[tar << 1 | 1].rm == t[tar << 1 | 1].r - t[tar << 1 | 1].l + 1)
     37         t[tar].rm += t[tar << 1].rm;
     38 
     39     t[tar].lm1 = t[tar << 1].lm1;
     40     t[tar].rm1 = t[tar << 1 | 1].rm1;
     41     t[tar].mm1 = max(t[tar << 1].mm1, t[tar << 1 | 1].mm1);
     42     t[tar].mm1 = max(t[tar].mm1, t[tar << 1].rm1 + t[tar << 1 | 1].lm1);
     43     if (t[tar << 1].lm1 == t[tar << 1].r - t[tar << 1].l + 1)
     44         t[tar].lm1 += t[tar << 1 | 1].lm1;
     45     if (t[tar << 1 | 1].rm1 == t[tar << 1 | 1].r - t[tar << 1 | 1].l + 1)
     46         t[tar].rm1 += t[tar << 1].rm1;
     47 }
     48 
     49 void build(int l, int r, int tar)
     50 {
     51     t[tar].l = l, t[tar].r = r;
     52     t[tar].full(), t[tar].full1();
     53     if (l == r) return;
     54     int mid = (l + r) >> 1;
     55     build(l, mid, tar << 1);
     56     build(mid + 1, r, tar << 1 | 1);
     57 }
     58 
     59 void update(int kind, int l, int r, int tar)
     60 {
     61     if (l == t[tar].l && r == t[tar].r)
     62     {
     63         if (kind == 1)  t[tar].ini();
     64         else if (kind == 2) t[tar].ini(), t[tar].ini1();
     65         else t[tar].full(), t[tar].full1();
     66         return;
     67     }
     68     pushdown(tar);
     69     int mid = (t[tar].l + t[tar].r) >> 1;
     70     if (r <= mid) update(kind, l, r, tar << 1);
     71     else if (l > mid) update(kind, l, r, tar << 1 | 1);
     72     else update(kind, l, mid, tar << 1), update(kind, mid + 1, r, tar << 1 | 1);
     73     pushup(tar);
     74 }
     75 
     76 int query(int kind, int tar, int v)
     77 {
     78     if (kind == 1)
     79     {
     80         if (t[tar].mm < v) return 0;
     81         if (t[tar].lm >= v) return t[tar].l;
     82         if (t[tar << 1].mm >= v) return query(kind, tar << 1, v);
     83         if (t[tar << 1].rm + t[tar << 1 | 1].lm >= v) return t[tar << 1].r - t[tar << 1].rm + 1;
     84         return query(kind, tar << 1 | 1, v);
     85     }
     86     else
     87     {
     88         if (t[tar].mm1 < v) return 0;
     89         if (t[tar].lm1 >= v) return t[tar].l;
     90         if (t[tar << 1].mm1 >= v) return query(kind, tar << 1, v);
     91         if (t[tar << 1].rm1 + t[tar << 1 | 1].lm1 >= v) return t[tar << 1].r - t[tar << 1].rm1 + 1;
     92         return query(kind, tar << 1 | 1, v);
     93     }
     94 }
     95 
     96 int main()
     97 {
     98     int T; cin >> T;
     99     char dir[100];
    100     int x, y;
    101     int cases = 0;
    102 
    103     while (T--)
    104     {
    105         scanf("%d%d", &n, &m);
    106         build(1, n, 1);
    107         printf("Case %d:\n", ++cases);
    108         while (m--)
    109         {
    110             scanf("%s", dir);
    111             if (dir[0] == 'D')
    112             {
    113                 scanf("%d", &x);
    114                 int l = query(1, 1, x);
    115                 //cout << l << endl;
    116                 if(!l) printf("fly with yourself\n");
    117                 else
    118                 {
    119                     printf("%d,let's fly\n", l);
    120                     update(1, l, l + x - 1, 1);   //kind, l, r, tar
    121                 }
    122             }
    123             else if (dir[0] == 'N')
    124             {
    125                 scanf("%d", &x);
    126                 int l = query(1, 1, x);
    127                 //cout << l << endl;
    128                 if (l != 0)
    129                 {
    130                     printf("%d,don't put my gezi\n", l);
    131                     update(2, l, l + x - 1, 1);
    132                 }
    133                 else
    134                 {
    135                     l = query(2, 1, x);
    136                     if (l != 0)
    137                     {
    138                         printf("%d,don't put my gezi\n", l);
    139                         update(2, l, l + x - 1, 1);
    140                     }
    141                     else printf("wait for me\n");
    142                 }
    143             }
    144             else
    145             {
    146                 scanf("%d%d", &x, &y);
    147                 printf("I am the hope of chinese chengxuyuan!!\n");
    148                 update(3, x, y, 1);
    149             }
    150         }
    151     }
    152 }

![点击并拖拽以移动][Image 1]

转载于:https://www.cnblogs.com/liuwenhan/p/11356198.html

[Image 1]: