河田镇建设局网站,网络优化网站,wordpress取消评论,网上做广告怎么收费基本概念#xff1a; 如果需要维护许多个大小为 \(10^5\) 级别的多重集#xff0c;可以看做给每一个多重集建立一棵线段树。线段树的合并、分裂就是多重集的累加、分开。 这里使用动态开点的方式存储线段树树。 如果一个节点为空#xff0c;那么它的编号为 \(0\) 。 变量释义… 基本概念 如果需要维护许多个大小为 \(10^5\) 级别的多重集可以看做给每一个多重集建立一棵线段树。线段树的合并、分裂就是多重集的累加、分开。 这里使用动态开点的方式存储线段树树。 如果一个节点为空那么它的编号为 \(0\) 。 变量释义 有 \(cnt\) 个多重集 建立了 \(tot\) 个节点 若一个多重集的编号为 \(x\) 它的根节点编号为 \(root[x]\) 注意空间是个谜能开多大是多大 线段树合并 把以 \(y\) 为根的线段树合并到以 \(x\) 为根的线段树 int merge(int x,int y,int nl,int nr) // i:y-x
{if(!x || !y) return xy;int mid(nlnr)1;//tree[x].sumtree[y].sum; 根据题目改动tree[x].lsmerge(tree[x].ls,tree[y].ls,nl,mid);tree[x].rsmerge(tree[x].rs,tree[y].rs,mid1,nr);//pushup(x);del(y);return x;
} 复杂度 \(\) 节点数 ( 一般均摊下来可以达到一次操作 \(O(\log n)\) 的级别 ) 线段树分裂 把以 \(x\) 为根的线段树中 \(\ge k\) 的数转移到一棵 空的 线段树 \(y\) 。 void split(int x,int y,int nl,int nr,int k) // ik i:x-y
{if(!x) xtot;if(!y) ytot;if(nlnr) { swap(x,y); return; }int mid(nlnr)1;if(midk){swap(tree[x].rs,tree[y].rs);split(tree[x].ls,tree[y].ls,nl,mid,k);}else split(tree[x].rs,tree[y].rs,mid1,nr,k);pushup(x),pushup(y);
} 例题 P5494 【模板】线段树分裂 \(\rightarrow\) 模板代码
