医院网站建设 中企动力,wordpress 打开速度慢,厦门长实建设有限公司网站,做视频资源网站有哪些内容前置知识#xff1a;权值线段树#xff0c;动态开点。
引入
我们先来看一道题#xff1a;
永无乡包含 nnn 座岛#xff0c;给出每座岛的重要度的排名#xff0c;名次用 111 到 nnn 来表示。一开始有 mmm 条边连接#xff0c;接下来有 qqq 次操作。操作分两种#xff…前置知识权值线段树动态开点。
引入
我们先来看一道题
永无乡包含 nnn 座岛给出每座岛的重要度的排名名次用 111 到 nnn 来表示。一开始有 mmm 条边连接接下来有 qqq 次操作。操作分两种
B x y 表示在岛与岛之间修建一座新桥。Q x k 表示询问当前与岛连通的所有岛中第重要的是哪座岛。
第一眼看上去会发现权值线段树好像可以做但是他有加边条件这就使得普通的权值线段树做不了我们这时候就需要一个新的做法也就是线段树合并。
思路
线段树合并的一个重要前提就是你们根节点的区间是相同的。
我们合并两棵线段树其实就相当于将一棵线段树的信息附在另一棵线段树上面。
我们假设我们要合并线段树 AAA 和线段树 BBB 且把线段树 BBB 的信息附在线段树 AAA 上。
我们可以从根节点同时往下枚举分以下几种情况。
如果这个点线段树 AAA 和线段树 BBB 都有那么我们继续往下枚举。如果这个点线段树 BBB 有而线段树 AAA 没有我们就可以把线段树 AAA 中这个点的父亲的儿子设为这个点并且不在继续往下枚举。如果这个点线段树 AAA 有而线段树 BBB 没有我们就可以不再往下枚举。如果这个点线段树 AAA 和线段树 BBB 都没有我们也可以不用再往下枚举了。
到此我们线段树就合并完了。
代码
void merge(int x1, int x2, int l, int r) {//x1是线段树A现在枚举到的节点x2是线段树B现在枚举到的节点l、r实现再枚举到的区间。if (!x1 || !x2)//如果这个节点线段树A没有或者线段树B没有x1 x1 x2;//因为这两个点至少一个是0所以他们的和就是另外一个点。else {int mid (l r) / 2;merge(tree[x1].lson, tree[x2].lson, l, mid);merge(tree[x1].rson, tree[x2].rson, mid 1, r);updata(x1);//记得合并完后要更新这个节点}
}例题
永无乡洛谷[USACO17JAN]Promotion Counting P洛谷
