首页 > 其他分享 >P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

时间:2024-03-30 10:22:38浏览次数:23  
标签:p2 p1 rs int P4556 线段 ls Vani 模板

P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

在这题里面讲一下线段树合并。顾名思义就是把多个线段树合并成一个。

显然完全二叉线段树(也就是普通线段树)是无法更高效的合并的,只能把所有节点加起来建个新树。但是在动态开点线段树中,有时候一个树只有几条链,这时候我们就是可以使用线段树合并了。

其核心就是只遍历两棵树重叠的部分实现合并。具体的,对于两棵线段树 \(p1\),\(p2\),我们要把 \(p2\) 合并到 \(p1\) 上。不妨先考虑左儿子,假如两个线段树都有左儿子,那么就往下遍历;假如只有 \(p1\) 有左儿子,显然不需要修改;假如只有 \(p2\) 有左儿子,\(p1\) 没有记录信息,那么只需要把 \(p1\) 左儿子的指针改成 \(p2\) 左儿子的指针即可。复杂度不会严格证明,一般所有线段树的总节点个数为 \(O(n\log n)\),合并时遍历到的只有重叠部分,非重叠部分没有遍历,所以每个线段树的节点至多被遍历一次,所以时间复杂度是 \(O(n\log n)\)。

void mg(int p1, int p2, int l, int r) {
	if(l == r) {
		.....
		return;
	}
	int mid = (l + r) >> 1;
	if(t[p1].ls && t[p2].ls) mg(t[p1].ls, t[p2].ls, l, mid);
	else if(t[p2].ls) t[p1].ls = t[p2].ls;
	if(t[p1].rs && t[p2].rs) mg(t[p1].rs, t[p2].rs, mid + 1, r);
	else if(t[p2].rs) t[p1].rs = t[p2].rs;
	pushup(p1, t[p1].ls, t[p1].rs);
}

回到这题,容易想到树上差分,然后把操作拆成 \(4\) 个单点修改,离线在树上线段树合并即可。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

typedef long long i64;
const int N = 1e5 + 10;
int n, m, cnt;
int dep[100010], anc[100010][21], h[100010];
struct node{
	int to, nxt;
} e[200010];
void add(int u, int v) {
	e[++cnt].to = v;
	e[cnt].nxt = h[u];
	h[u] = cnt;
}
void dfs(int u, int fa) {
	for(int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa) continue;
		anc[v][0] = u;
		dep[v] = dep[u] + 1;
		dfs(v, u);
	} 
}
void init() {
	for(int j = 1; j <= 19; j++) {
		for(int i = 1; i <= n; i++) {
			anc[i][j] = anc[anc[i][j - 1]][j - 1];
		}
	}
}
int lca(int u, int v) {
	if(dep[u] < dep[v]) std::swap(u, v);
	for(int i = 19; i >= 0; i--) if(dep[anc[u][i]] >= dep[v]) u = anc[u][i];
	if(u == v) return u;
	for(int i = 19; i >= 0; i--) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
	return anc[u][0];
}
int tot;
std::vector<pii> ve[N];
struct seg {
	int ls, rs, mx, cnt;
} t[40 * N];
void pushup(int u, int ls, int rs) {
	if(t[ls].cnt >= t[rs].cnt && t[ls].cnt) {
		t[u].cnt = t[ls].cnt;
		t[u].mx = t[ls].mx;
	} else if(t[ls].cnt <= t[rs].cnt && t[rs].cnt) {
		t[u].cnt = t[rs].cnt;
		t[u].mx = t[rs].mx;
	} else {
		t[u].cnt = t[u].mx = 0;
	}
	return;
}
void ins(int &u, int l, int r, int x, int y) {
	if(!u) u = ++tot;
	if(l == r) {
		t[u].cnt += y;
		t[u].mx = t[u].cnt ? l : 0;
		return;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) ins(t[u].ls, l, mid, x, y);
	else ins(t[u].rs, mid + 1, r, x, y);
	pushup(u, t[u].ls, t[u].rs);
}
void mg(int p1, int p2, int l, int r) {
	if(l == r) {
		t[p1].cnt += t[p2].cnt;
		t[p1].mx = t[p1].cnt ? l : 0;
		return;
	}
	int mid = (l + r) >> 1;
	if(t[p1].ls && t[p2].ls) mg(t[p1].ls, t[p2].ls, l, mid);
	else if(t[p2].ls) t[p1].ls = t[p2].ls;
	if(t[p1].rs && t[p2].rs) mg(t[p1].rs, t[p2].rs, mid + 1, r);
	else if(t[p2].rs) t[p1].rs = t[p2].rs;
	pushup(p1, t[p1].ls, t[p1].rs);
}
int ans[N];
void dfs2(int u, int fa) {
	for(int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa) continue;
		dfs2(v, u);
		mg(u, v, 1, 1e5);
	}
	for(auto x : ve[u]) ins(u, 1, 1e5, x.fi, x.se);
	ans[u] = t[u].mx;
}
void Solve() {
	std::cin >> n >> m;
	tot = n;
	for(int i = 1; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		add(u, v), add(v, u);
	}
	dep[1] = 1;
	dfs(1, 0);
	init();
	while(m--) {
		int u, v, w;
		std::cin >> u >> v >> w;
		int rt = lca(u, v);
		ve[u].push_back({w, 1}), ve[v].push_back({w, 1});
		ve[rt].push_back({w, -1}), ve[anc[rt][0]].push_back({w, -1});
	}
	dfs2(1, 0);
	for(int i = 1; i <= n; i++) std::cout << ans[i] << "\n";
}

