乐趣区

关于程序员:宫水三叶的刷题日记732-我的日程安排表-III

jiezi

题目形容

这是 LeetCode 上的 732. 我的日程安排表 III，难度为 艰难 。

Tag :「线段树（动静开点）」、「分块」、「线段树」

当 $k$ 个日程安排有一些工夫上的穿插时（例如 $k$ 个日程安排都在同一时间内），就会产生 $k$ 次预订。

给你一些日程安排 $[start, end)$，请你在每个日程安排增加后，返回一个整数 $k$，示意所有先前日程安排会产生的最大 $k$ 次预订。

实现一个 MyCalendarThree 类来寄存你的日程安排，你能够始终增加新的日程安排。

  • MyCalendarThree() 初始化对象。
  • int book(int start, int end) 返回一个整数 $k$，示意日历中存在的 $k$ 次预订的最大值。

示例：

 输出：["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

输入：[null, 1, 1, 2, 3, 3, 3]

解释：MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1，第一个日程安排能够预订并且不存在相交，所以最大 k 次预订是 1 次预订。myCalendarThree.book(50, 60); // 返回 1，第二个日程安排能够预订并且不存在相交，所以最大 k 次预订是 1 次预订。myCalendarThree.book(10, 40); // 返回 2，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。myCalendarThree.book(5, 15); // 返回 3，剩下的日程安排的最大 k 次预订是 3 次预订。myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

提醒：

  • $0 <= start < end <= 10^9$
  • 每个测试用例，调用 book 函数最多不超过 $400$ 次

线段树（动静开点）

和 731. 我的日程安排表 II 简直完全一致，只须要将对「线段树」所保护的节点信息进行调整即可。

线段树保护的节点信息包含：

  • ls/rs: 别离代表以后节点的左右子节点在线段树数组 tr 中的下标；
  • add: 懒标记；
  • max: 为以后区间的最大值。

对于惯例的线段树实现来说，都是一开始就调用 build 操作创立空树，而线段树个别以「满二叉树」的模式用数组存储，因而须要 $4 \times n$ 的空间，并且这些空间在起始 build 空树的时候曾经锁死。

如果一道题仅仅是「值域很大」的离线题（提前通晓所有的询问），咱们还能通过「离散化」来进行解决，将值域映射到一个小空间去，从而解决 MLE 问题。

但对于本题而言，因为「强制在线」的起因，咱们无奈进行「离散化」，同时值域大小达到 $1e9$ 级别，因而如果咱们想要应用「线段树」进行求解，只能采取「动静开点」的形式进行。

动静开点的劣势在于，不须要事先结构空树，而是在插入操作 add 和查问操作 query 时依据拜访须要进行「开点」操作。因为咱们不保障查问和插入都是间断的，因而对于父节点 $u$ 而言，咱们不能通过 u << 1 和 u << 1 | 1 的固定形式进行拜访，而要将节点 $tr[u]$ 的左右节点所在 tr 数组的下标进行存储，别离记为 ls 和 rs 属性。对于 $tr[u].ls = 0$ 和 $tr[u].rs = 0$ 则是代表子节点尚未被创立，当须要拜访到它们，而又尚未创立的时候，则将其进行创立。

因为存在「懒标记」，线段树的插入和查问都是 $\log{n}$ 的，因而咱们在单次操作的时候，最多会创立数量级为 $\log{n}$ 的点，因而空间复杂度为 $O(m\log{n})$，而不是 $O(4 \times n)$，而开点数的预估需不能仅仅依据 $\log{n}$ 来进行，还要对常熟进行剖析，能力失去精确的点数上界。

动静开点相比于原始的线段树实现，实质仍是应用「满二叉树」的模式进行存储，只不过是按需创立区间，如果咱们是依照间断段进行查问或插入，最坏状况下依然会占到 $4 \times n$ 的空间，因而盲猜 $\log{n}$ 的常数在 $4$ 左右，激进一点能够间接估算到 $6$，因而咱们能够估算点数为 $6 \times m \times \log{n}$，其中 $n = 1e9$ 和 $m = 1e3$ 别离代表值域大小和查问次数。

当然一个比拟实用的估点形式能够「尽可能的多开点数」，利用题目给定的空间上界和咱们创立的自定义类（构造体）的大小，尽可能的多开（Java 的 128M 能够开到 $5 \times 10^6$ 以上）。

代码：

class MyCalendarThree {
    class Node {int ls, rs, add, max;}
    int N = (int)1e9, M = 4 * 400 * 20, cnt = 1;
    Node[] tr = new Node[M];
    void update(int u, int lc, int rc, int l, int r, int v) {if (l <= lc && rc <= r) {tr[u].add += v;
            tr[u].max += v;
            return ;
        }
        lazyCreate(u);
        pushdown(u);
        int mid = lc + rc >> 1;
        if (l <= mid) update(tr[u].ls, lc, mid, l, r, v);
        if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, v);
        pushup(u);
    }
    int query(int u, int lc, int rc, int l, int r) {if (l <= lc && rc <= r) return tr[u].max;
        lazyCreate(u);
        pushdown(u);
        int mid = lc + rc >> 1, ans = 0;
        if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r);
        if (r > mid) ans = Math.max(ans, query(tr[u].rs, mid + 1, rc, l, r));
        return ans;
    }
    void lazyCreate(int u) {if (tr[u] == null) tr[u] = new Node();
        if (tr[u].ls == 0) {tr[u].ls = ++cnt;
            tr[tr[u].ls] = new Node();}
        if (tr[u].rs == 0) {tr[u].rs = ++cnt;
            tr[tr[u].rs] = new Node();}
    }
    void pushdown(int u) {tr[tr[u].ls].add += tr[u].add; tr[tr[u].rs].add += tr[u].add;
        tr[tr[u].ls].max += tr[u].add; tr[tr[u].rs].max += tr[u].add;
        tr[u].add = 0;
    }
    void pushup(int u) {tr[u].max = Math.max(tr[tr[u].ls].max, tr[tr[u].rs].max);
    }
    public int book(int start, int end) {update(1, 1, N + 1, start + 1, end, 1);
        return query(1, 1, N + 1, 1, N + 1);
    }
}
  • 工夫复杂度：令 $n$ 为值域大小，本题固定为 $1e9$，线段树的查问和减少复杂度均为 $O(\log{n})$
  • 空间复杂度：令询问数量为 $m$，复杂度为 $O(m\log{n})$

