首页 > 其他分享 >模板集合（持续更新中）

模板集合（持续更新中）

时间：2023-05-04 20:24:36浏览次数：29  
标签：q1 return val int top 更新 集合 const 模板

线段树

// 线段树
namespace Seg_tree {
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
	
	typedef long long ll;
	const int N = 1e5 + 5;
	using std::max;
	using std::min;
	
	ll val[N << 2], laz[N << 2], maxx[N << 2], minn[N << 2];
	
	template<class T>
	const T& _max(const T& a, const T& b) { // 比较函数
		return a > b ? a : b;
	}
	
	template<class T>
	const T& _min(const T& a, const T& b) { // 比较函数
		return a > b ? b : a;
	}
	
	void pushup(int u) { // 更新信息
		val[u] = val[ls] + val[rs];
		maxx[u] = max(maxx[ls], maxx[rs]);
		minn[u] = min(minn[ls], minn[rs]);
	}
	
	void pushdown(int u, int l, int r) { // 下传标记
		if (!laz[u])	return ;
		laz[ls] += laz[u];
		val[ls] += laz[u] * (mid - l + 1);
		maxx[ls] += laz[u] * (mid - l + 1);
		minn[ls] += laz[u] * (mid - l + 1);
		laz[rs] += laz[u];
		val[rs] += laz[u] * (r - mid);
		maxx[rs] += laz[u] * (r - mid);
		minn[rs] += laz[u] * (r - mid);
		laz[u] = 0;
	}
	
	void build(int u, int l, int r) { // 建树
		laz[u] = 0;
		if (l == r) {
			scanf("%lld", &val[u]);
			maxx[u] = minn[u] = val[u];
			return ;
		}
		build(ls, l, mid);
		build(rs, mid + 1, r);
		pushup(u);
	}
	
	void add(int u, int l, int r, int lr, int rr, ll c) { // 区间加减
		if (lr <= l && r <= rr) {
			laz[u] += c;
			ll tmp = (r - l + 1) * c;
			val[u] += tmp;
			minn[u] += tmp;
			maxx[u] += tmp;
			return ;
		}
		pushdown(u, l, r);
		if (lr <= mid)	add(ls, l, mid, lr, rr, c);
		if (rr > mid)	add(rs, mid + 1, r, lr, rr, c);
		pushup(u);
	}
	
	ll qry(int u, int l, int r, int lr, int rr, ll* g) { // 区间查询,g 为查询的数组名
		if (lr <= l && r <= rr) {
			return g[u];
		}
		pushdown(u, l, r);
		ll ans = 0;
		if (lr <= mid) {
			ans += qry(ls, l, mid, lr, rr, g);
		}
		if (rr > mid) {
			ans += qry(rs, mid + 1, r, lr, rr, g);
		}
		return ans;
	}
}

ST 表

namespace ST_RMQ {
#define MAX 1
#define MIN 0
	
	typedef long long ll;
	const int N = 1e5 + 5;
	using std::max;
	using std::min;
	
	int lg[N];
	ll maxx[N][20], minn[N][20];
	
	template<class T>
	const T& _max(const T& a, const T& b) {
		return a > b ? a : b;
	}
	
	template<class T>
	const T& _min(const T& a, const T& b) {
		return a > b ? b : a;
	}
	
	void pre(int n) { // 预处理 lg
		for (int i = 2; i <= n; ++ i) {
			lg[i] = lg[i >> 1] + 1;
		}
	}
	
	void work(int n) {
		for (int j = 1; j <= lg[n]; ++ j) {
			for (int i = 1; i + (1 << j) - 1 <= n; ++ i) {
				maxx[i][j] = max(maxx[i][j - 1], maxx[i + (1 << j - 1)][j - 1]);
				minn[i][j] = min(minn[i][j - 1], minn[i + (1 << j - 1)][j - 1]);
			}
		}
	}
	
	ll qry(int l, int r, int fg) { // 求最值,fg 为 1 时求最大值,fg 为 2 时求最小值
		int k = lg[r - l + 1];
		if (fg == MAX)	return max(maxx[l][k], maxx[r - (1 << k) + 1][k]);
		if (fg == MIN)	return min(minn[l][k], minn[r - (1 << k) + 1][k]);
		return -1;
	}
}

堆

// 堆
namespace Heap {
	typedef long long ll;
	using std::priority_queue;
	using std::vector;
	using std::queue;
	using std::greater;
	using std::swap;
	const int N = 1e5 + 5;
	
