题目地址：

https://leetcode.com/problems/amount-of-new-area-painted-each-day/description/

给定$n$个区间，每次将这段区间涂色，之前涂色过的区域就不重复涂，问每次涂色的涂到的长度。

可以用线段树 + 懒标记。这题区间端点范围是$[0,5\times 10^4]$，并不大，不需要离散化。代码如下：

class Solution {
public:
  struct Node {
    int l, r;
    int len;
    bool tag;
  };

  vector<Node> tr;
  vector<int> xs;

  int len(int u) { return tr[u].r - tr[u].l + 1; }
  void pushup(int u) { tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len; }
  void pushdown(int u) {
    if (tr[u].tag) {
      auto &l = tr[u << 1], &r = tr[u << 1 | 1];
      l.tag = r.tag = true;
      l.len = len(u << 1);
      r.len = len(u << 1 | 1);
      tr[u].tag = false;
    }
  }

  void build(int u, int l, int r) {
    tr[u] = {l, r, 0, false};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }

  int query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].len;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int res = 0;
    if (l <= mid) res += query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
  }

  void modify(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) {
      tr[u].len = len(u);
      tr[u].tag = true;
      return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r);
    if (r > mid) modify(u << 1 | 1, l, r);
    pushup(u);
  }

  vector<int> amountPainted(vector<vector<int>> &ps) {
    int l = 5e4, r = 0;
    for (auto &p : ps) l = min(l, p[0]), r = max(r, p[1] - 1);
    int n = r - l + 1;
    tr.resize(n << 2);
    build(1, l, r);
    vector<int> res;
    res.reserve(ps.size());
    for (auto &p : ps) {
      int len = p[1] - p[0], l = p[0], r = p[1] - 1;
      res.push_back(len - query(1, l, r));
      modify(1, l, r);
    }
    return res;
  }
};

时间复杂度$O(n\log R)$（$R$是区间端点的范围），空间$O(R)$。

最好的做法是并查集。每个点$x$定义其祖宗为$[x,+\infty ]$最小的没有被涂色的位置，所以一开始$p[x]=x$。那么涂色的操作就是不停找祖宗的过程。代码如下：

class Solution {
public:
  vector<int> amountPainted(vector<vector<int>> &ps) {
    vector<int> p(5e4 + 2);
    iota(p.begin(), p.end(), 0);
    auto find = [&](this auto &&find, int x) -> int {
      return x == p[x] ? x : p[x] = find(p[x]);
    };
    vector<int> res;
    res.reserve(ps.size());
    for (auto &w : ps) {
      int cnt = 0;
      for (int i = find(w[0]); i < w[1]; i = find(i)) {
        // 将i挂在i + 1下面
        p[i] = i + 1;
        // 涂色
        cnt++;
      }
      res.push_back(cnt);
    }
    return res;
  }
};

时间复杂度$O(n{\log }^{\ast }R)$，空间$O(R)$。