一些简单的竞赛小知识

首先在 $C ++$ 中我们常用的换行符是 $endl$，因为更好打，但是 $endl$ 是在换行的同时具有刷新缓冲区的作用的，这样带来的后果就是导致 $endl$ 的耗时是比 '\n' 是要慢一些的，尤其是在多组询问输出具有很多行的时候体现的非常明显， 所以我们一般会在头文件后面加上一行#define endl '\n'用来加快我们的输出速度，但是切记在写交互题这种需要刷新缓冲区的时候就要把这一行代码给删掉 除此之外呢，$C++$ 的输入输出是要比 $C$ 语言的 $scanf$ 和 $printf$ 要慢一些的，所以我们需要一个叫做关闭同步流的方式来提升 $C++$ 的输入输出速度，具体原理可以去网上搜索一下，那么就有了我们的开头

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	//开始编写代码
	
	return 0;
}

码风推荐是 $jiangly$（可以说是世界最强的算竞选手之一了，这里是他的Codeforces主页，可以查看他的代码）的码风，非常标准

个人算法模板

个人的开头模板（大部分取自 $jiangly$）

以下模板基于此初始化（并不是非常标准），建议同学们能够养成自己的码风和变量命名习惯，尽可能多得去使用 $STL$ 标准库，便于自己理解和阅读，同时带来程序时间和空间开销上更优

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <cmath>
#include <ctime>
#include <random>
#include <chrono>
#include <functional>
#include <cassert>
#include <iomanip>
#define ff first
#define se second
#define endl '\n'
using namespace std;
using i32 = signed;
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using f64 = long double;
using i128 = __int128;
using u128 = unsigned __int128;
constexpr long long inf = 1e18;

typedef pair<int, int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 2e5 + 10, INF = 0x3f3f3f3f, mod = 1e9 + 7;

void tell(int l, vector<int> &v)
{
	for(int i = l; i < v.size(); i ++)
		cout <<v[i] <<" \n"[i == v.size() - 1];
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	
	
	return 0;
}

高精度

高精度加法

string add(string a, string b)
{
    string c;
    reverse(a.begin(), a.end()), reverse(b.begin(), b.end());
    int t = 0, i = 0;
    while(i < a.size() || i < b.size() || t)
    {
        if(i < a.size()) t += a[i] - '0';
        if(i < b.size()) t += b[i] - '0';
        c.push_back(t % 10 + '0');
        t /= 10, i ++;
    }
    reverse(c.begin(), c.end());
    return c;
}

高精度减法

#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(string a, string b)
{
    if(a.size() != b.size()) return a.size() > b.size();
    for(int i = 0; i < a.size(); i ++)
        if(a[i] != b[i]) return a[i] > b[i];
    return true;
}

string sub(string a, string b)
{
    string c;
    reverse(a.begin(), a.end()), reverse(b.begin(), b.end());

    int i = 0, t = 0;
    for(int i = 0; i < a.size(); i ++)
    {
        t += a[i] - '0';
        if(i < b.size()) t -= b[i] - '0';

        c.push_back((t + 10) % 10 + '0');
        t = (t < 0) ? -1 : 0;
    }
    while(c.size() > 1 && c.back() == '0') c.pop_back();
    reverse(c.begin(), c.end());
    return c;
}

int main()
{
    string a, b; cin >>a >>b;
    if(cmp(a, b))
    {
        string c = sub(a, b);
        cout <<c <<endl;
    }
    else
    {
        string c = sub(b, a);
        cout <<"-" <<c <<endl;
    }
    return 0;
}

快速幂及逆元

int quick_pow(int a, i64 b, int p = mod)
{
	int res = 1;
	while(b)
	{
		if(b & 1) res = 1LL * res * a % p;

		a = 1LL * a * a % p;
		b >>= 1;
	}
	return res % p;
}

int inv(int x)
{
	return quick_pow(x, mod - 2, mod);
}

线性筛

vector<int> minp, primes;
int cnt;