	// 对顶堆
	struct top_heap {
		priority_queue<ll> q1;
		priority_queue<ll, vector<ll>, greater<ll> > q2;
		
		void insert(ll x) { // 插入
			if (q1.empty()) {
				q1.push(x);
				return ;
			}
			if(x > q1.top())	q2.push(x);
			else	q1.push(x);
		}
		
		int K_th(int k) { // 求第 K 大的值
			if (q1.size() + q2.size() < k)	return -1;
			while (q1.size() < k) {
				q1.push(q2.top());
				q2.pop();
			}
			while (q1.size() > k) {
				q2.push(q1.top());
				q1.pop();
			}
			return q1.top();
		}
		
		int pop_K_th(int k) { // 删除第 K 大的值
			if (q1.size() + q2.size() < k)	return -1;
			while (q1.size() < k) {
				q1.push(q2.top());
				q2.pop();
			}
			while (q1.size() > k) {
				q2.push(q1.top());
				q1.pop();
			}
			int u = q1.top();
			q1.pop();
			return u;
		}
	};

	// 可删除堆
	struct del_heap {
		priority_queue<ll, vector<ll>, greater<ll> > q1, q2;
		
		void insert(ll x) { // 插入
			q1.push(x);
		}
		
		void del(ll x) { // 删除
			q2.push(x);
		}
		
		ll top() { // 取堆顶
			while(!q2.empty() && !q1.empty() && q2.top() == q1.top()) {
				q1.pop(), q2.pop();
			}
			return q1.top();
		}
	};

	// 左偏树（小根堆）
	struct leftist_tree {
		int lson[N], rson[N], fa[N], fat[N];
		ll val[N], dist[N];
		
		int merge(int x, int y) { // 合并
			if (!x || !y) {
				return x | y;
			}
			if (val[x] > val[y] || (val[x] == val[y] && x > y))
				swap(x, y);
			rson[x] = merge(rson[x], y);
			fat[rson[x]] = fa[rson[x]] = x;
			if (dist[lson[x]] < dist[rson[x]])
				swap(lson[x], rson[x]);
			dist[x] = dist[rson[x]] + 1;
			return x;
		}
		
		int find(int u) { // 查询堆顶的元素的标号
			return (fat[u] == u || fat[u] == 0) ? u : fat[u] = find(fat[u]);
		}
		
		void earse(int u) { // 删除任意一点
			int tmp = merge(lson[u], rson[u]), fu = fa[u];
			fat[tmp] = fa[tmp] = fu;
			fat[u] = fa[u] = tmp;
			lson[fu] == u ? lson[fu] = tmp : rson[fu] = tmp;
			while (fu) {
				if (dist[lson[fu]] < dist[rson[fu]])
					swap(lson[fu], rson[fu]);
				if (dist[fu] == dist[rson[fu]] + 1)
					return ;
				dist[fu] = dist[rson[fu]] + 1;
				fu = fa[fu];
			}
		}
		
		ll top(int u) { // 查询 u 点所在堆的堆顶元素
			int g = find(u);
			return val[g];
		}
		
		void pop(int u) { // 弹出 u 点所在对的堆顶元素
			int g = find(u);
			earse(g);
		}
		
		int build(int n) { // 建树
			queue<int> q;
			for (int i = 1; i <= n; ++ i) {
				q.push(i);
			}
			int x, y, z;
			while (q.size() > 1) {
				x = q.front(), q.pop();
				y = q.front(), q.pop();
				z = merge(x, y), q.push(z);
			}
			return q.front();
		}
	};
}

平衡树（FHQ）

// 平衡树(FHQ)
namespace Balance_tree {
#define lc ch[u][0]
#define rc ch[u][1]
	
	const int N = 1e5 + 5;
	
	struct FHQ {
		int cnt, rt, top;
		int ch[N][2], siz[N], val[N], pai[N], rub[N];
		
		void pushup(int u) {
			siz[u] = siz[lc] + siz[rc] + 1;
			return ;
		}
		
		int New(int c) {
			int u;
			if (!top) {
				u = ++ cnt;
			}
			else {
				u = rub[top];
				top --;
			}
			val[u] = c;
			siz[u] = 1;
			pai[u] = rand();
			lc = 0, rc = 0;
			return u;
		}
		
		void split1(int u, int c, int &x, int &y) { // 按照权值分裂
			if (u == 0) {
				x = y = 0;
				return ;
			}
			if (val[u] <= c) {
				x = u;
				split1(rc, c, rc, y);
			}
			else {
				y = u;
				split1(lc, c, x, lc);
			}
			pushup(u);
		}
		
