题解 P2082 【区间覆盖(加强版)】

操作只有区间赋值，emmm... ## 用珂朵莉树啊！（第一反应真的是这个 [【暴力数据结构Warning】Chtholly Tree珂朵莉树](https://www.luogu.org/blog/ACdreamer/chtholly-tree) 把连续的区间存在```std::set```之中，区间覆盖的时候把这一段```split```出来，然后更改这段区间的```val```。最后把整个```set```遍历一边即可获得答案。 当然这题动态开点线段树也是可以的。 ``` #include<cstdio> #include<cctype> #include<set> #define LL long long using std::set; #define IT set<node>::iterator LL Read() { LL x=0;char c=getchar(); while(!isdigit(c)) { c=getchar(); } while(isdigit(c)) { x=x*10+(c^48); c=getchar(); } return x; } struct node { LL l,r; mutable int v; //由于需要修改，此处的v需要mutable修饰 node(LL L, LL R=-1, int V=0):l(L), r(R), v(V) {} bool operator<(const node& o) const { return l < o.l; } }; set<node> s; //split(pos)操作将原来含有pos位置的节点分成两部分：[l,pos−1]和[pos,r] IT split(LL pos) { IT it = s.lower_bound(node(pos)); if (it != s.end() && it->l == pos) return it; --it; LL L = it->l, R = it->r; LL V = it->v; s.erase(it); s.insert(node(L, pos-1, V)); return s.insert(node(pos, R, V)).first; //这里利用了pair<iterator,bool> insert (const value_type& val)的返回值 } void assign_val(LL l, LL r) { IT itr = split(r+1),itl = split(l); s.erase(itl, itr); //void erase (iterator first, iterator last)可删除[first,last)区间 s.insert(node(l, r, 1)); } LL sum(LL l, LL r) { //这个没啥好说的，遍历一遍 IT itr = split(r+1),itl = split(l); LL res = 0; for (; itl != itr; ++itl) res += itl->v ? itl->r - itl->l + 1 : 0; return res; } int main() { int n=Read(); LL l,r; s.insert(node(0,1e17+5)); //插入一个[0,1e17+5]，值全部为0的区间 while(n--) { l=Read(); r=Read(); assign_val(l,r); } printf("%lld",sum(0,1e17+3)); return 0; } ```