换新马蜂了，望周知

cjdst

2026-02-06 23:48:55

发布于：广东

236阅读

0回复

0点赞

#include <bits/stdc++.h>
namespace cjdst{
	typedef long long ll;
	typedef unsigned long long ull;
	typedef std::pair <int, int> pii;
	typedef std::pair <ll, ll> pll;

	template <typename T>
	class Sparse_Table{
		std::vector <std::vector <T>> st;
		int n;

		public:

		Sparse_Table(int n, std::vector <T> a){
			this -> n = n;
			st.resize(a.size() + 5, std::vector <T>(std::__lg(n) + 5));
			for(int i = 1; i <= n; i++){
				st[i][0] = a[i];
			}
			for(int i = 1; i <= std::__lg(n); i++){
				for(int j = 1; j <= n; j++){
					if(j + (1 << i) - 1 > n) break;
					st[j][i] = std::max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
				}
			}
		}

		T query(int l, int r){
			int idx = std::__lg(r - l + 1);
			return std::max(st[l][idx], st[r - (1 << idx) + 1][idx]);
		}
	};

	template <typename T>
	class Fenwick_Tree{
		std::vector <T> tr;
		int n;

		public:

		Fenwick_Tree(){}
		Fenwick_Tree(int n, std::vector <T> a){
			tr.resize(n + 5, 0);
			this -> n = n;
			for(int i = 1; i <= n; i++){
				tr[i] += a[i];
				if(i + (i & (-i)) <= n){
					tr[i + (i & (-i))] += tr[i];
				}
			}
		}
		void modify(int idx, T val){
			for(int i = idx; i <= n; i += (i & (-i))) tr[i] += val;
		}
		T query(int idx){
			T ans = 0;
			for(int i = idx; i; i -= (i & (-i))) ans += tr[i];
			return ans;
		}
	};

	template <typename T>
	class Segtree{
		std::vector <T> tr;
		std::vector <int> left, right;
		std::vector <T> lazytag;
		void push_up(int u){
			tr[u] = tr[u << 1] + tr[u << 1 | 1];
		}
		void push_down(int u){
			tr[u << 1] += (right[u << 1] - left[u << 1] + 1) * lazytag[u];
			tr[u << 1 | 1] += (right[u << 1 | 1] - left[u << 1 | 1] + 1) * lazytag[u];
			lazytag[u << 1] += lazytag[u];
			lazytag[u << 1 | 1] += lazytag[u];
			lazytag[u] = 0;
		}
		void build(int u, int l, int r, std::vector <T> &a){
			left[u] = l, right[u] = r;
			if(l == r){
				tr[u] = a[l];
				return;
			}
			int mid = (l + r) >> 1;
			build(u << 1, l, mid, a);
			build(u << 1 | 1, mid + 1, r, a);
			push_up(u);
		}
		void _modify(int u, int l, int r, T val){
			if(left[u] >= l && right[u] <= r){
				tr[u] += (right[u] - left[u] + 1) * val;
				lazytag[u] += val;
				return;
			}
			push_down(u);
			if(right[u << 1] >= l) _modify(u << 1, l, r, val);
			if(left[u << 1 | 1] <= r) _modify(u << 1 | 1, l, r, val);
			push_up(u);
		}
		T _query(int u, int l, int r){
			if(left[u] >= l && right[u] <= r){
				return tr[u];
			}
			push_down(u);
			T ans = 0;
			if(right[u << 1] >= l) ans += _query(u << 1, l, r);
			if(left[u << 1 | 1] <= r) ans += _query(u << 1 | 1, l, r);
			return ans;
		}

		public:

		Segtree(){}
		Segtree(int n, std::vector <T> a){
			tr.resize(n * 4 + 5);
			left.resize(n * 4 + 5);
			right.resize(n * 4 + 5);
			lazytag.resize(n * 4 + 5);
			build(1, 1, n, a);
		}
		void modify(int l, int r, T val){
			_modify(1, l, r, val);
		}
		T query(int l, int r){
			return _query(1, l, r);
		}
	};

	template <typename T>
	class Dynamic_Segtree{
		class node{
			public:

			T val;
			T lazytag;
			T left, right;
			node *lson, *rson;
			node(){
				val = lazytag = left = right = 0;
				lson = rson = 0;
			}
			node(T l, T r){
				val = (r + l) * (r - l + 1) / 2;
				lazytag = 0;
				lson = rson = 0;
				left = l, right = r;
			}
		}*root;

