统计区间中的整数数目

输入 ["CountIntervals", "add", "add", "count", "add", "count"] [[], [2, 3], [7, 10], [], [5, 8], []] 输出 [null, null, null, 6, null, 8] 解释 CountIntervals countIntervals = new CountIntervals(); // 用一个区间空集初始化对象 countIntervals.add(2, 3); // 将 [2, 3] 添加到区间集合中 countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中 countIntervals.count(); // 返回 6 // 整数 2 和 3 出现在区间 [2, 3] 中 // 整数 7、8、9、10 出现在区间 [7, 10] 中 countIntervals.add(5, 8); // 将 [5, 8] 添加到区间集合中 countIntervals.count(); // 返回 8 // 整数 2 和 3 出现在区间 [2, 3] 中 // 整数 5 和 6 出现在区间 [5, 8] 中 // 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中 // 整数 9 和 10 出现在区间 [7, 10] 中

上次编辑到这里，代码来自缓存点击恢复默认模板

class CountIntervals { public: CountIntervals() { } void add(int left, int right) { } int count() { } }; /** * Your CountIntervals object will be instantiated and called as such: * CountIntervals* obj = new CountIntervals(); * obj->add(left,right); * int param_2 = obj->count(); */

class CountIntervals { map<int, int> m; int cnt = 0; // 所有区间长度和 public: CountIntervals() {} void add(int left, int right) { // 遍历所有被 [left,right] 覆盖到的区间（部分覆盖也算） for (auto it = m.lower_bound(left); it != m.end() && it->second <= right; m.erase(it++)) { int l = it->second, r = it->first; left = min(left, l); // 合并后的新区间，其左端点为所有被覆盖的区间的左端点的最小值 right = max(right, r); // 合并后的新区间，其右端点为所有被覆盖的区间的右端点的最大值 cnt -= r - l + 1; } cnt += right - left + 1; m[right] = left; // 所有被覆盖到的区间与 [left,right] 合并成一个新区间 } int count() { return cnt; } }; /** * Your CountIntervals object will be instantiated and called as such: * CountIntervals* obj = new CountIntervals(); * obj->add(left,right); * int param_2 = obj->count(); */

class CountIntervals { CountIntervals *left = nullptr, *right = nullptr; int l, r, cnt = 0; public: CountIntervals() : l(1), r(1e9) {} CountIntervals(int l, int r) : l(l), r(r) {} void add(int L, int R) { // 为方便区分变量名，将递归中始终不变的入参改为大写（视作常量） if (cnt == r - l + 1) return; // 当前节点已被完整覆盖，无需执行任何操作 if (L <= l && r <= R) { // 当前节点已被区间 [L,R] 完整覆盖，不再继续递归 cnt = r - l + 1; return; } int mid = (l + r) / 2; if (left == nullptr) left = new CountIntervals(l, mid); // 动态开点 if (right == nullptr) right = new CountIntervals(mid + 1, r); // 动态开点 if (L <= mid) left->add(L, R); if (mid < R) right->add(L, R); cnt = left->cnt + right->cnt; } int count() { return cnt; } }; /** * Your CountIntervals object will be instantiated and called as such: * CountIntervals* obj = new CountIntervals(); * obj->add(left,right); * int param_2 = obj->count(); */

class CountIntervals { CountIntervals left, right; int l, r, cnt; public CountIntervals() { l = 1; r = (int) 1e9; } CountIntervals(int l, int r) { this.l = l; this.r = r; } public void add(int L, int R) { // 为方便区分变量名，将递归中始终不变的入参改为大写（视作常量） if (cnt == r - l + 1) return; // 当前节点已被完整覆盖，无需执行任何操作 if (L <= l && r <= R) { // 当前节点已被区间 [L,R] 完整覆盖，不再继续递归 cnt = r - l + 1; return; } int mid = (l + r) / 2; if (left == null) left = new CountIntervals(l, mid); // 动态开点 if (right == null) right = new CountIntervals(mid + 1, r); // 动态开点 if (L <= mid) left.add(L, R); if (mid < R) right.add(L, R); cnt = left.cnt + right.cnt; } public int count() { return cnt; } } /** * Your CountIntervals object will be instantiated and called as such: * CountIntervals obj = new CountIntervals(); * obj.add(left,right); * int param_2 = obj.count(); */

// 珂朵莉树 class CountIntervals { TreeMap<Integer, Integer> m = new TreeMap<>(); int cnt; // 所有区间长度和 public CountIntervals() {} public void add(int left, int right) { // 遍历所有被 [left,right] 覆盖到的区间（部分覆盖也算） for (var e = m.ceilingEntry(left); e != null && e.getValue() <= right; e = m.ceilingEntry(left)) { int l = e.getValue(), r = e.getKey(); left = Math.min(left, l); // 合并后的新区间，其左端点为所有被覆盖的区间的左端点的最小值 right = Math.max(right, r); // 合并后的新区间，其右端点为所有被覆盖的区间的右端点的最大值 cnt -= r - l + 1; m.remove(r); } cnt += right - left + 1; m.put(right, left); // 所有被覆盖到的区间与 [left,right] 合并成一个新区间 } public int count() { return cnt; } } /** * Your CountIntervals object will be instantiated and called as such: * CountIntervals obj = new CountIntervals(); * obj.add(left,right); * int param_2 = obj.count(); */

type CountIntervals struct { *redblacktree.Tree cnt int // 所有区间长度和 } func Constructor() CountIntervals { return CountIntervals{redblacktree.NewWithIntComparator(), 0} } func (t *CountIntervals) Add(left, right int) { // 遍历所有被 [left,right] 覆盖到的区间（部分覆盖也算） for node, _ := t.Ceiling(left); node != nil && node.Value.(int) <= right; node, _ = t.Ceiling(left) { l, r := node.Value.(int), node.Key.(int) if l < left { left = l } // 合并后的新区间，其左端点为所有被覆盖的区间的左端点的最小值 if r > right { right = r } // 合并后的新区间，其右端点为所有被覆盖的区间的右端点的最大值 t.cnt -= r - l + 1 t.Remove(r) } t.cnt += right - left + 1 t.Put(right, left) // 所有被覆盖到的区间与 [left,right] 合并成一个新区间 } func (t *CountIntervals) Count() int { return t.cnt } /** * Your CountIntervals object will be instantiated and called as such: * obj := Constructor(); * obj.Add(left,right); * param_2 := obj.Count(); */

type CountIntervals struct { left, right *CountIntervals l, r, cnt int } func Constructor() CountIntervals { return CountIntervals{l: 1, r: 1e9} } func (o *CountIntervals) Add(l, r int) { if o.cnt == o.r-o.l+1 { return } // o 已被完整覆盖，无需执行任何操作 if l <= o.l && o.r <= r { // 当前节点已被区间 [l,r] 完整覆盖，不再继续递归 o.cnt = o.r - o.l + 1 return } mid := (o.l + o.r) >> 1 if o.left == nil { o.left = &CountIntervals{l: o.l, r: mid} } // 动态开点 if o.right == nil { o.right = &CountIntervals{l: mid + 1, r: o.r} } // 动态开点 if l <= mid { o.left.Add(l, r)} if mid < r { o.right.Add(l, r) } o.cnt = o.left.cnt + o.right.cnt } func (o *CountIntervals) Count() int { return o.cnt } /** * Your CountIntervals object will be instantiated and called as such: * obj := Constructor(); * obj.Add(left,right); * param_2 := obj.Count(); */

''' 动态开点线段树 ''' class CountIntervals: __slots__ = 'left', 'right', 'l', 'r', 'cnt' def __init__(self, l=1, r=10 ** 9): self.left = self.right = None self.l, self.r, self.cnt = l, r, 0 def add(self, l: int, r: int) -> None: if self.cnt == self.r - self.l + 1: return # self 已被完整覆盖，无需执行任何操作 if l <= self.l and self.r <= r: # self 已被区间 [l,r] 完整覆盖，不再继续递归 self.cnt = self.r - self.l + 1 return mid = (self.l + self.r) // 2 if self.left is None: self.left = CountIntervals(self.l, mid) # 动态开点 if self.right is None: self.right = CountIntervals(mid + 1, self.r) # 动态开点 if l <= mid: self.left.add(l, r) if mid < r: self.right.add(l, r) self.cnt = self.left.cnt + self.right.cnt def count(self) -> int: return self.cnt # Your CountIntervals object will be instantiated and called as such: # obj = CountIntervals() # obj.add(left,right) # param_2 = obj.count()

''' 方法一：珂朵莉树用一颗平衡树维护若干个不相交的区间，每次 add(left,right) 时，删除被该区间覆盖到的区间（部分覆盖也算），然后将这些区间与 [left,right] 合并成一个新的大区间，插入平衡树中。 ''' from sortedcontainers import SortedDict class CountIntervals: def __init__(self): self.d = SortedDict() self.cnt = 0 # 所有区间长度和 def add(self, left: int, right: int) -> None: # 遍历所有被 [left,right] 覆盖到的区间（部分覆盖也算） i = self.d.bisect_left(left) while i < len(self.d) and self.d.values()[i] <= right: r, l = self.d.items()[i] left = min(left, l) # 合并后的新区间，其左端点为所有被覆盖的区间的左端点的最小值 right = max(right, r) # 合并后的新区间，其右端点为所有被覆盖的区间的右端点的最大值 self.cnt -= r - l + 1 self.d.popitem(i) self.cnt += right - left + 1 self.d[right] = left # 所有被覆盖到的区间与 [left,right] 合并成一个新区间 def count(self) -> int: return self.cnt # Your CountIntervals object will be instantiated and called as such: # obj = CountIntervals() # obj.add(left,right) # param_2 = obj.count()

详情