前言

        欢迎大家积极在评论区留言发表自己的看法，知无不言，言无不尽，养成每天刷题的习惯，也可以自己发布优质的解题报告，供社区一同鉴赏，吸引一波自己的核心粉丝。
        今天是六月集训第二十四天：线段树🔥🔥🔥🔥🔥

一、练习题目

        731. 我的日程安排表 II
        699. 掉落的方块

二、算法思路

• 1、731. 我的日程安排表 II：利用差分的思想来做的题，再复习一遍差分思想吧，还没用线段树。🔥🔥🔥🔥🔥
    1.差分数组的定义
    假设有数组A，我们将数组A中的每一项与前一项的差值组成的新数组F称为差分数组。对于F显然有：
  F [ i ] = { A [ i ] ( i = 0 ) A [ i ] − A [ i − 1 ] ( i > 0 ) F[i]=
  {A[i](i=0)A[i]−A[i−1](i>0)$$\{\begin{array}{l}A[i](i=0)\\ A[i]-A[i-1](i>0)\end{array}$$
  F[i]={A[i](i=0)A[i]−A[i−1](i>0)​
  举例：

   2.差分数组特性

   计算数列各项的值：数列第i项的值是可以用差分数组的前i项和计算得到，即前缀和。$A[i]=F[i]+A[i-1]$
  快速执行区间的加减操作：比如数组A的1~5项都增加1：

可以发现规律了，差分数组F只改变了两边端点的值，在左闭右开的区间内，即上面的例子是：[1,6)，起始端点加1，结尾端减1。
   3.差分数组应用
   结合此题来进行说明：我们要为每一个日期进行安排，每个日期安排的数组数量表示为数组A，F表示差分数组。

执行A(1,5)后，根据题意start=1，end=5：

可以发现规律了，差分数组F只改变了两边端点的值，在左闭右开的区间内，即上面的例子是：[1,5)，起始端点加1，结尾端减1。

• 2、699. 掉落的方块：困难题🔥🔥🔥🔥🔥

三、源码剖析

// 731. 我的日程安排表 II
class MyCalendarTwo {
    map<int, int> cnt;
public:
    MyCalendarTwo() {
        cnt.clear();
    }
    
    bool book(int start, int end) {
        ++cnt[start];
        --cnt[end];
        int sum = 0;
        for(auto i : cnt) {
            sum += i.second;
            if(sum > 2) {
                --cnt[start];
                ++cnt[end];
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 1、见思路详解。

// 699. 掉落的方块

1
2

• 1、