		void push_up(node *cur){
			cur -> val = cur -> lson -> val + cur -> rson -> val;
		}

		void build_son(node *cur){
			if(cur -> lson) return;
			T l = cur -> left, r = cur -> right;
			T mid = (l + r) >> 1;
			cur -> lson = new node(l, mid);
			cur -> rson = new node(mid + 1, r);
		}

		void push_down(node *cur){
			T lazy = cur -> lazytag;
			node *ls = cur -> lson, *rs = cur -> rson;
			ls -> lazytag += lazy;
			rs -> lazytag += lazy;
			ls -> val += lazy * (ls -> right - ls -> left + 1);
			rs -> val += lazy * (rs -> right - rs -> left + 1);
			cur -> lazytag = 0;
		}

		void _modify(node *u, T l, T r, T val){
			if(u -> left >= l && u -> right <= r){
				u -> val += (u -> right - u -> left + 1) * val;
				u -> lazytag += val;
				return;
			}
			build_son(u);
			push_down(u);
			if(u -> lson -> right >= l) _modify(u -> lson, l, r, val);
			if(u -> rson -> left <= r) _modify(u -> rson, l, r, val);
			push_up(u);
		}

		T _query(node *u, T l, T r){
			if(u -> left >= l && u -> right <= r){
				return u -> val;
			}
			build_son(u);
			push_down(u);
			T ans = 0;
			if(u -> lson -> right >= l) ans += _query(u -> lson, l, r);
			if(u -> rson -> left <= r) ans += _query(u -> rson, l, r);
			return ans;
		}

		public:

		Dynamic_Segtree(){}
		Dynamic_Segtree(T l, T r){
			root = new node(l, r);
		}

		void modify(T l, T r, T val){
			_modify(root, l, r, val);
		}

		T query(T l, T r){
			return _query(root, l, r);
		}
	};

	template <typename T>
	class Mergable_Map{
		class node{
			public:

			T val;
			T left, right;
			node *lson, *rson;
			node(){
				val = left = right = 0;
				lson = rson = 0;
			}
			node(T l, T r){
				val = 0;
				lson = rson = 0;
				left = l, right = r;
			}
		}*root;

		void push_up(node *cur){
			cur -> val = cur -> lson -> val + cur -> rson -> val;
		}

		void build_son(node *cur){
			if(cur -> lson) return;
			T l = cur -> left, r = cur -> right;
			T mid = (l + r) >> 1;
			cur -> lson = new node(l, mid);
			cur -> rson = new node(mid + 1, r);
		}

		void _modify(node *u, T idx, T val){
			if(u -> left == u -> right){
				u -> val += val;
				return;
			}
			build_son(u);
			if(u -> lson -> right >= idx) _modify(u -> lson, idx, val);
			else _modify(u -> rson, idx, val);
			push_up(u);
		}

		node *_merge(node *u, node *&v){
			if(!u) return v;
			if(!v) return u;
			if(u -> left == u -> right){
				u -> val += v -> val;
				return u;
			}
			u -> lson = _merge(u -> lson, v -> lson);
			u -> rson = _merge(u -> rson, v -> rson);
			if(u -> lson) push_up(u);
			return u;
		}

		T _get_val(node *u, T idx){
			if(!u) return 0;
			if(u -> left == u -> right) return u -> val;
			build_son(u);
			if(u -> lson -> right >= idx) return _get_val(u -> lson, idx);
			return _get_val(u -> rson, idx);
		}

		T _nth_element(node *u, T k){
			if(!u || u -> val < k) return 0;
			if(u -> left == u -> right) return u -> left;
			build_son(u);
			if(u -> lson -> val >= k) return _nth_element(u -> lson, k);
			return _nth_element(u -> rson, k - u -> lson -> val);
		}

		T _get_rank(node *u, T idx){
			if(!u) return 0;
			if(u -> left == u -> right) return u -> val;
			build_son(u);
			if(u -> lson -> right >= idx) return _get_rank(u -> lson, idx);
			return _get_rank(u -> rson, idx) + u -> lson -> val;
		}

