结构体模板（持续更新）

七分 / 2023-08-09 / 原文

树状数组：

点击查看代码

//1
struct Tree {
	vector<int> tr;  //vector 方便每根据需要的大小开
    Tree(int n) : n(n), tr(n + 1) {}
  //  Tree(int n) : tr(n + 1){  //初始化 
  //      iota(tr.begin(), tr.end(), 0); 
  //  }
	inline int lowbit(int x) {
	return x & -x;
	}
	inline void add(int x, int v) {
	for (; x <= n; x += lowbit(x))
	tr[x] += v;
	}
	inline int ask(int x) {
	int res = 0;
	for (; x; x -= lowbit(x))
	res += tr[x];
	return res;
	}
	void clear() {
		tr.clear();
	}
}t1(n),t2(n);;


//2
  struct Fenwick {
	int tr[N];
	inline int lowbit(int x) {
	return x & -x;
	}
	inline void add(int x, int v) {
	for (; x <= n; x += lowbit(x))
	tr[x] += v;
	}
	inline int ask(int x) {
	int res = 0;
	for (; x; x -= lowbit(x))
	res += tr[x];
	return res;
	}
	void clear() {
	memset(tr, 0, sizeof tr);
	}
}t1,t2;

并查集：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
// DSU with Size 
struct DSU{ //并查集板子 
    vector<int> p, sz; //p 表示集合  ， se表示集合个数
    DSU(int n) : p(n + 1), sz(n + 1, 1){  //初始化 
        iota(p.begin(), p.end(), 0); 
    }

    int find(int x){ //寻找根节点
        return p[x] == x ? x : p[x] = find(p[x]);
    }

    bool same(int x, int y) {  //判断是否相同，根节点 
        return find(x) == find(y); 
    }

    bool merge(int x, int y){ //合并集合 
        x = find(x), y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        p[y] = x;
        return true;
    }
    
    int size(int x) {  //输出集合点数
        return sz[find(x)];
    }
};
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	DSU dsu(n);
	char c;
	int x,y;
	while(m--)
	{
		cin>>c>>x>>y;
		if(c=='Q')
		{
			if(dsu.same(x,y)) cout<<"Yes\n";
			else cout<<"No\n";
		}
		else
		{
			dsu.merge(x,y);
		}
	}
	return 0;
}