首页 > 其他分享 >就像STL那样：封装的动态开点线段树（用于线段树合并）

就像STL那样：封装的动态开点线段树（用于线段树合并）

时间：2024-12-25 19:43:36浏览次数：4  
标签：mmax 封装 tem STL 线段 dsu son int void

Preface

起因是这个万恶的\(P9067\)，一个数据结构题，当时才搞了01字典树的板子，想\(trytry\)合并的题的，然后就搜到了这道。（虽然最后完全和这个没有关系）。

然后感觉用线段树合并做就可以了，于是抄了个之前封装的一个板子，但是一点都不好用（sad）。空间方面又是头疼，感觉封装了又好像没有封装，对比一下用\(map\)写的\(AC\)代码，感觉差的不是一点，而且本人实在是热衷搞板子，于是打算搞一个封装好的动态开点的线段树，可以像\(STL\)那样使用非常灵便。

code

先上代码：


//使用之前要先使用clear函数
namespace SegTree {

	constexpr int MAXN = (N * 40);

	struct info {
		int mmax = 0;
		int cnt = 0;

		void apply(int pos,int k) {
			mmax += k;
			cnt = pos;
		}

		void merge(info &q1) {
			mmax += q1.mmax;
		}

		void clear() {

		}

		friend info operator+(const info &q1, const info &q2) {
			info q;
			q.cnt = 0;
			if (q1.mmax == q2.mmax) {
				q.mmax = q1.mmax;
				q.cnt = min(q1.cnt, q2.cnt);
			}
			else {
				q.mmax = max(q1.mmax, q2.mmax);
				if (q.mmax == q1.mmax) q.cnt = q1.cnt;
				if (q.mmax == q2.mmax) q.cnt = q2.cnt;
			}
			return q;
		}


	} F[MAXN];

	bool lf[MAXN];
	int son[MAXN][2];
	stack<int> st;
	int tot;


	void clear() {
		tot = 0;
		lf[0] = 0;
		while (!st.empty()) st.pop();
	}

	int newNode() {
		int tem;
		if (!st.empty()) {
			tem = st.top();
			st.pop();
		}
		else
			tem = ++tot;
		F[tem] = info(), lf[tem] = 1, lf[son[tem][0]] = lf[son[tem][1]] = 0;
		son[tem][0] = son[tem][1] = 0;
		return tem;
	}

	void del(int x) { lf[x] = 0, F[x].clear(), st.push(x); }

	class Seg {
#define xl son[x][0]
#define xr son[x][1]
		int L, R;
		int rt = 1;

		void add(int &x, int l, int r, int l1, int r1, int k) {
			if (l1 > r1) return;
			if (!lf[x]) x = newNode();
			if (l1 <= l and r <= r1) {
				F[x].apply(l1, k);
				return;
			}
			int mid = l + r >> 1;
			if (r1 <= mid) add(xl, l, mid, l1, r1, k);
			else if (mid < l1) add(xr, mid + 1, r, l1, r1, k);
			else add(xl, l, mid, l1, mid, k), add(xr, mid + 1, r, mid + 1, r1, k);
			F[x] = F[xl] + F[xr];
		}

		info qry(int x, int l, int r, int l1, int r1) {
			if (l1 > r1 or !lf[x]) return info();
			if (l1 <= l and r <= r1) return F[x];
			int mid = l + r >> 1;
			if (r1 <= mid) return qry(xl, l, mid, l1, r1);
			else if (mid < l1) return qry(xr, mid + 1, r, l1, r1);
			else { return qry(xl, l, mid, l1, mid) + qry(xr, mid + 1, r, mid + 1, r1); }
		}

		int merge(int x,int y,int l,int r) {
			if (!x or !y) return x + y;
			if (l == r) {
				F[x].merge(F[y]);
				del(y);
				return x;
			}
			int mid = l + r >> 1;
			son[x][0] = merge(son[x][0], son[y][0], l, mid);
			son[x][1] = merge(son[x][1], son[y][1], mid + 1, r);
			F[x] = F[xl] + F[xr];
			del(y);
			return x;
		}

#undef xl
#undef xr