		T _get_pre(node *u, T idx){
			if(!u || !u -> val) return 0;
			if(u -> left >= idx) return 0;
			if(u -> left == u -> right) return u -> left;
			build_son(u);
			T ans = _get_pre(u -> rson, idx);
			if(ans) return ans;
			return _get_pre(u -> lson, idx);
		}

		T _get_next(node *u, T idx){
			if(!u || !u -> val) return 0;
			if(u -> right <= idx) return 0;
			if(u -> left == u -> right) return u -> left;
			build_son(u);
			T ans = _get_next(u -> lson, idx);
			if(ans) return ans;
			return _get_next(u -> rson, idx);
		}


		public:

		Mergable_Map(){}
		Mergable_Map(T l, T r){
			root = new node(l, r);
		}

		void modify(T idx, T val){
			_modify(root, idx, val);
		}

		T query(){
			return _query(root);
		}

		void merge(Mergable_Map &v){
			_merge(root, v.root);
			v = Mergable_Map(root -> left, root -> right);
		}

		T get_val(T idx){
			return _get_val(root, idx);
		}

		T nth_element(T k){
			return _nth_element(root, k);
		}

		T get_rank(T idx){
			return _get_rank(root, idx - 1) + 1;
		}

		T get_pre(T idx){
			return _get_pre(root, idx);
		}

		T get_next(T idx){
			return _get_next(root, idx);
		}
	};

    template <typename T>
	class HJT_Segtree{
		class node{
			public:

			T val;
			int left, right;
			node *lson, *rson;
			node(){
				val = left = right = 0;
				lson = rson = 0;
			}
		};
		std::vector <node*> roots;
		int len;

		void push_up(node *cur){
			cur -> val = cur -> lson -> val + cur -> rson -> val;
		}

		void build(node *cur, int l, int r, std::vector <T> &a){
			cur -> left = l;
			cur -> right = r;
			if(l == r){
				cur -> val = a[l];
				return;
			}
			int mid = (l + r) >> 1;
			node *ls = new node, *rs = new node;
			cur -> lson = ls;
			cur -> rson = rs;
			build(ls, l, mid, a);
			build(rs, mid + 1, r, a);
			push_up(cur);
		}

		void _build_new(node *cur, node *pre, int idx, T val){
			int l = pre -> left;
			int r = pre -> right;
			cur -> left = l;
			cur -> right = r;
			if(l == r){
				cur -> val = val;
				return;
			}
			int mid = (l + r) >> 1;
			node *ls, *rs;
			if(idx <= mid){
				ls = new node, rs = pre -> rson;
				cur -> lson = ls, cur -> rson = rs;
				_build_new(ls, pre -> lson, idx, val);
			}else{
				ls = pre -> lson, rs = new node;
				cur -> lson = ls, cur -> rson = rs;
				_build_new(rs, pre -> rson, idx, val);
			}
			push_up(cur);
		}

		T _query(node *cur, int l, int r){
			if(cur -> left >= l && cur -> right <= r){
				return cur -> val;
			}
			T ans = 0;
			if(cur -> lson -> right >= l) ans += _query(cur -> lson, l, r);
			if(cur -> rson -> left <= r) ans += _query(cur -> rson, l, r);
			return ans;
		}

		public:

		HJT_Segtree(){len = 0;}
		HJT_Segtree(int n, std::vector <T> a){
			node *root = new node;
			build(root, 1, n, a);
			roots.push_back(root);
		}

		void build_new(int pre, int idx, T val){
			node *cur = new node;
			_build_new(cur, roots[pre], idx, val);
			roots.push_back(cur);
		}

		T query(int pre, int l, int r){
			roots.push_back(roots[pre]);
			return _query(roots[pre], l, r);
		}
	};

	template <typename T>
	class Block{
		std::vector <T> a;
		std::vector <T> b;
		std::vector <T> lazytag;
		std::vector <int> belong, left, right;
		int n, len;

		void push_down(int idx){
			for(int i = left[idx]; i <= right[idx]; i++){
				a[i] += lazytag[idx];
			}
			lazytag[idx] = 0;
		}

		void push_up(int idx){
			for(int i = left[idx]; i <= right[idx]; i++){
				b[i] = a[i];
			}
			std::sort(b.begin() + left[idx], b.begin() + right[idx] + 1);
		}

		public:

