换新马蜂了，望周知

userId_undefined

cjdstttttt

题解仙人时空双修者尊贵铂金勇敢小狗CSP-J一等奖出题人

2025-11-16 13:26:08

发布于：广东

60阅读
0回复
0点赞
#include <bits/stdc++.h>
namespace cjdst{

	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);
		}
	};
	
	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;
		}
	};
	
	template <typename T>
	class Multi_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:

		Multi_Segtree(){len = 0;}
		Multi_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);
		}
	};
	
	namespace SCC_solver{
		std::vector <int> dfn, low, scc;
		std::vector <int> stack;
		int curdfn, curscc;
		void dfs(int cur, std::vector <std::vector <int>> &edge){
			curdfn++;
			dfn[cur] = curdfn;
			low[cur] = curdfn;
			stack.push_back(cur);
			for(int i:edge[cur]){
				if(scc[i] != -1) continue;
				if(dfn[i] == -1){
					dfs(i, edge);
					low[cur] = std::min(low[cur], low[i]);
				}else low[cur] = std::min(low[cur], dfn[i]);
			}
			if(low[cur] == dfn[cur]){
				curscc++;
				int tmp = stack.back();
				do{
					tmp = stack.back();
					scc[tmp] = curscc;
					stack.pop_back();
				}while(tmp != cur);
			}
		}
		std::vector <int> get_SCC(int n, std::vector <std::vector <int>> edge){
			dfn.resize(n + 5, -1);
			low.resize(n + 5, -1);
			scc.resize(n + 5, -1);
			for(int i = 1; i <= n; i++){
				if(scc[i] == -1) dfs(i, edge);
			}
			low.clear();
			dfn.clear();
			stack.clear();
			std::vector <int> ans;
			ans.swap(scc);
			curdfn = curscc = 0;
			return ans;
		}
	};

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

	typedef long long ll;
	typedef unsigned long long ull;
	typedef std::pair <int, int> pii;
	typedef std::pair <ll, ll> pll;

	void solve(){
	}
}


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

	return 0;
}

主打一个自定义（（（

目前包含的内容：

Fenwick_Tree

数据结构：树状数组。

  • 预处理：O(n)O(n)。
  • modify：将 AiA_i 增加 kk，O(log⁡n)O(\log n)，常数极小。
  • query：查询 ∑j=1iAj\sum_{j=1}^{i} A_j，O(log⁡n)O(\log n)，常数极小。

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

Segtree

数据结构：线段树。

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

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

dsu

数据结构：并查集。

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

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

matrix

数据结构：矩阵。

  • 预处理：O(n2)O(n^2)。
  • 乘法：O(n3)O(n^3)。

Multi_Segtree

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

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

SCC_solver

算法：Tarjan 求 SCC。

  • get_SCC：对一个大小为 nn，有 mm 条边的图，求它的所有 SCC（强联通分量），O(n+m)O(n+m)。
userId_undefined
去预览
0/2000

全部评论 10

热门讨论