贷款 东莞网站建设,网站后台版权,1000个免费邮箱账号,打车软件开发所谓珂朵莉树#xff0c;就是珂朵莉发明的树。 #xff08;逃
前言
在数据随机且带区间推平操作时适用#xff0c;此时所有操作的期望颜色段数都是 O(logn)O(\log n)O(logn) 的#xff0c;可以使用暴力解决即可。 暴力即优雅。
解析
利用 set 维护颜色段#xff1a;… 所谓珂朵莉树就是珂朵莉发明的树。 逃
前言
在数据随机且带区间推平操作时适用此时所有操作的期望颜色段数都是 O(logn)O(\log n)O(logn) 的可以使用暴力解决即可。 暴力即优雅。
解析
利用 set 维护颜色段
struct node{int l,r;ll v;node(int L0,int R0,ll V0):l(L),r(R),v(V){}bool operator (const node oth)const{return loth.l;}
};
bool cmp(const node x,const node y){return x.vy.v;
}
setnodes;split
分裂出以 ppp 为左端点的颜色段并返回迭代器。
It split(int p){It its.lower_bound((node){p,0,0});if(it!s.end()(*it).lp) return it;it--;if((*it).rp) return s.end();int l(*it).l;int r(*it).r;ll v(*it).v;s.erase(it);s.insert((node){l,p-1,v});return s.insert((node){p,r,v}).first;
}assign
对 (l,r)(l,r)(l,r) 区间颜色推平。 必须先 split(r1)split(r1)split(r1)再 split(l)split(l)split(l)不然可能会RE 然而由于随机数据RE的概率其实不大。
inline void assign(int l,int r,int w){It itrsplit(r1),itlsplit(l);s.erase(itl,itr);s.insert((node){l,r,w});
}