		Block(){}
		Block(int n, std::vector <T> a){
			this -> n = n;
			len = sqrtl(n) + 1;
			this -> a.resize(n + 5);
			b.resize(n + 5);
			lazytag.resize(n / len + 5);
			belong.resize(n + 5);
			left.resize(n / len + 5);
			right.resize(n / len + 5);

			for(int i = 1; i <= n; i++){
				this -> a[i] = a[i];
				b[i] = a[i];
				belong[i] = (i - 1) / len + 1;
				right[belong[i]] = i;
				if(!left[belong[i]]) left[belong[i]] = i;
			}
			for(int i = 1; left[i]; i++){
				std::sort(b.begin() + left[i], b.begin() + right[i] + 1);
			}
		}

		void modify(int l, int r, T val){
			if(belong[l] == belong[r]){
				push_down(belong[l]);
				for(int i = l; i <= r; i++){
					a[i] += val;
				}
				push_up(belong[l]);
				return;
			}
			int curl = belong[l], curr = belong[r];
			push_down(curl), push_down(curr);
			for(int i = l; i <= right[curl]; i++){
				a[i] += val;
			}
			for(int i = curl + 1; i < curr; i++){
				lazytag[i] += val;
			}
			for(int i = left[curr]; i <= r; i++){
				a[i] += val;
			}
			push_up(curl), push_up(curr);
		}

		T query(int l, int r, T val){
			T ans = 0;
			if(belong[l] == belong[r]){
				push_down(belong[l]);
				push_up(belong[l]);
				for(int i = l; i <= r; i++){
					if(a[i] < val) ans = std::max(ans, a[i]);
				}
				return ans;
			}
			int curl = belong[l], curr = belong[r];
			push_down(curl), push_down(curr);
			push_up(curl), push_up(curr);
			for(int i = l; i <= right[curl]; i++){
				if(a[i] < val) ans = std::max(ans, a[i]);
			}
			for(int i = curl + 1; i < curr; i++){
				int idx = lower_bound(b.begin() + left[i], b.begin() + right[i] + 1, val - lazytag[i]) - b.begin() - 1;
				if(idx >= left[i]) ans = std::max(ans, b[idx] + lazytag[i]);
			}
			for(int i = left[curr]; i <= r; i++){
				if(a[i] < val) ans = std::max(ans, a[i]);
			}
			return ans;
		}
	};
	
	template <typename T>
	class FHQ_Treap{
		class node{
			public:

			T key, val, siz;
			ull pri;
			node *lson, *rson;
			node(T _k, T _v, ull _p){
				key = _k, val = _v, pri = _p;
				siz = _v;
				lson = rson = 0;
			}
		}*root;
		std::mt19937_64 rng;

		void push_up(node *cur){
			cur -> siz = cur -> val;
			if(cur -> lson) cur -> siz += cur -> lson -> siz;
			if(cur -> rson) cur -> siz += cur -> rson -> siz;
		}

		node *merge(node *x, node *y){
			if(!x && !y) return 0;
			if(!x) return y;
			if(!y) return x;
			if(x -> pri > y -> pri){
				y -> lson = merge(x, y -> lson);
				push_up(y);
				return y;
			}else{
				x -> rson = merge(x -> rson, y);
				push_up(x);
				return x;
			}
		}

		void split(node *cur, T x, node *&l, node *&r){
			if(!cur){
				l = 0, r = 0;
				return;
			}
			if(cur -> key > x){
				r = cur;
				split(cur -> lson, x, l, cur -> lson);
			}else{
				l = cur;
				split(cur -> rson, x, cur -> rson, r);
			}
			push_up(cur);
		}

		public:

		FHQ_Treap(){}
		FHQ_Treap(ull s){
			root = 0;
			rng.seed(s);
		}

		void modify(T key, T val){
			node *l, *mid, *r;
			split(root, key, l, r);
			split(l, key - 1, l, mid);

			if(!mid) mid = new node(key, val, rng());
			else{
				mid -> val += val;
				push_up(mid);
				if(!mid -> val){
					root = merge(l, r);
					return;
				}
			}
			root = merge(merge(l, mid), r);
		}

		T get_rank(T val){
			node *l, *r;
			split(root, val - 1, l, r);
			ll ans = (l ? l -> siz : 0);
			root = merge(l, r);
			return ans + 1;
		}

