【线段树专题】求解常见「值域爆炸，查询有限」区间问题的几种方式

宫水三叶的刷题日记

发布于 2022-05-27 14:17:12

3620

发布于 2022-05-27 14:17:12

文章被收录于专栏：宫水三叶的刷题日记宫水三叶的刷题日记

题目描述

示例：

输入：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]

输出：
[null, true, false, true]

解释：
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False ，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。
myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20 ，且不包含时间 20 。

模拟

代码：

class MyCalendar {
    List<int[]> list = new ArrayList<>();
    public boolean book(int start, int end) {
        end--;
        for (int[] info : list) {
            int l = info[0], r = info[1];
            if (start > r || end < l) continue;
            return false;
        }
        list.add(new int[]{start, end});
        return true;
    }
}

有序集合（红黑树）

解法一中，每次的 book 操作我们都不可避免的需要遍历所有已存在的日期。

实际上，如果我们使用 TreeMap（底层为红黑树）来维护所有日期，可以避免对所有已存在的日期进行遍历。

代码：

class MyCalendar {
    TreeMap<Integer, Integer> tm = new TreeMap<>();    
    public boolean book(int start, int end) {
        Integer prev = tm.floorKey(start), next = tm.ceilingKey(start);
        if ((prev == null || tm.get(prev) <= start) && (next == null || end <= next)) {
            tm.put(start, end);
            return true;
        }
        return false;
    }
}

线段树（动态开点）

代码：

class MyCalendar {
    class Node {
        // ls 和 rs 分别代表当前节点的左右子节点在 tr 的下标
        // val 代表当前节点有多少数
        // add 为懒标记
        int ls, rs, add, val;
    }
    int N = (int)1e9, M = 120010, 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].val += (rc - lc + 1) * v;
            tr[u].add += v;
            return ;
        }
        lazyCreate(u);
        pushdown(u, rc - lc + 1);
        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].val;
        lazyCreate(u);
        pushdown(u, rc - lc + 1);
        int mid = lc + rc >> 1, ans = 0;
        if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r);
        if (r > mid) 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, int len) {
        tr[tr[u].ls].add += tr[u].add; tr[tr[u].rs].add += tr[u].add;
        tr[tr[u].ls].val += (len - len / 2) * tr[u].add; tr[tr[u].rs].val += len / 2 * tr[u].add;
        tr[u].add = 0;
    }
    void pushup(int u) {
        tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
    }
    public boolean book(int start, int end) {
        if (query(1, 1, N + 1, start + 1, end) > 0) return false;
        update(1, 1, N + 1, start + 1, end, 1);
        return true;
    }
}