	public:
		void clear(int l, int r) {
			L = l, R = r;
			rt = newNode();
		}

		void add(int pos, int k) { add(rt, L, R, pos, pos, k); }
		info qry(int l, int r) { return qry(rt, L, R, l, r); }
		void merge(Seg &y) { rt = merge(rt, y.rt, L, R); }
	};

}

细节部分：

\(info\) （节点）结构体：

有一个大的命名空间包着，其中我们在使用的时候根据每个题的变动，修改的地方就是\(namespace\)里的\(info\)。

里面有\(apply、clear、merge、up\)函数，以下是注释：

\(apply\)：用来实现单点添加。

\(clear\)：例如此题中链表需要\(clear\)掉，不然会占空间，所以用来\(clear\)一些节点维护的数据结构。（一般也可以不\(clear\)，直接空着放那就好了）

\(merge\)：用来完善线段树合并中节点合并时具体合并哪些信息，也是我们经常需要修改的地方。

\(up\)：是一个重载运算符，如字面意思就是一个实现合并操作的。

SegTree里的变量：

\(lf\)数组代表当前这个点是否存活，\(1\)代表或者，\(0\)代表不在。

\(st\)是一个栈，用来实现线段树合并里的垃圾回收操作（这一步也可以不用，如果节点过多数组开不下，就可以用这个，否则也可以不用）

\(tot\)：用来存节点总数的，和\(st\)一起实现\(newNode\)函数。

\(son\)数组：字面意思，存当前节点的左右儿子的编号

SegTree里的函数：

\(clear\)函数：用来清空的，面对多组数据使用，以及使用这个封装的线段树之前要\(clear\)下。

\(newNode\)：用来建立一个新的节点

\(del\)：用来将当前节点删除（做垃圾回收的）

Seg class：

这个就是线段树，其中每一个线段树都有一个自己的根（编号，也是里面的变量\(rt\)），自己所维护的范围（ \(L\)~\(R\)区间 ）。

然后里面有三个操作，添加，求和，合并。这里就不细说内容，学过线段树合并的就大概都知道了。

使用注意事项：

其中主要需要修改的就是\(info\)，其他的都当做黑盒来处理就可以。

使用方面各位可以参考一下，\(STL\)中别的容器平常是怎么使用的，就怎么使用这个。

但是不同的地方就是声明变量后都一定要\(clear\)，线段树的\(clear\)函数有两个参数\(（l，r）\)，用来设定当前线段树的维护的区间。

以及在使用这个封装的之前要先使用空间里的\(clear\)函数。

直接声明\(SegTree::Seg \ \ tem\)，那么\(tem\)就是一个线段树，调用函数就是\(tem.add(pos,val)\)，就是在这个线段树的\(pos\)位置加上\(val\)，其他的函数也都是。如果要合并两颗线段树等操作就看如下代码：

signed main() {
	fileRead();
	kuaidu();
	T = 1;
	//cin >> T;
	while (T--) {
		SegTree::clear();
		SegTree::Seg seg[3];
		rep(i, 0, 2) seg[i].clear(1, 10000);
		seg[1].add(12, 1);
		seg[1].qry(12, 142);
		seg[1].merge(seg[2]);

	}
	return 0;
}

雨天的尾巴（线段树合并板子）

下面是具体的使用：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <stack>
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rep2(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;

template<typename T>
void cc(const vector<T> &tem) {
	for (const auto &x: tem) cout << x << ' ';
	cout << endl;
}

template<typename T>
void cc(const T &a) { cout << a << endl; }

template<typename T1, typename T2>
void cc(const T1 &a, const T2 &b) { cout << a << ' ' << b << endl; }

template<typename T1, typename T2, typename T3>
void cc(const T1 &a, const T2 &b, const T3 &c) { cout << a << ' ' << b << ' ' << c << endl; }

void fileRead() {
#ifdef LOCALL
	freopen("D:\\AADVISE\\Clioncode\\untitled2\\in.txt", "r", stdin);
	freopen("D:\\AADVISE\\Clioncode\\untitled2\\out.txt", "w", stdout);
#endif
}

void kuaidu() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }

inline int max(int a, int b) {
	if (a < b) return b;
	return a;
}

inline double max(double a, double b) {
	if (a < b) return b;
	return a;
}

inline int min(int a, int b) {
	if (a < b) return a;
	return b;
}

inline double min(double a, double b) {
	if (a < b) return a;
	return b;
}

void cmax(int &a, const int &b) { if (b > a) a = b; }
void cmin(int &a, const int &b) { if (b < a) a = b; }
void cmin(double &a, const double &b) { if (b < a) a = b; }
void cmax(double &a, const double &b) { if (b > a) a = b; }

template<typename T>
using vec = vector<T>;
using PII = pair<int, int>;
using i128 = __int128;


//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
int ans[N];
int dep[N];
int fu[N][33];
bool book[N];
vector<int> A[N];
//--------------------------------------------------------------------------------
//struct or namespace:

//使用之前要先使用clear函数
namespace SegTree {

	constexpr int MAXN = (N * 60);

	struct info {
		int mmax = 0;
		int cnt = 0;

		void apply(int pos,int k) {
			mmax += k;
			cnt = pos;
		}

		void merge(info &q1) {
			mmax += q1.mmax;
		}

		void clear() {

		}

		friend info operator+(const info &q1, const info &q2) {
			info q;
			q.cnt = 0;
			if (q1.mmax == q2.mmax) {
				q.mmax = q1.mmax;
				q.cnt = min(q1.cnt, q2.cnt);
			}
			else {
				q.mmax = max(q1.mmax, q2.mmax);
				if (q.mmax == q1.mmax) q.cnt = q1.cnt;
				if (q.mmax == q2.mmax) q.cnt = q2.cnt;
			}
			return q;
		}


	} F[MAXN];

	bool lf[MAXN];
	int son[MAXN][2];
	stack<int> st;
	int tot;


	void clear() {
		tot = 0;
		lf[0] = 0;
		while (!st.empty()) st.pop();
	}

	int newNode() {
		int tem;
		if (!st.empty()) {
			tem = st.top();
			st.pop();
		}
		else
			tem = ++tot;
		F[tem] = info(), lf[tem] = 1, lf[son[tem][0]] = lf[son[tem][1]] = 0;
		son[tem][0] = son[tem][1] = 0;
		return tem;
	}

	void del(int x) { lf[x] = 0, F[x].clear(), st.push(x); }

	class Seg {
#define xl son[x][0]
#define xr son[x][1]
		int L, R;
		int rt = 1;

		void up(int x) {
			if (lf[xl] and lf[xr]) F[x] = F[xl] + F[xr];
			else if (lf[xl]) F[x] = F[xl];
			else if (lf[xr]) F[x] = F[xr];
		}

		void add(int &x, int l, int r, int l1, int r1, int k) {
			if (l1 > r1) return;
			if (!lf[x]) x = newNode();
			if (l1 <= l and r <= r1) {
				F[x].apply(l1, k);
				return;
			}
			int mid = l + r >> 1;
			if (r1 <= mid) add(xl, l, mid, l1, r1, k);
			else if (mid < l1) add(xr, mid + 1, r, l1, r1, k);
			else add(xl, l, mid, l1, mid, k), add(xr, mid + 1, r, mid + 1, r1, k);
			// up(x);
			F[x] = F[xl] + F[xr];
		}

		info qry(int x, int l, int r, int l1, int r1) {
			if (l1 > r1 or !lf[x]) return info();
			if (l1 <= l and r <= r1) return F[x];
			int mid = l + r >> 1;
			if (r1 <= mid) return qry(xl, l, mid, l1, r1);
			else if (mid < l1) return qry(xr, mid + 1, r, l1, r1);
			else { return qry(xl, l, mid, l1, mid) + qry(xr, mid + 1, r, mid + 1, r1); }
		}