		T _nth_element(node *cur, T k){
			int lsize = 0;
			if(cur -> lson) lsize = cur -> lson -> siz;
			if(k <= lsize) return _nth_element(cur -> lson, k);
			if(k <= lsize + cur -> val) return cur -> key;
			return _nth_element(cur -> rson, k - lsize - cur -> val);
		}
		T nth_element(T k){
			return _nth_element(root, k);
		}

		T get_pre(T val){
			node *l, *r;
			split(root, val - 1, l, r);
			node *cur = l;
			ll ans = 0;
			while(cur){
				ans = cur -> key;
				cur = cur -> rson;
			}
			root = merge(l, r);
			return ans;
		}

		T get_next(T val){
			node *l, *r;
			split(root, val, l, r);
			node *cur = r;
			ll ans = 0;
			while(cur){
				ans = cur -> key;
				cur = cur -> lson;
			}
			root = merge(l, r);
			return ans;
		}
	};
	
	class Tree_Spliter{
		std::vector <std::vector <int>> edges;
		std::vector <int> dfn, dep, father, head, rank, son, siz;


		void dfs(int cur, int fa){
			father[cur] = fa;
			siz[cur] = 1;
			dep[cur] = dep[fa] + 1;
			for(int i:edges[cur]){
				if(i == fa) continue;
				dfs(i, cur);
				siz[cur] += siz[i];
				if(siz[son[cur]] < siz[i]) son[cur] = i;
			}
		}
		void dfs2(int cur, int top, int &curdfn){
			head[cur] = top;
			curdfn++;
			dfn[cur] = curdfn;
			rank[curdfn] = cur;
			if(!son[cur]) return;
			dfs2(son[cur], top, curdfn);
			for(int i:edges[cur]){
				if(i != son[cur] && i != father[cur]) dfs2(i, i, curdfn);
			}
		}

		public:

		Tree_Spliter(){}
		Tree_Spliter(int n, int root, std::vector <std::vector <int>> a){
			dfn.resize(n + 5), dep.resize(n + 5), father.resize(n + 5);
			head.resize(n + 5), rank.resize(n + 5);
			son.resize(n + 5), siz.resize(n + 5);

			edges = a;
			dfs(root, 0);
			int curdfn = 0;
			dfs2(root, root, curdfn);
		}

		int get_lca(int x, int y){
			int hx = head[x], hy = head[y];
			while(hx != hy){
				if(dep[hx] < dep[hy]) y = father[hy], hy = head[y];
				else x = father[hx], hx = head[x];
			}
			return (dep[x] < dep[y] ? x : y);
		}

		std::vector <pii> get_path(int x, int y){
			std::vector <pii> ans;
			int hx = head[x], hy = head[y];
			while(hx != hy){
				if(dep[hx] < dep[hy]){
					ans.push_back({dfn[hy], dfn[y]});
					y = father[hy], hy = head[y];
				}
				else{
					ans.push_back({dfn[hx], dfn[x]});
					x = father[hx], hx = head[x];
				}
			}
			if(dfn[x] > dfn[y]) std::swap(x, y);
			ans.push_back({dfn[x], dfn[y]});
			return ans;
		}

		pii get_subtree(int idx){
			return {dfn[idx], dfn[idx] + siz[idx] - 1};
		}

		int node_to_dfn(int idx){
			return dfn[idx];
		}
		int dfn_to_node(int idx){
			return rank[idx];
		}
	};
	
	class Trie{
		class node{
			public:

			node *next[26];
			int val;
			node(){
				memset(next, 0, sizeof(next));
				val = 0;
			}
		}*root;

		public:

		Trie(){
			root = new node;
		}

		void insert(std::string &s){
			node *cur = root;
			cur -> val++;
			for(char c:s){
				if(!cur -> next[c - 'a']) cur -> next[c - 'a'] = new node;
				cur = cur -> next[c - 'a'];
				cur -> val++;
			}
		}

		int find_pre(std::string &s){
			node *cur = root;
			for(char c:s){
				if(!cur -> next[c - 'a']) return 0;
				cur = cur -> next[c - 'a'];
			}
			return cur -> val;
		}
	};

	class dsu{
		std::vector <int> father, siz;

		public:

		int n, unions;
		dsu(){
			n = 0;
		}
		dsu(int n){
			this -> n = n;
			unions = n;
			father.resize(n + 5, 0);
			siz.resize(n + 5, 1);
			for(int i = 1; i <= n; i++){
				father[i] = i;
			}
		}
		int find(int n){
			return (father[n] == n ? n : father[n] = find(father[n]));
		}
		void merge(int x, int y){
			x = find(x), y = find(y);
			if(x == y) return;
			if(siz[x] < siz[y]) std::swap(x, y);
			siz[x] += siz[y];
			father[y] = x;
			unions--;
		}
	};

	template <typename T, int siz>
	class matrix{
		public:

		std::vector <std::vector <T>> a;
		T mod;
		matrix(T m){
			a.resize(siz, std::vector <T>(siz, 0));
			mod = m;
		}
		matrix(std::vector <std::vector <T>> v, T m){
			a = v;
			mod = m;
		}
		matrix operator * (matrix <T, siz> b){
			matrix <T, siz> ans(mod);
			for(int i = 0; i < siz; i++){
				for(int k = 0; k < siz; k++){
					for(int j = 0; j < siz; j++){
						ans.a[i][j] += a[i][k] * b.a[k][j] % mod;
						ans.a[i][j] %= mod;
					}
				}
			}
			return ans;
		}
	};

	void init(){
		std::ios::sync_with_stdio(0);
		std::cin.tie(0);
		std::cout.tie(0);
	}

	void solve(){
	}
}


int main(){
	cjdst::init();
	int T = 1;
	// std::cin >> T;
	for(int _ = 1; _ <= T; _++){
		cjdst::solve();
	}
	std::cout.flush();

	return 0;
}

主打一个自定义（（（

目前包含的内容：

Sparse_Table

数据结构：ST 表。

预处理： $O(n\log n)$ 。
query：查询 $\max_{j=l}^{r} A_j$ ， $O(1)$ ，常数较小。

可以替换成区间 $\min,\text{and},\text{or}$ 等。

Fenwick_Tree

数据结构：树状数组。

预处理： $O(n)$ 。
modify：将 $A_i$ 增加 $k$ ， $O(\log n)$ ，常数极小。
query：查询 $\sum_{j=1}^{i} A_j$ ， $O(\log n)$ ，常数极小。

可以替换成前缀异或、前缀最值等。

Segtree

数据结构：线段树。

预处理： $O(n)$ 。
modify：将 $A_l,A_{l+1},...,A_r$ 的值增加 $k$ ， $O(\log n)$ ，常数较大。
query：查询 $\sum_{j=l}^r A_j$ ， $O(\log n)$ ，常数较大。

可以替换成区间最值，区间 $k$ 次方和等。

Dynamic_Segtree

数据结构：线段树（动态开点）。

预处理： $O(1)$ 。
modify：将 $A_l,A_{l+1},...,A_r$ 的值增加 $k$ ，时空复杂度 $O(\log n)$ ，常数极大。
query：查询 $\sum_{j=l}^r A_j$ ，时空复杂度 $O(\log n)$ ，常数极大。

Mergable_Map

数据结构：线段树（动态开点）。

预处理： $O(1)$ 。
modify：将集合增加 $k$ （ $k$ 可以小于 $0$ ）个 $x$ ，时空复杂度 $O(\log V)$ ，常数较大。
一堆 query：时空复杂度反正都是 $O(\log V)$ ，常数较大。
merge：将另一个集合合并至该集合，时空复杂度均摊 $O(\log V)$ ，常数较大。

HJT_Segtree

数据结构：可持久化线段树/主席树。

预处理： $O(n)$ 。
build_new：新建一个数组 $A_{new}$ ，使 $A_{new,j}=A_{pre,j}$ ，并修改 $A_{new,i}=k$ ， $O(\log n)$ ，常数较大。
query：查询 $\sum_{j=l}^r A_{i,j}$ ， $O(\log n)$ ，常数中等。

Block

数据结构：分块。

预处理： $O(n\log n)$ 。
modify：将 $A_l,A_{l+1},...,A_r$ 的值增加 $k$ ， $O(\sqrt n\log n)$ 。
query：查询 $\max_{j=l}^r A_j\times [A_j\lt k]$ ， $O(\sqrt n\log n)$ 。

这个可以改的就很多了，几乎可以说是万能数据结构。

FHQ_Treap

