能干什么/局限性
高效处理区间平推(区间赋值)的问题。
在随机数据下飞快。
如果没有区间平推,或者区间平推的操作数量可以被卡得很少甚至没有,就不适用。
前置知识
set
没了。
建点
每个点要维护一个区间,以及这个区间的信息。表示这个区间的信息都是相等的。
所有的点维护的区间都没有交集,且并集就是的区间就是 \(1\sim n\)。
struct node{int l,r; //维护的区间mutable int val; //维护的信息//mutable 表示可以直接在 set 中修改node(int L,int R=-1,int VAL=0){l=L,r=R,val=VAL;}bool operator<(const node&other)const{return l<other.l;}
};
set<node> odt;
分裂(split)
传进去一个参数 \(pos\),表示把包含 \(pos\) 的区间 \([l,r]\),分裂成 \([l,pos-1]\) 和 \([pos,r]\),并返回后一个区间的迭代器。
特别地,若 \(pos\) 所在的区间的左端点就是 \(pos\),那么不分裂直接返回这个区间。
auto split(int pos){auto it=odt.lower_bound(node(pos));if(it!=odt.end() && it->l==pos) return it; //特判it--;int l=it->l,r=it->r,val=it->val;odt.erase(it);odt.insert(node(l,pos-1,val)); //每个点维护的区间信息都是相同的return odt.insert(node(pos,r,val)).first;
}
平推(assgin)
如果只分裂那肯定是不行的,复杂度只会越来越高。
平推就是可以把一堆区间赋值成相同的,就可以合并起来。这也是 ODT 必须要有的平推操作,而且这也关乎到复杂度。
void assgin(int l,int r,int k){auto itr=split(r+1),itl=split(l);odt.erase(itl,itr);odt.insert(node(l,r,k));
}
所有的 ODT 的题必须要有的操作就这俩。
剩下的就全看实际题目了。