		int merge(int x,int y,int l,int r) {
			if (!x or !y) return x + y;
			if (l == r) {
				F[x].merge(F[y]);
				del(y);
				return x;
			}
			int mid = l + r >> 1;
			son[x][0] = merge(son[x][0], son[y][0], l, mid);
			son[x][1] = merge(son[x][1], son[y][1], mid + 1, r);
			// up(x);
			F[x] = F[xl] + F[xr];
			del(y);
			return x;
		}

#undef xl
#undef xr

	public:
		void clear(int l, int r) {
			L = l, R = r;
			rt = newNode();
		}

		void add(int pos, int k) { add(rt, L, R, pos, pos, k); }
		info qry(int l, int r) { return qry(rt, L, R, l, r); }
		void merge(Seg &y) { rt = merge(rt, y.rt, L, R); }
	};

}

class DSU {
	struct Info {
		int fa;
		int siz;
		SegTree::Seg seg;
	} dsu[N];

public:
	Info &operator()(const int &x) { return dsu[find(x)]; }
	Info &operator[](const int &x) { return dsu[x]; }

	void clear(int n) {
		//TODO 初始化
		rep(i, 0, n) {
			dsu[i].fa = i, dsu[i].siz = 1;
			dsu[i].seg.clear(1, 100000);
		}
	}

	void merge(int x, int y) {
		x = find(x), y = find(y);
		if (x == y) return;
		dsu[y].fa = dsu[x].fa;
		if (dsu[x].siz < dsu[y].siz) swap(dsu[x], dsu[y]);
		dsu[y].fa = dsu[x].fa, dsu[x].siz += dsu[y].siz;
		dsu[x].seg.merge(dsu[y].seg);
		//TODO 合并操作

	}

	int find(int x) { return x == dsu[x].fa ? x : dsu[x].fa = find(dsu[x].fa); }
	bool same(int x, int y) { return (find(x) == find(y)); }
} dsu;

//--------------------------------------------------------------------------------


void dfs(int now, int father) {
	dep[now] = dep[father] + 1;
	fu[now][0] = father;
	for (int i = 1; i <= 20; i++) fu[now][i] = fu[fu[now][i - 1]][i - 1];
	for (auto y: A[now]) {
		if (y == father) continue;
		dfs(y, now);
	}
}

int LCA(int x, int y) {
	if (dep[x] < dep[y]) std::swap(x, y);
	for (int i = 20; i >= 0; --i)
		if (dep[fu[x][i]] >= dep[y]) x = fu[x][i];
	if (x == y) return x;
	for (int i = 20; i >= 0; --i)
		if (fu[x][i] != fu[y][i]) x = fu[x][i], y = fu[y][i];
	return fu[x][0];
}

void dfs2(int x, int pa) {
	for (auto y: A[x]) {
		if (y == pa) continue;
		dfs2(y, x);
		dsu.merge(x, y);
	}
	SegTree::info tem = dsu(x).seg.qry(1, 100000);
	if (tem.mmax == 0) ans[x] = 0;
	else ans[x] = tem.cnt;
}

signed main() {
#ifdef LOCALL
	freopen("D:\\AADVISE\\Clioncode\\untitled2\\in.txt", "r", stdin);
	freopen("D:\\AADVISE\\Clioncode\\untitled2\\out.txt", "w", stdout);
#endif
	kuaidu();
	int dd;

	cin >> dd >> m;
	const int n = dd;


	// cout << n << endl;
	rep(i, 1, n - 1) {
		int a, b;
		cin >> a >> b;
		A[a].push_back(b);
		A[b].push_back(a);
	}

	SegTree::clear();
	dsu.clear(n);

	dfs(1, 0);
	rep(i, 1, m) {
		int a, b, c;
		cin >> a >> b >> c;
		int t = LCA(a, b);
		dsu(a).seg.add(c, 1);
		dsu(b).seg.add(c, 1);
		if (fu[t][0])dsu(fu[t][0]).seg.add(c, -1);
		if (t)dsu(t).seg.add(c, -1);

	}

	dfs2(1, 0);

	rep(i, 1, n) {
		cout << ans[i] << endl;
	}
	return 0;
}


