Texcavator 的秘密基地

unique + erase 去除重复值result.erase(unique(result.begin(),result.end()),result.end()); upper_bound 和 lower_boundupper_bound找到第一个大于 x 的位置，lower_bound找到第一个大于等于 x 位置加greater<int>()就相反注意数组一定要排好序int pos1=lower_bound(num,num+6,7)-num;int pos2=lower_bound(num,num+6,7,greater<int>())-num; next_permutation 和 prev_permutation全排列函数next_permutation 从前往后排列prev_permutation 从后往前排列（这里的从前往后和从后往前指的是字典序，在后面有举例）int num[3] = {1, 2, 3}; do { cout << num[0] << &qu ...

板子 #include <bits/stdc++.h>using namespace std;const int N = 2e5 + 5;int n;// g[u]: 存储与 u 相邻的结点vector<int> g[N];// sz: 子树大小// big: 重儿子// col: 结点颜色// L[u]: 结点 u 的 DFS 序// R[u]: 结点 u 子树中结点的 DFS 序的最大值// Node[i]: DFS 序为 i 的结点// ans: 存答案// cnt[i]: 颜色为 i 的结点个数// totColor: 目前出现过的颜色个数int sz[N], big[N], col[N], L[N], R[N], Node[N], totdfn;int ans[N], cnt[N], totColor;void add(int u) { if (cnt[col[u]] == 0) ++totColor; cnt[col[u]]++;}void del(int u) { cnt[col[u]]--; if (cnt[ ...

主席树 即为 可持久化线段树，是一种可以记录每一个修改版本的数据结构。 难以进行区间的修改操作 主席树存储的信息 struct Node{ int l, r; // 左结点和右结点 int cnt; // 区间内有多少数}; 下面以图示表示主席树记录修改的过程 接下来是一道例题 第k小数 给定长度为 $N$ 的整数序列 $A$，下标为 $1∼N$。 现在要执行 $M$ 次操作，其中第 $i$ 次操作为给出三个整数 $l_i,r_i,k_i$，求 $A[l_i],A[l_i+1],…,A[r_i]$ (即 $A$ 的下标区间 $[l_i,r_i]$中第 $k_i$ 小的数是多少。 输入格式 第一行包含两个整数 $N$ 和 $M$。 第二行包含 $N$ 个整数，表示整数序列 $A$。 接下来 $M$ 行，每行包含三个整数 $l_i,r_i,k_i$，用以描述第 $i$ 次操作。 输出格式 对于每次操作输出一个结果，表示在该次操作中，第 $k$ 小的数的数值。 每个结果占一行。 数据范围 $N≤105,M≤104,|A[i]|≤109$ 输入样例： 7 31 ...

转载自：exgcd详解 - zzt1208 - 博客园 (cnblogs.com) 1.exgcd是什么？exgcd大名扩展欧几里得算法，用来求形如 $ax+by=gcd(a,b)$（$a,b$ 为常数）的方程的一组整数解。 2.推导当 $b=0$ 时，$gcd(a,b)=a$，此时 $x=1$， $y=0$ 当 $b≠0$ 时，考虑到 $gcd(a,b)=gcd(b,a\ mod\ b)$，所以我们可以先递归去求 $bx+(a\ mod\ b)y=gcd(b,a\ mod\ b)$ 的解 \begin{cases} x=x_0 \\ y=y_0 \end{cases}然后再往回带： \begin{aligned} ax+by&=gcd(a, b) \\ &=gcd(b,a\ mod\ b) \\ &=bx_0+(a\ mod\ b)y_0 \end{aligned}因为 $a\ mod\ b=a−⌊\frac{a}{b}⌋b$，所以： \begin{aligned} ax+by&=bx_0+(a−⌊\frac{a}{b}⌋b)y_0 \\ &=bx_0+ay_0−⌊\frac ...

最大公约数gcd板子int gcd(int a, int b){ return b > 0 ? gcd(b, a % b) : a;} 最小公倍数lcm板子int lcm(int a, int b){ return a / gcd(a, b) * b;} 性质 gcd(a, b) * lcm(a, b) = a * b gcd(a, b) = gcd(a, b - a) gcd(a, b, c) = gcd(a, gcd(b, c))