数据结构：替罪羊树。

modify：加入 $k$ （ $k$ 可以小于 $0$ ）个 $x$ ，时间复杂度均摊 $O(\log n)$ ，空间复杂度 $O(1)$ ，常数巨大。
一堆 query：时间复杂度都是严格 $O(\log n)$ 的，常数较大。

Tree_Spliter

算法：树链剖分。

预处理： $O(n)$ 。
点和编号互相转化： $O(1)$ 。
lca：给定两个点 $x,y$ ，求它们在树上的最近公共祖先的编号， $O(\log n)$ ，常数极小。
get_path：给定两个点 $x,y$ ，求它们在树上的路径的所有点的编号，并且压缩成不超过 $2\log_2 n$ 个区间， $O(\log n)$ ，常数极小。
get_subtree：给定一个点 $x$ ，求它以及它的所有子树的点的编号，并且压缩成一个区间， $O(1)$ 。

Trie

预处理： $O(|\Sigma|)$ 。
insert：添加一个字符串 $S$ ， $O(|S|\times |\Sigma|)$ 。
find_pre：查询以 $S$ 为前缀的字符串数量， $O(|S|)$ 。

dsu

数据结构：并查集。

预处理： $O(n)$ 。
find：查询一个点所在集合的代表， $O(\alpha(n))$ 。
merge合并两个集合， $O(\alpha(n))$ 。

可以删除路径压缩优化，用作可撤销并查集，此时查询、合并时间复杂度均为 $O(\log n)$ 。

matrix

数据结构：矩阵。

预处理： $O(n^2)$ 。
乘法： $O(n^3)$ 。

SCC_solver

算法：Tarjan 求 SCC。

get_SCC：对一个大小为 $n$ ，有 $m$ 条边的图，求它的所有 SCC（强联通分量）， $O(n+m)$ 。

废弃（暂无用处）

namespace pipilong{
    template <typename T>
	class Goat_Tree{
		const double B = 0.75;
		class node{
			public:

			T key, val;
			T siz, realsiz;
			node *lson, *rson;
			node(){}
			node(T k, T v){
				key = k, val = v, siz = v;
				realsiz = 1;
				lson = rson = 0;
			}
		}*root;

		void push_up(node *cur){
			cur -> siz = cur -> val;
			cur -> realsiz = 1;
			if(cur -> lson){
				cur -> siz += cur -> lson -> siz;
				cur -> realsiz += cur -> lson -> realsiz;
			}
			if(cur -> rson){
				cur -> siz += cur -> rson -> siz;
				cur -> realsiz += cur -> rson -> realsiz;
			}
		}

		void get_subtree(node *cur, std::vector <T> &k, std::vector <T> &v){
			if(!cur) return;
			get_subtree(cur -> lson, k, v);
			k.push_back(cur -> key);
			v.push_back(cur -> val);
			get_subtree(cur -> rson, k, v);
		}

		node *_rebuild(std::vector <T> &k, std::vector <T> &v, int l, int r, node *cur){
			if(l > r) return 0;
			int mid = (l + r) >> 1;
			if(!cur) cur = new node(k[mid], v[mid]);
			else (*cur) = node(k[mid], v[mid]);
			cur -> lson = _rebuild(k, v, l, mid - 1, 0);
			cur -> rson = _rebuild(k, v, mid + 1, r, 0);
			push_up(cur);
			return cur;
		}

		void rebuild(node *cur){
			std::vector <T> k, v;
			get_subtree(cur, k, v);
			_rebuild(k, v, 0, k.size() - 1, cur);
		}

		node *_modify(node *&cur, T k, T v){
			if(!cur){
				cur = new node(k, v);
				return 0;
			}
			if(cur -> key == k){
				cur -> val += v;
				cur -> siz += v;
				return 0;
			}
			node *ans = 0;
			if(cur -> key > k) ans = _modify(cur -> lson, k, v);
			else ans = _modify(cur -> rson, k, v);
			push_up(cur);
			if((cur -> lson && cur -> lson -> realsiz >= cur -> realsiz * B) ||
			(cur -> rson && cur -> rson -> realsiz >= cur -> realsiz * B)) ans = cur;
			return ans;
		}

		public:

		Goat_Tree(){root = 0;}

		void modify(T k, T v){
			node *cur = _modify(root, k, v);
			if(cur) rebuild(cur);
		}

