题意
样例
数据范围
代码
- 动态开点
class CountIntervals { CountIntervals *left = nullptr, *right = nullptr; int l, r, sum = 0; public: CountIntervals() :l(1), r(1e9) {} CountIntervals(int l, int r) :l(l), r(r) {} void add(int L, int R) { if(sum >= r - l + 1) return ; // 到该已经覆盖完的节点，不用向下走了 if(l >= L && r <= R) { sum = r - l + 1; return ; } // 该节点能被完全覆盖 int mid = (l + r) >> 1; 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(R > mid) right->add(L, R); sum = left->sum + right->sum; } int count() { return sum; } }; /** * Your CountIntervals object will be instantiated and called as such: * CountIntervals* obj = new CountIntervals(); * obj->add(left,right); * int param_2 = obj->count(); */
- set集合，二分
class CountIntervals { public: #define PII pair<int, int> set<PII> s; // <R, L>，存的是R，L int res = 0; CountIntervals() {} // 以右端点排 void add(int left, int right) { int l = left, r = right; // 找到第一个右端点>l， 即从相交的开始。 auto it = s.lower_bound(PII{l, -1e9}); // 向后找到第一个左端点>r，即不在相交了 while(it != s.end()) { if(it->second > r) break; // 维护最终合并完的最小l，最大r l = min(it->second, l); r = max(it->first, r); // 减去所有找到的区间值 res -= it->first - it->second + 1; s.erase(it++); } // 加上最终合并的区间值 res += r - l + 1; // 在插入当前合并的区间 s.insert(PII{r, l}); } int count() { return res; } }; /** * Your CountIntervals object will be instantiated and called as such: * CountIntervals* obj = new CountIntervals(); * obj->add(left,right); * int param_2 = obj->count(); */