		void split2(int u, int k, int &x, int &y) { // 按照子树大小分裂
			if (u == 0) {
				x = y = 0;
				return ;
			}
			pushup(u);
			if (siz[lc] + 1 <= k) {
				x = u;
				split2(rc, k - siz[lc] - 1, rc, y);
			}
			else {
				y = u;
				split2(lc, k, x, lc);
			}
			pushup(u);
		}
		
		int merge(int x, int y) {
			if (!x || !y) {
				return x + y;
			}
			if (pai[x] < pai[y]) {
				ch[x][1] = merge(ch[x][1], y);
				pushup(x);
				return x;
			}
			else {
				ch[y][0] = merge(x, ch[y][0]);
				pushup(y);
				return y;
			}
		}
		
		void insert(int c) {
			int t1, t2;
			split1(rt, c, t1, t2);
			rt = merge(merge(t1, New(c)), t2);
		}
		
		void del(int c) {
			int t1, t2, t3;
			split1(rt, c, t1, t2);
			split1(t1, c - 1, t1, t3);
			rub[++ top] = t3;
			t3 = merge(ch[t3][0], ch[t3][1]);
			rt = merge(merge(t1, t3), t2);
		}
		
		int ranking(int c) {
			int t1, t2, k;
			split1(rt, c - 1, t1, t2);
			k = siz[t1] + 1;
			rt = merge(t1, t2);
			return k;
		}
		
		int K_th(int k) {
			int t1, t2, t3, c;
			split2(rt, k, t1, t2);
			split2(t1, k - 1, t1, t3);
			c = val[t3];
			rt = merge(merge(t1, t3), t2);
			return c;
		}
		
		int pre(int c) {
			int t1, t2, t3, k;
			split1(rt, c - 1, t1, t2);
			split2(t1, siz[t1] - 1, t1, t3);
			k = val[t3];
			rt = merge(merge(t1, t3), t2);
			return k;
		}
		
		int nxt(int c) {
			int t1, t2, t3, k;
			split1(rt, c, t1, t2);
			split2(t2, 1, t2, t3);
			k = val[t2];
			rt = merge(t1, merge(t2, t3));
			return k;
		}
	};
}

可持久化数据结构

namespace Persistent { // 可持久化数据结构
#define mid ((l + r) >> 1)
	
	const int N = 1e6 + 5;
	const int M = (N << 5) + 10;
	
	struct persistent_arr { // 可持久化数组
		
		int rot;
		
		struct node {
			int ls, rs, val;
		} nod[(N << 5) + 10];
		
		inline int newnod(int u) { // 创建新节点
			++ rot;
			nod[rot] = nod[u];
			return rot;
		}
		
		int build(int l, int r) { // 建树
			int u = ++ rot;
			if (l == r) {
				scanf("%d", &nod[u].val);
				return u;
			}
			nod[u].ls = build(l, mid);
			nod[u].rs = build(mid + 1, r);
			return u;
		}
		
		int modify(int u, int l, int r, int pos, int c) { // 修改
			u = newnod(u);
			if (l == r) {
				nod[u].val = c;
			}
			else {
				if (pos <= mid) {
					nod[u].ls = modify(nod[u].ls, l, mid, pos, c);
				}
				else {
					nod[u].rs = modify(nod[u].rs, mid + 1, r, pos, c);
				}
			}
			return u;
		}
		
		int query(int u, int l, int r, int pos) { // 查询
			if (l == r) {
				return nod[u].val;
			}
			else {
				if (pos <= mid) {
					return query(nod[u].ls, l, mid, pos);
				}
				else {
					return query(nod[u].rs, mid + 1, r, pos);
				}
			}
		}
	};
	
	struct persistent_seg {
		int rot;
		
		struct node {
			int l, r, val;
		} nod[M];
		
		inline int newnod(int u) { // 创建新节点
			++ rot;
			nod[rot] = nod[u];
			nod[rot].val = nod[u].val + 1;
			return rot;
		}
		
		int build(int l, int r) { // 建树
			int u = ++ rot;
			if (l == r) {
				return u;
			}
			nod[u].l = build(l, mid);
			nod[u].r = build(mid + 1, r);
			return u;
		}
		
		int add(int u, int l, int r, int pos) { // 插入新节点
			u = newnod(u);
			if (l == r)	return u;
			if (pos <= mid) {
				nod[u].l = add(nod[u].l, l, mid, pos);
			}
			else {
				nod[u].r = add(nod[u].r, mid + 1, r, pos);
			}
			return u;
		}
		