void sieve(int n)
{
	minp.assign(n + 1, 0);
	primes.clear();

	for(int i = 2; i <= n; i ++)
	{
		if(!minp[i])
		{
			minp[i] = i;
			primes.push_back(i);
		}
		for(auto p : primes)
		{
			if(i * p > n) break;

			minp[i * p] = p;
			if(p == minp[i]) break;
		}
	}
}

并查集

struct DSU
{
	vector<int> p, siz;

	void initial(int n)
	{
		p.resize(n + 1);
		iota(p.begin(), p.end(), 0);

		siz.assign(n + 1, 1);
	}

	DSU(int n)
	{
		initial(n);
	}

	int find(int x)
	{
		if(x != p[x]) p[x] = find(p[x]);
		return p[x];
	}

	bool same(int a, int b)
	{
		return find(a) == find(b);
	}

	void merge(int a, int b)
	{
		a = find(a), b = find(b);
		if(a == b) return ;

		siz[a] += siz[b];
		p[b] = a;
	}

	int size(int x)
	{
		return siz[find(x)];
	}
};

组合数学

int fac[N], invfac[N];

int quick_pow(int a, i64 b, int p)
{
	int res = 1;
	while(b)
	{
		if(b & 1) res = 1LL * res * a % p;

		a = 1LL * a * a % p;
		b >>= 1;
	}
	return res % p;
}

void initial()
{
	fac[0] = invfac[0] = 1;
	for(int i = 1; i < N; i ++)
	{
		fac[i] = (ll)fac[i - 1] * i % mod;
		invfac[i] = (ll)invfac[i - 1] * quick_pow(i, mod - 2, mod) % mod;
	}
}