/*


*/

PostScript

板子也许会有问题，如果有请指出来。

标签：mmax,封装,tem,STL,线段,dsu,son,int,void
From： https://www.cnblogs.com/advisedy/p/18631294

相关文章

  • 线段树1模板 （洛谷p3372）
    关键在于创建一个向上返回的函数up，向下查询的同时将父亲sum和add值传给儿子函数down最后用lazy函数更新sum和add的值先通过build函数是sum数组完成初始化，然后用adds已经quiey函数完成求解，详细注释见代码​#include<iostream>#include<cstdio>usingnamespacestd;intm......
  • jstl一些标签 中timestamp类型在页面去掉时分秒！
    jstl一些标签中timestamp类型在页面去掉时分秒！|Id|Title|DateAdded|SourceUrl|PostType|Body|BlogId|Description|DateUpdated|IsMarkdown|EntryName|CreatedTime|IsActive|AutoDesc|AccessPermission||-------------|-------------|--------......
  • 简单记录下底部固定的样式并简单封装
    需求：需要在底部做个固定样式，添加备案等信息实现思路：1.定义文本，数组对象记录，循环遍历，有利于维护2.定义样式，固定定位+层级置顶3.抽离成组件复用js<scriptlang="ts"setup>constbottomInfoList=[{label:'关于我们',link:'user/aboutUs'},{label:'帮......
  • 经典区间线段树详解：从原理到实践
    线段树（SegmentTree）是一种非常高效的树形数据结构，用于解决区间查询和修改问题。本文将通过分步骤讲解，带领读者熟练掌握线段树的原理与实现，并探索其应用场景。引言：数组区间修改问题在一些经典问题中，比如给定一个数组，频繁地需要进行以下操作：区间查询：查询数组某一子区间内的最大......
  • 封装（3）
    大家好，今天我们来学习一下静态方法相关的内容，这个要和普通成员做一个区分，那么它们到底有什么不同点呢，我们现在就来看看。7.2static修饰成员变量1、访问方式,通过类名静态变量不在对象里面,在方法区,要通过类名.访问.  static修饰的成员变量,称为静态成员变量,静态成负......
  • 封装（2）
    大家好，今天我们来介绍一下包的概念，知道包的作用可以更好的面对今后的开发，那么我们就来看看包是什么东西吧。6.3封装扩展之包6.3.1包的概念在面向对象体系中,提出了一个软件包的概念,即:为了更好的管理类,把多个类收集在一起成为一组,称为软件包,有点类似于目录,比如:为了更......
  • JAVA面向对象（二）封装
    数据的守护者封装是面向对象编程的重要特性之一，它将数据和操作数据的方法紧密地结合在一起，并对外部隐藏了数据的具体实现细节。这样做的好处是多方面的。一方面，它保护了数据的完整性。例如，在Person类中，如果我们直接将age成员变量暴露给外部，那么可能会出现不合理的赋值情况，比如设......
  • mybatis完成联表查询结果的封装。
    1.mybatis完成联表查询结果的封装。表与表之间通过外键会建立关联关系。我们也可以通过联表查询得到多张表的数据。我们java中如何通过实体类建立这种关系呢?例如:班级表1-----n学生表(外键列)。查询学生信息时要求携带班级信息。一定使用了联表查询的sql语句.select*fro......
  • blog-结构与封装热应力仿真
    仿真场景结构放入某种温度环境较长时间：（1）管壳封装；（2）结构应力分布；（3）MEMS锚区比研究；仿真方法对于结构内外温度达到一致且该温度已知的情况，进行热应力分析时不需要引入传热接口。在固体力学中加入热膨胀子节点分析节后相对于参考温度的热应变。仿真原理热应力=杨氏模量*热膨胀系数*温度......
  • vue 登录时的验证码的封装
    <template><divclass="s-canvas"><canvasid="s-canvas":width="contentWidth":height="contentHeight":style={height:codeheight}></canvas></div></template><script>......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99