		T get_rank(T k){
			node *cur = root;
			ll ans = 0;
			while(cur){
				if(cur -> key > k){
					cur = cur -> lson;
					continue;
				}
				if(cur -> lson) ans += cur -> lson -> siz;
				if(cur -> key == k) return ans + 1;
				ans += cur -> val;
				cur = cur -> rson;
			}
			return ans + 1;
		}

		T nth_element(T k){
			node *cur = root;
			while(k){
				if(cur -> lson){
					if(cur -> lson -> siz >= k){
						cur = cur -> lson;
						continue;
					}
					k -= cur -> lson -> siz;
				}
				if(cur -> val >= k) return cur -> key;
				k -= cur -> val;
				cur = cur -> rson;
			}
			return cur -> key;
		}

		T get_pre(T val){
			return nth_element(get_rank(val) - 1);
		}

		T get_next(T val){
			return nth_element(get_rank(val + 1));
		}
	};
}

有帮助，赞一个

去预览

0/2000

全部评论 24

༺ཉStars_Seekerད༻
主播主播，能用这个码蜂去洛谷打比赛吗

2026-01-13 来自重庆
2
- cjdst
  回复
  ༺ཉStars_Seekerད༻
  和意为
  
  2026-01-13 来自广东
  1
༺ཌༀཉི༒白·羊༒༃ༀད༻
阅（（（

2025-12-06 来自上海
2
Eucatastrophe‌
经过AI判定，代码AI相似度高达80%（

2025-12-17 来自浙江
1
- 次元骑手
  回复
  Eucatastrophe‌
  没有的20%是头文件和注释
  
  2026-01-14 来自浙江
  0
- Eucatastrophe‌
  回复
  次元骑手
  并非
  
  2026-01-19 来自浙江
  0
Grapher
大家好啊，我是最新款童瑞琪大模型

2025-11-09 来自浙江
1
cjdst
d

2026-02-06 来自广东
0
Xylophone
合并集合都有啊%%%

2026-01-14 来自广东
0
Xylophone
甚至12个算法

2026-01-14 来自广东
0
Xylophone
这个点还能上机您是人类吗

2026-01-14 来自广东
0
Xylophone
%%%

2026-01-14 来自广东
0
Xylophone
只有我觉得写类不好看吗（无恶意）

2026-01-14 来自广东
0
- cjdst
  回复
  Xylophone
  感觉class更正式，其实和struct差不多的（
  
  2026-01-14 来自广东
  0
- Xylophone
  回复
  cjdst
  是的，觉得很有学术感
  
  2026-01-14 来自广东
  0
- Xylophone
  回复
  cjdst
  但是以前有本c++教材看得我发誓用struct替代class
  
  2026-01-14 来自广东
  0
༺ཌༀཉི༒白·羊༒༃ༀད༻
这是你自己写的吗？

2025-12-14 来自上海
0
古希腊掌管AC和WA的神
建议加一个快速傅里叶变换（（（

2025-12-10 来自上海
0
- cjdst
  回复
  古希腊掌管AC和WA的神
  buhui
  
  2025-12-10 来自广东
  0
MuktorFM
前摇过长（

2025-12-06 来自云南
0
- cjdst
  回复
  MuktorFM
  ？
  
  2025-12-06 来自广东
  0
Grapher
越来越逆天了，你加点数据结构也还说得过去，这他妈SCC是几个意思？（话说可以把珂朵莉树，Splay也加进去

2025-12-06 来自浙江
0
- Grapher
  回复
  Grapher
  
  2025-12-06 来自浙江
  0
- cjdst
  回复
  Grapher
  美学
  
  2025-12-06 来自广东
  1
- cjdst
  回复
  Grapher
  你这名字何意味
  
  2025-12-06 来自广东
  0
cjdst
在这里的分块没调块长

2025-11-22 来自广东
0
cjdst
d

2025-11-16 来自广东
0
XRiaB
被调成啥了这大模型

2025-11-14 来自广东
0
- cjdst
  回复
  XRiaB
  问号
  
  2025-11-14 来自广东
  0
地下城
0

2025-11-14 来自湖南
0
cjdst
d

2025-11-14 来自广东
0
古希腊掌管AC和WA的神
骸刑，没我IA

2025-11-09 来自上海
0