int binom(int n, int m)
{
	if(n < m || m < 0) return 0;
	return 1LL * fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
//注:函数开始时必须调用initial

线段树

struct SegmentTree
{
	struct node
	{
		int l, r;
		i64 sum, val1, val2, lazy;//val1, val2分别是区间的最大最小值
		bool f;
		i64 set_lazy;
	};
	vector<int> w;
	vector<node> tree;
	
	void pushup(int u)
	{
		auto pushup = [&](node &p, node &l, node &r) -> void
		{
			p.sum = l.sum + r.sum;
			p.val1 = max(l.val1, r.val1);
			p.val2 = min(l.val2, r.val2);
		};
		pushup(tree[u], tree[u << 1], tree[u << 1 | 1]);
	}
	
	void initial(int n)
	{
		w.resize(n + 1);
		tree.resize(4 * n + 1);
		
		auto build = [this](auto &&self, int u, int l, int r) -> void
		{
			if(l == r)
			{
				tree[u] = {l, r, w[l], w[l], w[l], 0, false, -inf};
				return ;
			}
			tree[u] = {l, r, 0, 0, 0, 0, false, -inf};
			int mid = l + r >> 1;
			self(self, u << 1, l, mid), self(self, u << 1 | 1, mid + 1, r);
			pushup(u);
		};
		build(build, 1, 1, n);
	}
	
	SegmentTree() {}
	SegmentTree(int n)
	{
		initial(n);
	}
	SegmentTree(vector<int> a)
	{
		int n = a.size() - 1;
		w.resize(n + 1);
		for(int i = 1; i <= n; i ++)
			w[i] = a[i];
		initial(n);
	}
	
	void apply_set(node &u, i64 set_lazy)
	{
		u.sum = 1LL * (u.r - u.l + 1) * set_lazy;
		u.val1 = u.val2 = u.set_lazy = set_lazy;
		u.f = true;
		u.lazy = 0;
	}
	
	void apply_add(node &u, i64 lazy)
	{
		if(u.f)
		{
			u.set_lazy += lazy;
			u.sum += 1LL * (u.r - u.l + 1) * lazy;
			u.val1 += lazy, u.val2 += lazy;
		}
		else
		{
			u.sum += 1LL * (u.r - u.l + 1) * lazy;
			u.val1 += lazy, u.val2 += lazy;
			u.lazy += lazy;
		}
	}
	
	void pushdown(int u)
	{
		if(tree[u].f)//优先处理赋值操作
		{
			apply_set(tree[u << 1], tree[u].set_lazy);
			apply_set(tree[u << 1 | 1], tree[u].set_lazy);
			tree[u].f = false;
		}
		if(tree[u].lazy == 0) return ;
		apply_add(tree[u << 1], tree[u].lazy);
		apply_add(tree[u << 1 | 1], tree[u].lazy);
		tree[u].lazy = 0;
	}
	
	void rangeSet(int u, int l, int r, int x)
	{
		if(tree[u].l >= l && tree[u].r <= r)
		{
			apply_set(tree[u], x);
			return ;
		}
		
		pushdown(u);
		int mid = tree[u].l + tree[u].r >> 1;
		if(l <= mid) rangeSet(u << 1, l, r, x);
		if(r >= mid + 1) rangeSet(u << 1 | 1, l, r, x);
		pushup(u);
	}
	
	void rangeAdd(int u, int l, int r, int x)
	{
		if(tree[u].l >= l && tree[u].r <= r)
		{
			apply_add(tree[u], x);
			return ;
		}
		
		pushdown(u);
		
		int mid = tree[u].l + tree[u].r >> 1;
		if(l <= mid) rangeAdd(u << 1, l, r, x);
		if(r >= mid + 1) rangeAdd(u << 1 | 1, l, r, x);
		pushup(u);
	}
	
	i64 max_query(int u, int l, int r)
	{
		if(tree[u].l >= l && tree[u].r <= r) return tree[u].val1;
		
		pushdown(u);
		int mid = tree[u].l + tree[u].r >> 1;
		
		i64 res = -inf;
		if(l <= mid) res = max(res, max_query(u << 1, l, r));
		if(r >= mid + 1) res = max(res, max_query(u << 1 | 1, l, r));
		return res;
	}
	
	i64 min_query(int u, int l, int r)
	{
		if(tree[u].l >= l && tree[u].r <= r) return tree[u].val2;
		
		pushdown(u);
		int mid = tree[u].l + tree[u].r >> 1;
		
		i64 res = inf;
		if(l <= mid) res = min(res, min_query(u << 1, l, r));
		if(r >= mid + 1) res = min(res, min_query(u << 1 | 1, l, r));
		return res;
	}
	
	i64 rangeSum(int u, int l, int r)
	{
		if(tree[u].l >= l && tree[u].r <= r) return tree[u].sum;
		
		pushdown(u);
		int mid = tree[u].l + tree[u].r >> 1;
		
		i64 res = 0;
		if(l <= mid) res += rangeSum(u << 1, l, r);
		if(r >= mid + 1) res += rangeSum(u << 1 | 1, l, r);
		return res;
	}
	
	int find_first(int u, int ql, int qr, int l, int r)//求第一个不在区间内的数
	{
		//无交集返回-1
		if(tree[u].l > qr || tree[u].r < ql) return -1;
		
		//完美包含但不满足返回-1
		if(tree[u].l >= ql && tree[u].r <= qr && tree[u].val1 <= r && tree[u].val2 >= l) return -1;
		
		if(tree[u].l == tree[u].r) return tree[u].l;
		
		pushdown(u);
		
		int c = find_first(u << 1, ql, qr, l, r);
		if(c != -1) return c;
		return find_first(u << 1 | 1, ql, qr, l, r);
	}
	
	int find_last(int u, int ql, int qr, int l, int r)//求最后一个不在区间内的数
	{
		//无交集返回-1
		if(tree[u].l > qr || tree[u].r < ql) return -1;
		
		//完美包含但不满足返回-1
		if(tree[u].l >= ql && tree[u].r <= qr && tree[u].val1 <= r && tree[u].val2 >= l) return -1;
		
		if(tree[u].l == tree[u].r) return tree[u].l;
		
		pushdown(u);
		
		int c = find_last(u << 1 | 1, ql, qr, l, r);
		if(c != -1) return c;
		return find_last(u << 1, ql, qr, l, r);
	}
};
//注:find_first/last中不满足条件就是对条件取反, 并注意对val1, val2进行修改