预约网免费建站流程,网站建设需要具备哪些知识,怎样做代刷网站,阳江网吧珂朵莉树 ODT 主要内容 珂朵莉树是基于数据随机且有整体赋值操作而对序列操作的乱搞算法。 它的主要思想是用 set 维护若干个数值上相同的区间#xff0c;并暴力处理其他询问。 建立 在 set 中#xff0c;我们需要用结构体记录每个区间的信息#xff1a; struct NODE
{int l… 珂朵莉树 ODT 主要内容 珂朵莉树是基于数据随机且有整体赋值操作而对序列操作的乱搞算法。 它的主要思想是用 set 维护若干个数值上相同的区间并暴力处理其他询问。 建立 在 set 中我们需要用结构体记录每个区间的信息 struct NODE
{int l,r;mutable ll val; // mutable 表示可变的便于在外边修改 val 的值NODE(int L,int R-1,ll Val0):l(L),r(R),val(Vol){} // 相当于 (NODE){l,r,val}bool friend operator (NODE x,NODE y) { return x.ly.l; } // 重载
};
setNODE s; 这样再 set 中就可以自动按照左端点排序了注意在初始化的时候加入 \([n1,n1]\) 的区间。 split 珂朵莉树用 split 操作分裂出一堆区间后暴力操作。 inline auto split(int p)
{auto its.lower_bound(NODE(p));if(it!s.end() it-lp) return it;it--;int lit-l,rit-r;ll vit-val;s.erase(it);s.insert(NODE(l,p-1,v));return s.insert(NODE(p,r,v)).fi;
} assign 如果只有 split 操作那 set 中元素岂不是爆炸我们需要时不时将一些区间合并为一个区间才能保证复杂度。 \(\bigstar\texttt{attention}\)在推平的时候需要先 split 右端点再左端点否则会 RE inline void assign(int l,int r,int v)
{auto itrs.split(r1),itls.split(l);s.erase(itl,itr); // 用将 [itl,itr) 之间的元素全部删除s.insert(NODE(l,r,v));
} 其他操作 其他操作就可以直接暴力在 set 中搞了下面以求区间内每个数的平方的和为例 inline ll query(int l,int r)
{auto itrs.split(r1),itls.split(l);ll ret0;for(auto ititl;it!itr;it)ret1ll*(it-r-it-l1)*it-v*it-v;return ret;
} 复杂度 如果只有推平操作即不需要将这个区间拎出来暴力处理复杂度是 \(\mathcal{O(n\log n)}\)。 如果有区间加等操作就要基于数据随机了这种情况下一定时间内进行一次推平可以达到 \(\mathcal{O(m\log n)}\) 的复杂度。 例题 起源题CF896C Willem, Chtholly and Seniorious。 CF1638E Colorful Operations 在询问的时候把答案累加上去再套上一个树状数组利用前缀和维护区间加即可。 CF1423G Growing flowers 给你一个序列支持以下两种操作 区间推平即将 \([l,r]\) 中的数都改为同一个数 \(x\)。求序列中所有长度为 \(k\) 的子段中不同数的个数的和。 \(n,q\le 10^5\)。 MatrixCascade这题 800。 区间推平所以考虑珂朵莉树。发现如果每次询问的时候再去统计复杂度至少是和区间个数同阶不可取。 考虑在推平的过程中更新答案。 将即将被推平的区间拎出来将他们对答案减小的贡献减去。 对每一种数建立一个 set再用线段树记录方案数即可。