		int query(int l, int r, int lr, int rr, int k) { // 查找第 k 大的值
			int x = nod[nod[rr].l].val - nod[nod[lr].l].val;
			if (l == r)	return l;
			if (k <= x) {
				return query(l, mid, nod[lr].l, nod[rr].l, k);
			}
			else {
				return query(mid + 1, r, nod[lr].r, nod[rr].r, k - x);
			}
		}
	};
}

标签：q1,return,val,int,top,更新,集合,const,模板
From： https://www.cnblogs.com/yifan0305/p/17344817.html

相关文章

  • springboot 分析源码欢迎页和图标-> thymeleaf模板引擎常用语法->扩展
    欢迎页： icon： 注意点： thymeleaf模板引擎1.使用thymeleaf模板引擎前要导入对应依赖包2.阅读源码：根据源码说明我们可以将html文件放置在templates目录下，然后通过controller进行跳转即可 controller类：//在templates下的东西需要通过controller类来跳转，//需要导入......
  • 模板库
    火车头:#pragmaGCCoptimize(3)#pragmaGCCtarget("avx")#pragmaGCCoptimize("Ofast")#pragmaGCCoptimize("inline")#pragmaGCCoptimize("-fgcse")#pragmaGCCoptimize("-fgcse-lm")#pragmaGCCoptimize(&qu......
  • 16 春节快乐｜一篇暂停更新的说明
    你好呀，我是辰洋，《郭东白的架构课》的负责人。我又来啦！不过这一次，我不是带着加餐来的，而是带着一套“减餐”。是的，专栏将在春节期间暂停更新。临近春节，各种不可控因素打乱了东白老师的写作计划，相应地也打乱了我们的备稿节奏，这让我们暂时无法保证春节期间每周两篇的更新。打磨一篇......
  • TypeScript 学习笔记 — 模板字符串和类型体操（十五）
    目录基本介绍字符串类型体操实操环节1.字符串首字母大写CapitalizeString2.获取字符串第一个字符FirstChar3.获取字符串最后一个字符LastChar4.字符串转元组StringToTuple5.元组转字符串TupleToString6.重复字符串RepeatString7.字符串分割SplitString8.获取字符串......
  • node.js版本更新及遇到的错
    下载你要更新的版本双击运行一直next然后如果你之前安装过node.js不用管它会覆盖安装安装好之后cmd检查版本号node -v出来版本号那就没有问题但是在启动的时候会报node不是不是内部或外部命令，也不是可运行的程序或批处理文件这个时候呢上百度说是环境的问题但......
  • 分页查询处理上百万数据 更新
    $count=Route::find()->where(['ro_visible'=>1])->count();//统计数据表数量$limit=100;$pagecount=ceil($count/$limit);//计算数据表的页数//事务执行$tr=Yii::$app->db->beginTransaction();try{for($page=1;$page<=$pagecount;$page++)......
  • 【Call for papers】2023年CCF人工智能会议信息汇总（持续更新）
    本博文是根据2022年CCF会议推荐的人工智能领域相关会议目录撰写。一、截稿时间总览截稿时间的总时间轴内容将会持续更新......往年投稿及录用情况及链接详见图片后面的内容。二、会议详细目录由于一些会议的投稿时间还没公开，因此根据往年投稿时间在表格中使用 ~符号表示大概的投......
  • 关于租房（持续更新...)
    确定租房地点和预算在租房之前，我需要先了解所在城市的租房市场行情，比较不同地区的房价和租金水平，同时也得根据自己的经济状况和生活需求制定一个较为合理的预算。地段：提前看好交通方式和路线，沿着上班路线找，离工作近为主，工作稳定后再换又近又好的搜寻房源信息通过租房A......
  • jdbc更新|5-2
    数据库操作总结起来就四个字：增删改查，行话叫CRUD：Create，Retrieve，Update和Delete。查就是查询，我们已经讲过了，就是使用PreparedStatement进行各种SELECT，然后处理结果集。现在我们来看看如何使用JDBC进行增删改。插入插入操作是INSERT，即插入一条新记录。通过JDBC进行插入，本质上也是用Pre......
  • 1159 Structure of a Binary Tree + 根据前序和中序构建二叉树+ 层序遍历模板复习
    题目链接：https://pintia.cn/problem-sets/994805342720868352/exam/problems/1478635126488367104唉，今天的bug出在了下面这条语句。if(tree[root_key].left*tree[root_key].right<0)full_tree=false;我写成了full_tree=!(tree[root_key].left*tree[root_key].rig......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99