杂模板
inline int rd()
{
int data = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9')
{
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9')
{
data = (data<<3) + (data<<1) + ch - '0';
ch = getchar();
}
return f * data;
} 模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p
(a – b) % p = (a % p – b % p) % p
(a * b) % p = (a % p * b % p) % p
ab % p = ((a % p)b) % p
结合率：
((a+b) % p + c) % p = (a + (b+c) % p) % p
struct node
{
int to;
int w;
int next;
}edge[100005];
int head[100005];
int cnt=0;
void add(int u,int v,int w)
{
edge[u].to=v;
edge[u].w=w;
edge[u].next=head[u];
head[u]=cnt++;
} #pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
} 字典树模板 int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}
// 查询字符串出现的次数
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
} 哈希表模板 (1) 拉链法
int h[N], e[N], ne[N], idx;
// 向哈希表中插入一个数
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}
(2) 开放寻址法
int h[N];
// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
} 重载操作符 bool operator < (const node &a) const
{
if(this->mark==a.mark)
{
return this->id<a.id;
}
return this->mark>b.mark;
} 字符串的进制转换 string s = "123456"; int t = strtol(s.c_str(), NULL, 10); cout << t;
2.lower_bound：查找第一个大于或等于某个元素的位置。
a.函数模板：lower_bound(arr[],arr[]+size , indx):
b.参数说明：
arr[]： 数组首地址
size：数组元素个数
indx:需要查找的值
c.函数功能： 函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置(注意是地址)。如果所有元素都小于val，则返回last的位置
d.举例如下：
一个数组number序列为：4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标，则
/*注意因为返回值是一个指针，所以减去数组的指针就是int变量了*/
pos = lower_bound( number, number + 8, 3) - number，pos = 0.即number数组的下标为0的位置。
pos = lower_bound( number, number + 8, 9) - number， pos = 1，即number数组的下标为1的位置（即10所在的位置）。
pos = lower_bound( number, number + 8, 111) - number， pos = 8，即number数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。
e.注意：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！
返回查找元素的第一个可安插位置，也就是“元素值>=查找值”的第一个元素的位置
3.upper_bound：查找第一个大于某个元素的位置。
a.函数模板：upper_bound(arr[],arr[]+size , indx):
b.参数说明：
arr[]： 数组首地址
size：数组元素个数
indx:需要查找的值
c.函数功能：函数upper_bound()返回的在前闭后开区间查找的关键字的上界，返回大于val的第一个元素位置
例如：一个数组number序列1,2,2,4.upper_bound(2)后，返回的位置是3（下标）也就是4所在的位置,同样，如果插入元素大于数组中全部元素，返回的是last。(注意：数组下标越界)
void print(__int128 x)
{
if(x < 0) {putchar('-');x = -x;}
if(x/10) print(x/10);
putchar(x%10+'0');
} bool isPowerOfTwo(int n) { //判断这个值是否是2的幂
return (n & (n - 1)) == 0;
} 