带懒标记的分块（TLE）

实际上，还存在另外一种非常值得学习的算法：分块。

但该做法被奇怪的测评机制卡掉，是给每个样例都定了执行用时吗 🤣？

旧题解没有这种做法，明天补充的，咱们能够大略讲讲「分块」算法是如何解决波及「区间批改」，也就是带懒标记的问题。

对于本题，咱们设定两个块数组 max 和 add，其中 max[idx] 含意为块编号为 idx 的间断区间的最大反复值，而 add[idx] 代表块编号的懒标记，同时应用「哈希表」记录下某些具体位置的笼罩次数。

而后咱们思考如何指定块大小，设定一个正当的块大小是缩小运算量的要害。

通常状况下，咱们会设定块大小为 $\sqrt{n}$，从而确保块内最多不超过 $\sqrt{n}$ 个元素，同时块的总个数也不超过 $\sqrt{n}$，即无论咱们是块内暴力，还是操作多个块，复杂度均为 $O(\sqrt{n})$。因而对于本题而言，设定块大小为 $\sqrt{1e9}$（经试验，调成 $1200010$ 可能通过较多样例），较为适合。

对于波及「区间批改」的分块算法，咱们须要在每次批改和查问前，先将懒标记下传到区间的每个元素中。

而后思考如何解决「块内」和「块间」操作：

  • 块内操作：

    • 块内更新：间接操作 map 进行累加，同时应用更新后的 map 来保护相应的 max[idx]；
    • 块内查问：间接查问 map 即可；

  • 块间操作：

    • 块间更新：间接更新懒标记 add[idx] 即可，同时因为咱们是对整个区间进行累加操作，因而最大值必然也会同步被累加，因而同步更新 max[idx]；
    • 块间查问：间接查问 max[idx] 即可。

代码：

class MyCalendarThree {static int N = (int)1e9 + 10, M = 1200010, SZ = N / M + 10;
    static int[] max = new int[M], add = new int[M];
    static Map<Integer, Integer> map = new HashMap<>();
    int minv = -1, maxv = -1;
    int getIdx(int x) {return x / SZ;}
    void add(int l, int r) {pushdown(l); pushdown(r);
        if (getIdx(l) == getIdx(r)) {for (int k = l; k <= r; k++) {map.put(k, map.getOrDefault(k, 0) + 1);
                max[getIdx(k)] = Math.max(max[getIdx(k)], map.get(k));
            }
        } else {
            int i = l, j = r;
            while (getIdx(i) == getIdx(l)) {map.put(i, map.getOrDefault(i, 0) + 1);
                max[getIdx(i)] = Math.max(max[getIdx(i)], map.get(i));
                i++;
            }
            while (getIdx(j) == getIdx(r)) {map.put(j, map.getOrDefault(j, 0) + 1);
                max[getIdx(j)] = Math.max(max[getIdx(j)], map.get(j));
                j--;
            }
            for (int k = getIdx(i); k <= getIdx(j); k++) {max[k]++; add[k]++;
            }
        }
    }
    int query(int l, int r) {pushdown(l); pushdown(r);
        int ans = 0;
        if (getIdx(l) == getIdx(r)) {for (int k = l; k <= r; k++) ans = Math.max(ans, map.getOrDefault(k, 0));
        } else {
            int i = l, j = r;
            while (getIdx(i) == getIdx(l)) ans = Math.max(ans, map.getOrDefault(i++, 0));
            while (getIdx(j) == getIdx(r)) ans = Math.max(ans, map.getOrDefault(j--, 0));
            for (int k = getIdx(i); k <= getIdx(j); k++) ans = Math.max(ans, max[k]);
        }
        return ans;
    }
    void pushdown(int x) {int idx = getIdx(x);
        if (add[idx] == 0) return ;
        int i = x, j = x + 1;
        while (getIdx(i) == idx) map.put(i, map.getOrDefault(i--, 0) + add[idx]);
        while (getIdx(j) == idx) map.put(j, map.getOrDefault(j++, 0) + add[idx]);
        add[idx] = 0;
    }
    public MyCalendarThree() {Arrays.fill(max, 0);
        Arrays.fill(add, 0);
        map.clear();}
    public int book(int start, int end) {add(start + 1, end);
        minv = minv == -1 ? start : Math.min(minv, start);
        maxv = maxv == -1 ? end + 1 : Math.max(maxv, end + 1);
        return query(minv, maxv);
    }
}
  • 工夫复杂度：令 $M$ 为块大小，复杂度为 $O(\sqrt{M})$
  • 空间复杂度：$O(C \times \sqrt{M})$，其中 $C = 1e3$ 为最大调用次数

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.732 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

本文由 mdnice 多平台公布

退出移动版