int main() {
	
	Solve();

	return 0;
}

标签:p2,p1,rs,int,P4556,线段,ls,Vani,模板
From: https://www.cnblogs.com/FireRaku/p/18105162

相关文章

  • 类模板
    1.类模板的基本范例和模板参数的推断基本范例:类模板,也是生产类的工具,通过给定的模板参数,生成具体的类。类模板的声明和实现一般都放在同一个头文件中,因为实例化的时候必须有类模板的全部信息。template<typenameT>//T表示myvector这个容器所存储的元素类型classmyvector......
  • 类模板中的友元
    1.友元类传统友元类的概念是:让某个类B成为另外一个类A的友元类,这样的话,类B就可以在其成员函数中访问类A的所有成员(成员变量、成员函数),而不管这些成员在类A中是用什么修饰符(private、protected、public)修饰的。如果现在类A和类B都变成了类模板,那么能否让类模板B成为类模板A的友元......
  • C++精品小案例:C++中的多态性及其实现、模板元编程及其在C++中的应用
    1.C++中的多态性及其实现多态性是面向对象编程的三大特性之一,它允许使用父类类型的指针或引用来指向子类对象,并通过这个父类类型的指针或引用来调用实际子类的成员函数。这样,就可以在运行时确定应该调用哪个具体的函数实现,从而实现一个接口多种形态。多态性主要通过虚函数来......
  • WPF中使用PDF模板实现PDF导出和预览-来自GPT4
    在C#和WPF项目中实现加载不同的PDF模板、查看报告和导出PDF文件的功能,可以通过以下步骤完成:1.选择PDF库首先,选择一个合适的.NETPDF库。有许多库可以帮助你处理PDF文件,包括但不限于:iTextSharp:一个功能强大的和灵活的库,适用于创建和修改PDF文件。它是iText的一个.NET端口。......
  • 【Vue】模板语法
    用js完成输出输入框中的值到列表中constbuttonEl=document.querySelector('button');constinputEl=document.querySelector('input');constlistEl=document.querySelector('ul')0;functionaddGoal(){ constenteredValue=inputEl.value; c......
  • 【模板】快速读入
    1inlineintread()2{3intw=0,s=1;4charch=getchar();5while(ch<'0'||ch>'9')6{7if(ch=='-')s=-1;8ch=getchar();9}10while(ch>='0'&&ch<='9')11{12w=w*10+ch......
  • 软件项目管理全套文档模板(开发/实施/运维/安全/交付)
     前言:在软件项目管理中,每个阶段都有其特定的目标和活动,确保项目的顺利进行和最终的成功交付。以下是软件项目管理各个阶段的详细资料:软件项目全套文档资料下载:点我获取1.需求阶段目标:收集、分析和定义用户需求和业务目标。主要活动:需求调研:与用户沟通,了解他们的需求和......
  • FLASK学习记录-宏、模板继承
    宏{%macroname%}{%endmacro%}app.pyfromflaskimportFlask,render_templateapp=Flask(__name__)@app.route('/')defindex1():returnrender_template("macro1.html")@app.route("/")defindex2():returnrend......
  • 软件项目管理全套通用模板(规格说明书~详细设计~测试计划~验收报告)
     前言:在软件开发过程中,文档资料是非常关键的一部分,它们帮助团队成员理解项目需求、设计、实施、测试、验收等各个环节,确保项目的顺利进行。以下是针对您提到的各个阶段的文档资料概述:所有资料获取:点击获取开发阶段需求规格说明书:详细描述了软件系统的功能需求、非功能......
  • 写模板,线段树
    1意义:线段是是为了对区间中的元素进行操作,而衍生出来的一种数据结构,比如区间加减,区间求和。线段树将1~n的区间分解成4n个小区间。2过程:区间修改就是对一个或者多个节点按照设定的规则对数值进行修改。区间查询就是对一个或多个节点查询的结果按规则进行合并,得到最终结果。其......