• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# OI 基础模板

4小时前 2次浏览

(text{Update:})

``````2021.9.15
STL 新增写了 list, multimap, bieset 等
``````

``````
2021.9.10

2021.9.8

2021.9.1

2021.8.29

2021.8.20

2021.7.24

2021.7.22

2021.7.7

2021.7.4

2021.7.3

2021.7.2

2021.6.30

2021.6.29

2021.6.28

2021.6.15

2021.6.14

2021.5.30

2021.5.16

2021.5.14

2021.4.29

2021.4.28

2021.4.23

2021.4.20

``````

## 考试必备

### Fast I/O

``````inline ll read()
{
int x = 0, f = 0;
char ch = getchar();
while (!isdigit(ch))
f |= (ch == '-'), ch = getchar();
while (isdigit(ch))
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? -x : x;
}

void write(ll x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + 48);
}

``````

### 卡常小技巧

① 位运算乘除

\$ x=xtimes2^n 可以转化成 x<<n \$

\$ x=x÷2^n 可以转化成 x>>n \$

② for 卡常

``````for (register int i(1); i <= n; ++i)
``````

③ 短函数前加 `inline` 卡常

④ 判断奇偶

``````if(a % 2 == 0)  可以转化成  if((a & 1) == 0)
``````

⑤ 取模用 `&`

``````x = 667 % 4;    可以转化成  x = 667 & (4-1);
x = 667 % 32;   可以转化成  x = 667 & (32-1);
``````

⑥ 正负转换用位运算

``````i = -1;       可以转换成  i = ~i + 1;   或   i = (i ^ -1) + 1;
``````

⑦ 取绝对值

``````k = abs(x);   可以转换成  k = (x ^ (x >> 31))-(x >> 31);
``````

## 数据结构

### ST表

``````ll f[100001][20], lg[100001];
ll n, m, a[100001];

void pre()
{
lg[0] = -1;
for (int i = 1; i <= n; ++i)
lg[i] = lg[i >> 1] + 1;
}

void ST_make()
{
for (int i = 1; i <= n; ++i)
f[i][0] = a[i];
for (int j = 1; j < 22; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

ll ST_check(ll l, ll r)
{
ll k = lg[r - l + 1];
return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main()
{
for (int i = 1; i <= n; ++i)
pre();
ST_make();
for (int i = 1; i <= m; ++i)
{
printf("%lldn", ST_check(l, r));
}
return 0;
}
``````

### 单调队列

``````ll n, k, cnt = 0;
ll ans[2][1000005];

struct node
{
ll sum, id;
};

deque<node> maxq;
deque<node> minq;

int main()
{
node t;
for (int i = 1; i <= n; ++i)
{
t.id = i;
t.sum = x;
while (!minq.empty() && x <= minq.back().sum)
minq.pop_back();
while (!maxq.empty() && x >= maxq.back().sum)
maxq.pop_back();
minq.push_back(t);
maxq.push_back(t);
while (i - k >= minq.front().id)
minq.pop_front();
while (i - k >= maxq.front().id)
maxq.pop_front();
if (i >= k)
{
ans[0][++cnt] = minq.front().sum;
ans[1][cnt] = maxq.front().sum;
}
}
for (int i = 1; i <= n - k + 1; ++i)
printf("%lld ", ans[0][i]);
puts("");
for (int i = 1; i <= n - k + 1; ++i)
printf("%lld ", ans[1][i]);
}
``````

``````const ll maxn = 5000005;
#define INF 9223372036854775800

ll sum[maxn], q[maxn];
ll n, m;

int main()
{
for (int i = 1; i <= n; ++i)
{
sum[i] = sum[i - 1] + x;
}

ll h = 1, t = 1, ans = -INF;
q[1] = 0;
for (int i = 1; i <= n; ++i)
{
while (h <= t && q[h] < i - m)
h++;
ans = max(ans, sum[i] - sum[q[h]]);
while (h <= t && sum[i] <= sum[q[t]])
t--;
q[++t] = i;
}
printf("%lldn", ans);
Edison Ba;
}
``````

### 树状数组

``````ll lowbit(ll x)
{
return x & (-x);
}

ll c[500002], n, m;

void add(ll x, ll y) //单点修改
{
for (; x <= n; x += lowbit(x))
c[x] += y;
}

ll sum(ll x) //前缀和
{
ll ans = 0;
for (; x; x -= lowbit(x))
ans += c[x];
return ans;
}

ll ask(ll l, ll r) //区间查询
{
return sum(r) - sum(l - 1);
}

int main()
{
for (int i = 1; i <= n; ++i) //初始化
{
}
for (int i = 1; i <= m; ++i)
{
if (opt == 1) //单点修改
{
}
else if (opt == 2) //区间查询
{
ll x, y;
printf("%lldn", ans);
}
}
return 0;
}
``````

### 线段树

P3373 【模板】线段树 2

``````ll n, m, mod;

struct node{
ll L, R, add, mul, sum;
node *lc, *rc;
{
sum = (sum + k * (R - L + 1)) % mod;
}
void makemul(ll k)
{
sum = (sum * k) % mod;
mul = (mul * k) % mod;
}
void pushup()
{
sum = (lc->sum + rc->sum) % mod;
}
void pushdown()
{
if(mul != 1)
{
lc->makemul(mul);
rc->makemul(mul);
mul = 1;
}
{
}
}
};

const ll N = 1e5 + 4;
ll a[N];

void Build(node *now, ll l, ll r)
{
now->L = l;
now->R = r;
now->mul = 1;
now->sum = 0;
if(l < r)
{
ll mid = (l + r) >> 1;
now->lc = new node;
now->rc = new node;
Build(now->lc, l, mid);
Build(now->rc, mid + 1, r);
now->pushup();
}
else
{
now->sum = a[l];
now->lc = now->rc = NULL;
}
}

ll check(node *now, ll l, ll r)
{
if(l <= now->L and now->R <= r)
return now->sum % mod;
now->pushdown();
ll mid = (now->L + now->R) >> 1;
ll ans = 0;
if(l <= mid)
ans = (ans + check(now->lc, l, r)) % mod;
if(mid < r)
ans = (ans + check(now->rc, l , r)) % mod;
return ans % mod;
}

void add(node *now, ll l, ll r, ll k)
{
if(l <= now->L and now->R <= r)
else
{
now->pushdown();
ll mid = (now->L + now->R) >> 1;
if(l <= mid)
if(mid < r)
now->pushup();
}
}

void mul(node *now, ll l, ll r, ll k)
{
if(l <= now->L and now->R <= r)
now->makemul(k);
else
{
now->pushdown();
ll mid = (now->L + now->R) >> 1;
if(l <= mid)
mul(now->lc, l, r, k);
if(mid < r)
mul(now->rc, l, r, k);
now->pushup();
}
}

int main()
{
for(int i = 1; i <= n; ++i)
node *root;
root = new node;
Build(root, 1, n);
for(int i = 1; i <= m; ++i)
{
if(opt == 1)
{
mul(root, l, r, k);
}
if(opt == 2)
{
}
if(opt == 3)
{
printf("%lldn", check(root, l, r) % mod);
}
}
return 0;
}
``````

### 树链剖分

(n) 个点， (m) 个操作数， 根结点为 (R)， 取模数为 (mod)

1. (x) 点的点权增加（或修改）(y)
2. 将树从 (x)(y) 结点最短路径上所有节点的值都加上 (z)
3. 询问某个节点 (x)(y) 节点的路径中所有点的点权和 (或maxn)。
4. (x) 为根结点的子树中所有点的点权都增加 (y)
5. 求以 (x) 为根节点的子树内所有节点值之和
``````const ll N = 3e5 + 4;
ll n, m, tot, R, mod;
ll head[N], fa[N], son[N], siz[N], top[N], dep[N], seg[N], rev[N], a[N], lim[N];

struct nodee
{
ll to, nxt;
} t[2 * N];

{
t[++tot].to = y;
}

void dfs1(ll u, ll father)
{
siz[u] = 1, fa[u] = father, dep[u] = dep[father] + 1;
for (ll i = head[u]; i; i = t[i].nxt)
{
ll y = t[i].to;
if (siz[y] == 0)
{
dfs1(y, u);
siz[u] += siz[y];
if (siz[y] > siz[son[u]])
{
son[u] = y;
}
}
}
}

void dfs2(ll u)
{
seg[u] = ++seg[0];
rev[seg[0]] = u;
if (son[u])
{
top[son[u]] = top[u];
dfs2(son[u]);
}
for (ll i = head[u]; i; i = t[i].nxt)
{
ll y = t[i].to;
if (y == son[u] || fa[u] == y)
{
continue;
}
dfs2(y);
}
lim[u] = seg[0];
}

struct node
{
ll L, R, sum, tag, maxn;
node *lc, *rc;
};

void pushup(node *now)
{
now->sum = (now->lc->sum + now->rc->sum) % mod;
now->maxn = max(now->lc->maxn, now->rc->maxn);
}

inline void maketag(node *now, ll w)
{
now->tag = (now->tag + w) % mod;
now->sum = (now->sum + (now->R - now->L + 1) * w) % mod;
now->maxn = w;
}

inline void pushdown(node *now)
{
if (now->tag == 0)
return;
maketag(now->lc, now->tag);
maketag(now->rc, now->tag);
now->tag = 0;
}

void build(node *now, ll l, ll r)
{
now->L = l;
now->R = r;
now->tag = 0;
if (l < r)
{
ll mid = (l + r) >> 1;
now->lc = new node;
now->rc = new node;
build(now->lc, l, mid);
build(now->rc, mid + 1, r);
pushup(now);
}
else
{
now->maxn = a[rev[l]];
now->sum = a[rev[l]];
now->lc = now->rc = NULL;
}
}

void change(node *now, ll l, ll r, ll w)
{
if (l <= now->L and now->R <= r)
{
maketag(now, w);
}
else if (!((now->L > r) || (now->R < l)))
{
pushdown(now);
change(now->lc, l, r, w);
change(now->rc, l, r, w);
pushup(now);
}
}

ll check1(node *now, ll l, ll r)
{
if (l <= now->L and now->R <= r)
return now->sum;
if ((now->L > r) || (now->R < l))
return 0;
pushdown(now);
return (check1(now->lc, l, r) + check1(now->rc, l, r)) % mod;
}

ll check2(node *now, ll l, ll r)
{
if (l <= now->L and now->R <= r)
return now->maxn;
if ((now->L > r) || (now->R < l))
return -INF;
pushdown(now);
return max(check2(now->lc, l, r), check2(now->rc, l, r));
}

int main()
{
R = 1, mod = INF; // R为根结点序号

for (ll i = 1; i <= n; i++)
top[i] = i;

for (ll i = 1; i <= n; i++)

for (ll i = 1; i <= n - 1; i++)
{
}

dfs1(R, 0);
dfs2(R);

node *root;
root = new node;
build(root, 1, n);

for (int i = 1; i <= m; ++i)
{

// 把 x 点的点权增加 y
// 如果想要修改，更改上面的 maketag
if (opt == 0)
{
change(root, seg[x], seg[x], y);
}

// 表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。
else if (opt == 1)
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
swap(x, y);
change(root, seg[top[x]], seg[x], z);
x = fa[top[x]];
}
if(seg[x] > seg[y]) swap(x, y);
change(root, seg[x], seg[y], z);
}

// 询问某个节点 x 到 y 节点的路径中所有点的点权和 (或maxn)
else if (opt == 2)
{
ll sum = 0;
// ll maxn = -2147483647;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
swap(x, y);
sum = (sum + check1(root, seg[top[x]], seg[x])) % mod;
// maxn = max(maxn, check2(root, seg[top[x]], seg[x]));
x = fa[top[x]];
}
if (seg[x] > seg[y])
swap(x, y);
sum = (sum + check1(root, seg[x], seg[y])) % mod;
// maxn = max(maxn, check2(root, seg[x], seg[y]));
printf("%lldn", sum);
}

// 把 x 为根结点的子树中所有点的点权都增加 y
else if (opt == 3)
{
change(root, seg[x], lim[x], y);
}

// 求以 x 为根节点的子树内所有节点值之和
else if (opt == 4)
{
ll ans = check1(root, seg[x], lim[x]) % mod;
printf("%lldn", ans);
}
}
return 0;
}
``````

### 平衡树

#### FHQ-Treap

##### 普通平衡树

1. 插入 (x)
2. 删除 (x) 数(若有多个相同的数，因只删除一个)
3. 查询 (x) 数的排名(排名定义为比当前数小的数的个数 (+1) )
4. 查询排名为 (x) 的数
5. (x) 的前驱(前驱定义为小于 (x)，且最大的数)
6. (x) 的后继(后继定义为大于 (x)，且最小的数)

``````
ll n;

struct node{
ll size, w, ran;
node *lc, *rc;
node(int x)
{
size = 1, w = x, ran = rand();
lc = rc = NULL;
}
} *root = NULL;

void pushup(node *now)
{
now->size = 1;
if(now->lc != NULL) now->size += now->lc->size;
if(now->rc != NULL) now->size += now->rc->size;
}

void split(node *now , ll k, node *&x, node *&y)
{
if(now == NULL)
{
x = y = NULL;
return ;
}
if(k < now->w)
y = now, split(now->lc, k, x, now->lc);
else
x = now, split(now->rc, k ,now->rc, y);
pushup(now);
}

node *merge(node *x, node *y)
{
if(x == NULL || y == NULL)
return x == NULL ? y : x;
if(x->ran < y->ran)
{
x->rc = merge(x->rc, y);
pushup(x);
return x;
}
else
{
y->lc = merge(x, y->lc);
pushup(y);
return y;
}
}

void Insert(ll k)
{
node *x, *y, *now = new node(k);
split(root, k, x, y);
root = merge(merge(x, now), y);
}

void Del(ll k)
{
node *x, *y, *z;
split(root, k, x, z);
split(x, k - 1, x, y);
y = merge(y->lc, y->rc);
root = merge(merge(x, y), z);
}

ll Ran(ll k)
{
ll ans = 0;
node *x, *y;
split(root, k - 1, x, y);
ans = (x == NULL ? 0 : x->size) + 1;
root = merge(x, y);
return ans;
}

ll Kth(ll k)
{
node *now = root;
ll lsize;
while(1)
{
lsize = (now->lc == NULL ? 0 : now->lc->size);
if(lsize + 1 == k) break;
else if(k <= lsize) now = now->lc;
else
{
k -= lsize + 1;
now = now->rc;
}
}
return now->w;
}

int main()
{
for(int i = 1; i <= n; ++i)
{
if(opt == 1) Insert(x);
if(opt == 2) Del(x);
if(opt == 3) printf("%lldn", Ran(x));
if(opt == 4) printf("%lldn", Kth(x));
if(opt == 5) printf("%lldn", Kth(Ran(x) - 1));
if(opt == 6) printf("%lldn", Kth(Ran(x + 1)));
}
return 0;
}
``````
##### 文艺平衡树
``````
const ll N = 1e6 + 3;
ll n, m, a[N];

struct node
{
node *lc, *rc;
node(int x)
{
size = 1, w = x, ran = rand(), add = 0;
lc = rc = NULL;
}
} *root = NULL;

void pushdown(node *now)
{
swap(now->lc, now->rc);
if (now->lc != NULL)
if (now->rc != NULL)
}

void pushup(node *now)
{
now->size = 1;
if (now->lc != NULL)
now->size += now->lc->size;
if (now->rc != NULL)
now->size += now->rc->size;
}

void split(node *now, ll k, node *&x, node *&y)
{
if (now == NULL)
{
x = y = NULL;
return;
}
pushdown(now);
ll ls = (now->lc == NULL) ? 1 : now->lc->size + 1;
if (k < ls)
y = now, split(now->lc, k, x, now->lc);
else
x = now, split(now->rc, k - ls, now->rc, y);
pushup(now);
}

node *merge(node *x, node *y)
{
if (x == NULL || y == NULL)
return x == NULL ? y : x;
if (x->ran < y->ran)
{
pushdown(x);
x->rc = merge(x->rc, y);
pushup(x);
return x;
}
else
{
y->lc = merge(x, y->lc);
pushup(y);
return y;
}
}

node *Build(ll l, ll r)
{
node *now;
if (l == r)
return now = new node(a[l]);
ll mid = (l + r) >> 1;
return merge(Build(l, mid), Build(mid + 1, r));
}

void Insert()
{
for (int i = 1; i <= n; ++i)
a[i] = i;
root = Build(1, n);
}

void Reverse(ll l, ll r)
{
node *x, *y, *z;
split(root, r, x, z);
split(x, l - 1, x, y);
root = merge(merge(x, y), z);
}

void Print(node *now)
{
if(now->lc) Print(now->lc);
printf("%lld ", now->w);
if(now->rc) Print(now->rc);
}

int main()
{
Insert();
for (int i = 1; i <= m; ++i)
{
Reverse(l, r);
}
Print(root);
return 0;
}
``````

#### Treap

``````const ll maxn = 1e5 + 10;
const ll inf = 1e14 + 10;
ll n, tot, root;

struct node
{
ll l, r;
ll v, rk;
ll cnt, si
} s[maxn << 1];

inline ll New(ll w)
{
s[++tot].v = w;
s[tot].rk = rand();
s[tot].cnt = s[tot].siz = 1;
}

inline void upd(ll p)
{
s[p].siz = s[s[p].l].siz + s[s[p].r].siz + s[p].cnt;
}

inline void build()
{
New(-inf), New(inf);
root = 1;
s[1].r = 2;
upd(root);
return;
}

inline void zig(ll &p)
{
ll q = s[p].l;
s[p].l = s[q].r, s[q].r = p;
p = q;
upd(s[p].r);
upd(p);
}

inline void zag(ll &p)
{
ll q = s[p].r;
s[p].r = s[q].l, s[q].l = p;
p = q;
upd(s[p].l);
upd(p);
}

inline void add(ll &p, ll x)
{
if (p == 0)
{
p = New(x);
return;
}
if (s[p].v == x)
{
s[p].cnt++;
upd(p);
return;
}
if (s[p].v < x)
{
if (s[p].rk < s[s[p].r].rk)
zag(p);
}
if (s[p].v > x)
{
if (s[p].rk < s[s[p].l].rk)
zig(p);
}

upd(p);
}

inline void delt(ll &p, ll x)
{
if (p == 0)
return;
if (s[p].v == x)
{
if (s[p].cnt > 1)
{
s[p].cnt--;
upd(p);
return;
}
if (s[p].l || s[p].r)
{
if (s[p].r == 0 || s[s[p].l].rk > s[s[p].r].rk)
{
zig(p);
delt(s[p].r, x);
}
else
{
zag(p);
delt(s[p].l, x);
}
upd(p);
}
else
p = 0;
return;
}
if (s[p].v < x)
{
delt(s[p].r, x);
upd(p);
return;
}
if (s[p].v > x)
{
delt(s[p].l, x);
upd(p);
return;
}
}

inline ll getrank(ll p, ll x)
{
if (p == 0)
return 0;
if (s[p].v == x)
{
return s[s[p].l].siz + 1;
}
if (s[p].v > x)
{
return getrank(s[p].l, x);
}
else
{
return getrank(s[p].r, x) + s[s[p].l].siz + s[p].cnt;
}
}

inline ll getval(ll p, ll x)
{
if (p == 0)
return inf;
if (s[s[p].l].siz >= x)
{
return getval(s[p].l, x);
}
if (s[s[p].l].siz + s[p].cnt >= x)
{
return s[p].v;
}
else
{
return getval(s[p].r, x - s[s[p].l].siz - s[p].cnt);
}
}

inline ll getpre(ll x)
{
ll ans = 1;
ll p = root;
while (p)
{
if (x == s[p].v)
{
if (s[p].l)
{
p = s[p].l;
while (s[p].r)
p = s[p].r;
ans = p;
}
break;
}
if (s[p].v < x && s[p].v > s[ans].v)
ans = p;
if (x < s[p].v)
p = s[p].l;
else
p = s[p].r;
}
return s[ans].v;
}

inline ll getnxt(ll x)
{
ll ans = 2;
ll p = root;
while (p)
{
if (x == s[p].v)
{
if (s[p].r)
{
p = s[p].r;
while (s[p].l)
p = s[p].l;
ans = p;
}
break;
}
if (s[p].v > x && s[p].v < s[ans].v)
ans = p;
if (x < s[p].v)
p = s[p].l;
else
p = s[p].r;
}
return s[ans].v;
}

int main()
{
build();
for (int i = 1; i <= n; i++)
{
if (op == 1)
if (op == 2)
delt(root, x);
if (op == 3)
printf("%lldn", getrank(root, x) - 1);
if (op == 4)
printf("%lldn", getval(root, x + 1));
if (op == 5)
printf("%lldn", getpre(x));
if (op == 6)
printf("%lldn", getnxt(x));
}
return 0;
}
``````

#### Splay

``````struct node
{
ll cnt, val, size;
node *son[2], *fa;
};

node *root, *null;

inline void C(node *&now)
{
now->son[0] = now->son[1] = now->fa = null;
now->val = now->cnt = now->size = 0;
}

inline bool getwhich(node *now)
{
return now->fa->son[1] == now;
}

inline void rotate(node *now)
{
node *fa = now->fa;
node *gfa = fa->fa;
ll idson = getwhich(now);
gfa->son[getwhich(fa)] = now;
now->fa = gfa;
fa->son[idson] = now->son[idson ^ 1];
now->son[idson ^ 1]->fa = fa;
now->son[idson ^ 1] = fa;
fa->fa = now;
fa->size = fa->son[0]->size + fa->son[1]->size + fa->cnt;
now->size = now->son[0]->size + now->son[1]->size + now->cnt;
}

inline void Splay(node *now, node *f)
{
while (now->fa != f)
{
node *fa = now->fa;
node *gfa = fa->fa;
if (gfa != f)
getwhich(now) ^ getwhich(fa) ? rotate(now) : rotate(fa);
rotate(now);
}
if (f == null)
root = now;
}

inline void insert(ll x)
{
node *now = root, *fa = null;
while (now != null and now->val != x)
{
fa = now;
now = now->son[x > now->val];
}
if (now != null)
++now->cnt;
else
{
node *p = new node;
if (fa != null)
fa->son[x > fa->val] = p;
p->fa = fa;
p->val = x;
p->size = p->cnt = 1;
p->son[0] = p->son[1] = null;
Splay(p, null);
return;
}
Splay(now, null);
}

void search(ll x)
{
node *now = root;
if (now == null)
return;
while (now->son[x > now->val] != null and x != now->val)
now = now->son[x > now->val];
Splay(now, null);
}

node *getpre(ll x)
{
search(x);
node *now = root->son[0];
while (now->son[1] != null)
now = now->son[1];
return now;
}

node *getback(ll x)
{
search(x);
node *now = root->son[1];
while (now->son[0] != null)
now = now->son[0];
return now;
}

ll getnum(ll x)
{
node *now = root;
while (1)
{
if (x <= now->son[0]->size)
now = now->son[0];
else
{
x -= (now->son[0]->size + now->cnt);
if (x <= 0)
return now->val;
else
now = now->son[1];
}
}
}

void _delete(ll x)
{
node *pre = getpre(x), *back = getback(x);
Splay(pre, null);
Splay(back, pre);
if (back->son[0]->cnt > 1)
{
--back->son[0]->cnt;
Splay(back->son[0], null);
}
else
{
back->son[0] = null;
C(back->son[0]);
}
}

int main()
{
null = new node;
null->size = null->cnt = null->val = 0;
null->son[0] = null->son[1] = null->fa = NULL;
root = null;
insert(-INF);
insert(INF);
for (int i = 1; i <= n; ++i)
{
if (opt == 1)
{
insert(x);
}
else if (opt == 2)
{
_delete(x);
}
else if (opt == 3)
{
search(x);
printf("%lldn", root->son[0]->size);
}
else if (opt == 4)
{
printf("%lldn", getnum(x + 1));
}
else if (opt == 5)
{
insert(x);
printf("%lldn", getpre(x)->val);
_delete(x);
}
else
{
insert(x);
printf("%lldn", getback(x)->val);
_delete(x);
}
}
return 0;
}
``````

### 可持久化数组

P3919 【模板】可持久化线段树 1（可持久化数组）

1. 在某个历史版本上修改某一个位置上的值

2. 访问某个历史版本上的某一位置的值

1. 对于操作1，格式为 (v_i ~1 ~loc_i~ value_i)，即为在版本 (v_i) ​的基础上，将 (a_{{loc}_i}) 修改为 ({value}_i)

2. 对于操作2，格式为 (v_i 2 {loc}_i)​，即访问版本 (v_i) ​中的 (a_{{loc}_i}) ​​的值，生成一样版本的对象应为 (v_i)

``````const ll N = 1e6 + 3;
int n, m, tot, a[N];

struct node
{
int L, R, w;
node *lc, *rc;
};

struct node by[N * 21], *pool = by, *root[N];

node *New()
{
return ++pool;
}

node *build(int l, int r)
{
node *now = New();
now->L = l;
now->R = r;
if (l < r)
{
ll mid = (now->L + now->R) >> 1;
now->lc = build(l, mid);
now->rc = build(mid + 1, r);
}
else
{
now->w = a[l];
now->lc = now->rc = NULL;
}
return now;
}

inline bool out(node *&now, int l, int r)
{
return (now->R < l) || (r < now->L);
}

void change(node *&pre, node *&now, int x, int w)
{
*now = *pre;
if (pre->L == x and pre->R == x)
now->w = w;
else
{
if (!out(pre->lc, x, x))
{
now->lc = New();
change(pre->lc, now->lc, x, w);
}
else
{
now->rc = New();
change(pre->rc, now->rc, x, w);
}
}
}

int check(node *now, int x)
{
if (now->L == x && now->R == x)
return now->w;
if (!out(now->lc, x, x))
return check(now->lc, x);
else
return check(now->rc, x);
}

int main()
{
for (int i = 1; i <= n; ++i)
{
}
root[0] = build(1, n);
for (int i = 0; i < m; ++i)
{
if (opt == 1)
{
root[++tot] = New();
change(root[v], root[tot], x, k);
}
else
{
ll ans = check(root[v], x);
printf("%lldn", ans);
root[++tot] = New();
root[tot] = root[v];
}
}
return 0;
}
``````

### 可持久化线段树

P3834 【模板】可持久化线段树 2（主席树）

``````const ll M = 2e5 + 3;
int n, N, m, tot, a[M], b[M];

struct node
{
int L, R, cnt;
node *lc, *rc;
};

struct node by[M * 21], *pool = by, *root[M];

node *New()
{
return ++pool;
}

void update(node *&now)
{
now->cnt = now->lc->cnt + now->rc->cnt;
}

node *build(int l, int r)
{
node *now = New();
now->L = l;
now->R = r;
if (l < r)
{
int mid = (l + r) >> 1;
now->lc = build(l, mid);
now->rc = build(mid + 1, r);
update(now);
}
else
{
now->cnt = 0;
now->lc = now->rc = NULL;
}
return now;
}

inline bool out(node *&now, int l, int r)
{
return (now->R < l) || (r < now->L);
}

void change(node *pre, node *now, int x)
{
*now = *pre;
if (pre->L == x and pre->R == x)
now->cnt++;
else
{
if (!out(pre->lc, x, x))
{
now->lc = New();
change(pre->lc, now->lc, x);
update(now);
}
else
{
now->rc = New();
change(pre->rc, now->rc, x);
update(now);
}
}
}

int check(node *&nowl, node *&nowr, int k)
{
if (nowl->L == nowl->R)
return nowl->L;
int lcnt = nowr->lc->cnt - nowl->lc->cnt;
if (lcnt >= k)
return check(nowl->lc, nowr->lc, k);
else
return check(nowl->rc, nowr->rc, k - lcnt);
}

void Main()
{
for (int i = 1; i <= n; ++i)
{
b[i] = a[i];
}
sort(b + 1, b + n + 1);
N = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i)
a[i] = lower_bound(b + 1, b + N + 1, a[i]) - b;
root[0] = build(1, N);
for (int i = 1; i <= n; ++i)
{
root[++tot] = New();
change(root[tot - 1], root[tot], a[i]);
}
for (int i = 1; i <= m; ++i)
{
int l, r, k;
int ans = b[check(root[l - 1], root[r], k)];
printf("%dn", ans);
}
}
``````

### 左偏树

1. `1 x y`:将第 (x) 个数和第 (y) 个数所在的小根堆合并（若第 (x) 或第 (y) 个数已经被删除或第 (x) 和第 (y) 个数在用一个堆内，则无视此操作）。
2. `2 x`：输出第 (x) 个数所在的堆最小数，并将这个最小数删除（若有多个最小数，优先删除先输入的；若第 (x) 个数已经被删除，则输出 (-1) 并无视删除操作）。

``````#define M 150010
#define swap my_swap
#define ls S[x].Son[0]
#define rs S[x].Son[1]

struct Tree
{
ll dis, val, Son[2], rt;
} S[M];
ll N, T, A, B, C, i;

inline ll Merge(ll x, ll y);
ll my_swap(ll &x, ll &y) { x ^= y ^= x ^= y; }
inline ll Get(ll x) { return S[x].rt == x ? x : S[x].rt = Get(S[x].rt); }
inline void Pop(ll x) { S[x].val = -1, S[ls].rt = ls, S[rs].rt = rs, S[x].rt = Merge(ls, rs); }
inline ll Merge(ll x, ll y)
{
if (!x || !y)
return x + y;
if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y))
swap(x, y);
rs = Merge(rs, y);
if (S[ls].dis < S[rs].dis)
swap(ls, rs);
S[ls].rt = S[rs].rt = S[x].rt = x, S[x].dis = S[rs].dis + 1;
return x;
}
int main()
{
S[0].dis = -1;
for (i = 1; i <= N; ++i)
S[i].rt = i, S[i].val = read();
for (i = 1; i <= T; ++i)
{
if (A == 1)
{
if (S[B].val == -1 || S[C].val == -1)
continue;
ll f1 = Get(B), f2 = Get(C);
if (f1 != f2)
S[f1].rt = S[f2].rt = Merge(f1, f2);
}
else
{
if (S[B].val == -1)
puts("-1");
else
printf("%lldn", S[Get(B)].val), Pop(Get(B));
}
}
return 0;
}
``````

### 珂朵莉树

(n) 个数，(m) 次操作 ((n,m≤105))

• 区间加
• 区间赋值
• 区间第k小
• 求区间幂次和

``````#include <set>
#include <vector>
#define p 1000000007
#define IT set<node>::iterator

/* 初始化 */
struct node
{
ll l, r;
mutable ll w; //可变的
node(ll L, ll R = -1, ll W = 0)
{
l = L;
r = R;
w = W;
}
bool operator<(const node &o) const
{
return l < o.l;
}
};

ll n, m, seed, vmax, a[100005];
set<node> s;

ll rnd() /* 对于本题的数据生成器 */
{
ll ans = seed;
seed = (seed * 7 + 13) % p;
return ans;
}

ll ksm(){}

IT split(ll pos) /* 分裂 */
{
IT it = s.lower_bound(node(pos));
if (it != s.end() && it->l == pos)
return it;
--it;
ll L = it->l, R = it->r;
ll W = it->w;
s.erase(it);
s.insert(node(L, pos - 1, W));
return s.insert(node(pos, R, W)).first;
}

void assign(ll l, ll r, ll w = 0) /* 推平 */
{
IT itl = split(l), itr = split(r + 1);
s.erase(itl, itr);
s.insert(node(l, r, w));
}

void add(ll l, ll r, ll w = 1) /* 暴力区间加 */
{
IT itl = split(l), itr = split(r + 1);
for (; itl != itr; ++itl)
itl->w += w;
}

ll rnk(ll l, ll r, ll k) /* 暴力区间第 k 小 */
{
vector<pair<ll, int>> vp;
IT itl = split(l), itr = split(r + 1);
vp.clear();
for (; itl != itr; ++itl)
vp.push_back(pair<ll, int>(itl->w, itl->r - itl->l + 1));
std::sort(vp.begin(), vp.end());
for (vector<pair<ll, int>>::iterator it = vp.begin(); it != vp.end(); ++it)
{
k -= it->second;
if (k <= 0)
return it->first;
}
return -1LL;
}

ll sum(ll l, ll r, ll ex, ll mod) /* 暴力求和 */
{
IT itl = split(l), itr = split(r + 1);
ll res = 0;
for (; itl != itr; ++itl)
res = (res + (ll)(itl->r - itl->l + 1) * ksm(itl->w, ex, mod)) % mod;
return res;
}

int main()
{
for (int i = 1; i <= n; ++i)
{
a[i] = (rnd() % vmax) + 1;
s.insert(node(i, i, a[i]));
}
s.insert(node(n + 1, n + 1, 0));

for (int i = 1; i <= m; ++i)
{
ll op = 1LL * (rnd() % 4) + 1;
ll l = 1LL * (rnd() % n) + 1;
ll r = 1LL * (rnd() % n) + 1;
if (l > r)
swap(l, r);
ll x, y;
if (op == 3)
x = 1LL * (rnd() % (r - l + 1)) + 1;
else
x = 1LL * (rnd() % vmax) + 1;
if (op == 4)
y = 1LL * (rnd() % vmax) + 1;
if (op == 1)
else if (op == 2)
assign(l, r, x);
else if (op == 3)
printf("%lldn", rnk(l, r, x));
else
printf("%lldn", sum(l, r, x, y));
}
return 0;
}
``````

## 数学

### 线性筛素数

``````int v[maxn], prime[maxn], n, k, t, m;
void primes(int n)
{
memset(v, 0, sizeof(v)); //清空标记数组
m = 0;                   //质数个数
for (int i = 2; i <= n; i++)
{
if (!v[i])                    //未被标记，i为质数
v[i] = i, prime[++m] = i; //记录
for (int j = 1; j <= m; j++)
{
if (prime[j] > v[i] || prime[j] > n / i)
break;                  //i有更小的质因子，或者超出n的范围
v[i * prime[j]] = prime[j]; //prime[j]为合数 i*prime[j]的最小质因子
}
}
}
int main()
{
scanf("%d", &n);
primes(n);
for (int i = 1; i <= m; ++i)
printf("%dn", prime[i]);
}
``````

### 最大公约数

① 标准

``````inline int gcd(int a, int b)
{
int r;
while (b > 0)
{
r = a % b;
a = b;
b = r;
}
return a;
}
``````

② 位运算

``````inline int gcd(int a, int b) //a，b不能为0
{
while (b ^= a ^= b ^= a %= b)
;
return a;
}
``````

③ 辗转相除法

``````inline int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
``````

④ 三目

``````inline int gcd(int a, int b)
{
return b > 0 ? gcd(b, a % b) : a;
}
``````

⑤ 外挂（考试禁止）

``````#include <algorithm>
inline int gcd(int a, int b)
{
return __gcd(a, b); //其实可以在主函数里直接用这个
}
``````

### 线性求逆元

``````inv[0] = inv[1] = 1;
for (register int i(2); i <= n; i++)
inv[i] = (1ll * (mod - mod / i) * inv[mod % i]) % mod;
``````

### 线性求欧拉函数

``````int prime[N], phi[N];
bool isprime[N];

void pre()
{
ll cnt = 0;
isprime[1] = 1;
phi[1] = 1;
for (register int i(2); i <= n; ++i)
{
if (!isprime[i])
{
prime[++cnt] = i;
phi[i] = i - 1;
}
for (register int j(1); j <= cnt and i * prime[j] <= n; ++j)
{
isprime[i * prime[j]] = 1;
if (i % prime[j])
phi[i * prime[j]] = phi[i] * phi[prime[j]];
else
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
}
``````

## 分治

### 快速乘法取余

``````inline int mult_mod(int a, int n, int mod)
{
int ans = 0;
while (n > 0)
{
if (n & 1)
ans = (ans + a) % mod;
a = (a + a) % mod;
n >>= 1;
}
return ans;
}
``````

### 快速幂

``````ll ksm(ll a, ll b, ll mod)
{
ll ret = 1 % mod;
while(b)
{
if(b & 1)
ret = ret * a % mod;
b >>= 1;
a = a * a % mod;
}
return ret;
}
``````

### LIS

``````ll f[maxn], ans = 1; //注意答案个数初始化为1

int main()
{
for (int i = 1; i <= n; ++i)
{
if (i == 1)
{
f[1] = x;
continue;
}
int l = 1, r = ans, mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (x <= f[mid])
r = mid - 1;
else
l = mid + 1;
}
f[l] = x;
if (l > ans)
++ans;
}
printf("%lldn", ans);
return 0;
}

``````

### lower_bound

#### ①数组内

``````//查找范围：[ begin , end ) ，左闭右开区间。
*lower_bound(begin, end, num);        //返回第一个 >= num 的数的数值
lower_bound(begin, end, num) - begin; // 返回下标

int a[100] = {0, 1, 3, 5, 7, 9, 10};
//       下标：0  1  2  3  4  5  6
int main()
{
int x = lower_bound(a + 1, a + 6 + 1, 6) - a; //输出下标
int y = *lower_bound(a + 1, a + 6 + 1, 6);    //输出值
printf("%d %d", x, y);
return 0;
}

``````

#### ②结构体内

``````struct node //开结构体
{
int a, id; //定义结构体内的两个变量
node() {}
node(int x, int y) : a(x), id(y) {}
bool operator<(const node t) const //重载
{
return a < t.a;
}
} t[1001];

bool cmp(node x, node y) //快排 cmp 比较函数
{
if (x.a < y.a)
return 1; //结构体内按 a 由小到大排序。
return 0;
}

int main()
{
for (int i = 1; i <= n; ++i)
{
t[i].id = i;
}
sort(t + 1, t + n + 1, cmp); //按小到大排序

int x, xiabiao, ans;
xiabiao = lower_bound(t + 1, t + n + 1, node(x, 0)) - t; //这样求下标
ans = (*lower_bound(t + 1, t + n + 1, node(x, 0))).a;    //这样求值
printf("%d %dn", xiabiao, ans);
return 0;
}

5
20 40 30 10 50
35

4 40
``````

## 动态规划

### 基础模型

#### 数字金字塔

``````f[i][j] = max((f[i][j] + f[i + 1][j]), (f[i][j] + f[i][j + 1]));
``````

#### LCS

``````string s, t;
int f[maxn][maxn];

int main()
{
cin >> s >> t;
int ls = s.length(), lt = t.length();
for (int i = 1; i <= ls; i++)
for (int j = 1; j <= lt; j++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (s[i - 1] == t[j - 1])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[ls][lt] << endl;
return 0;
}
``````

#### LCIS

CF10D

``````const int maxn = 1005;
ll n, m, a[maxn], b[maxn], ans;
ll f[maxn][maxn], lcis[maxn][maxn];

int main()
{
for (int i = 1; i <= n; ++i)
for (int i = 1; i <= m; ++i)

for (int i = 1; i <= n; ++i)
{
for (int j = 1, k = 0; j <= m; ++j)
{
if (a[i] == b[j])
{
f[i][j] = f[i - 1][k] + 1;
for (int p = 1; p <= f[i - 1][k]; ++p)
lcis[j][p] = lcis[k][p];
lcis[j][f[i][j]] = a[i];
}
else
f[i][j] = f[i - 1][j];
if (b[j] < a[i] && f[i][j] > f[i][k])
k = j;
}
}

for (int i = 1; i <= m; ++i)
if (f[n][i] > f[n][ans])
ans = i;

printf("%lldn", f[n][ans]);
for (int p = 1; p <= f[n][ans]; ++p)
printf("%lld ", lcis[ans][p]);
puts("");
return 0;
}
``````

### 基础背包

#### 01背包

``````ll V, n, w[10000], c[10000], f[10000];

int main()
{
for (int i = 1; i <= n; ++i)
{
}
for (int i = 1; i <= n; ++i)
for (int v = V; v >= w[i]; --v)
{
if (f[v - w[i]] + c[i] > f[v])
f[v] = f[v - w[i]] + c[i];
}
printf("%lldn", f[V]);
return 0;
}
``````

#### 01-方案数

``````ll a[21], f[1003], n, t;
int main()
{
for (int i = 1; i <= n; ++i)
{
}
f[0] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = t; j >= a[i]; --j)
{
f[j] += f[j - a[i]];
}
}
printf("%lldn", f[t]);
return 0;
}
``````

#### 完全背包

``````for (int i = 1; i <= n; ++i)
for (int v = w[i]; v <= V; ++v)
{
if (f[v - w[i]] + c[i] > f[v])
f[v] = f[v - w[i]] + c[i];
}
``````

#### 完全-方案数

``````ll a[5], f[10002], m;

int main()
{
a[1] = 10, a[2] = 20, a[3] = 50, a[4] = 100;
f[0] = 1;
for (int i = 1; i <= 4; ++i)
{
for (int j = a[i]; j <= m; ++j)
{
f[j] += f[j - a[i]];
}
}
printf("%lldn", f[m]);
return 0;
}
``````

#### 混合背包

``````ll w[31], c[31], p[31];
ll f[201], n, m;

int main()
{
for (int i = 1; i <= n; ++i)
{
}
for (int i = 1; i <= n; ++i)
{
if (p[i] == 0) //完全
{
for (int j = w[i]; j <= m; ++j)
f[j] = max(f[j], f[j - w[i]] + c[i]);
}
else //01和多重
{
for (int j = 1; j <= p[i]; ++j)
{
for (int k = m; k >= w[i]; --k)
{
f[k] = max(f[k], f[k - w[i]] + c[i]);
}
}
}
}
printf("%lldn", f[m]);
return 0;
}
``````

#### 二维费用背包

``````ll v, u, k;
ll a[1091], b[1021], c[1092];
ll f[101][101];

int main()
{
memset(f, 127, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= k; ++i)
{
}
for (int i = 1; i <= k; ++i)
{
for (int j = v; j >= 0; --j)
{
for (int l = u; l >= 0; --l)
{
ll t1 = j + a[i];
ll t2 = l + b[i];
t1 = min(t1, v);
t2 = min(t2, u);
f[t1][t2] = min(f[t1][t2], f[j][l] + c[i]);
}
}
}
printf("%lldn", f[v][u]);
return 0;
}
``````

### 进阶dp

#### 区间dp

`f[i][j]` 中的 (i) 为起点，(j) 为终点进行 dp。

``````
for (int t = 2; t <= n; ++t)
{
for (int i = 1; i <=  n - t + 1; ++i)
{
int j = i + t - 1;
for (int k = i; k < j; ++k)
{
f[i][j] = ();
}
}
}

print()

``````

#### 斜率优化dp

``````ll sum[M], f[M], Q[M];
ll n, L;

ll X(ll j)
{
return sum[j];
}

ll Y(ll j)
{
return f[j] + (sum[j] + L) * (sum[j] + L);
}

long double K(ll j, ll k)
{
return 1.0 * ((Y(j) - Y(k)) / (X(j) - X(k)));
}

int main()
{
for (int i = 1; i <= n; ++i)
{
sum[i] += sum[i - 1];
++sum[i];
}

ll l = 1, r = 1, j;
for (int i = 1; i <= n; ++i)
{
while (l < r && K(Q[l + 1], Q[l]) <= 2 * sum[i])
++l;
j = Q[l];
f[i] = f[j] + (sum[i] - sum[j] - (L + 1)) * (sum[i] - sum[j] - (L + 1));
while (l < r && K(Q[r], Q[r - 1]) >= K(i, Q[r - 1]))
--r;
Q[++r] = i;
}
printf("%lldn", f[n]);
}
``````

## 图论

### 前置

#### 链式前向星存图

``````ll head[maxn];

struct node
{
ll nxt, to, w;
} t[maxn];

void add(const ll u, const ll v, const ll w)
{
t[++tot].to = v;
t[tot].w = w;
}
``````

#### vector 存图

``````struct node{
ll to, w;
};

vector<node> t[maxn];

void add(const int u, const int v, const int w)
{
t[u].push_back((node){v, w});
}
``````

### 图的遍历

`ans` 存储遍历顺序。

#### DFS

``````void dfs(ll s)
{
vis[s] = 1;
ans.push_back(s);
for (int i = 0; i < t[s].size(); ++i)
if (!vis[t[s][i]])
dfs(t[s][i]);
}
``````

#### BFS

``````void bfs(ll s)
{
queue<ll> q;
q.push(s);
vis[s] = 1;
while (!q.empty())
{
ll x = q.front();
ans.push_back(x);
q.pop();
for (ll i = 0; i < t[x].size(); ++i)
{
if (!vis[t[x][i]])
{
q.push(t[x][i]);
vis[t[x][i]] = 1;
}
}
}
}
``````

### Dijkstra 最短路

#### 链式前向星

``````#include <queue>
priority_queue<pair<ll, ll>> q;
void dijkstra(int s)
{
memset(dis, 0x3f, sizeof(dis)); //初始边无限大
memset(vis, 0, sizeof(vis));          //结点初始均为访问
dis[s] = 0;                           //起点到自己距离为0
q.push(make_pair(0, s));              //起点进队
while (!q.empty())
{
x = q.top().second;
q.pop();                          //初始结点入队
if (vis[x])
continue;                     //如果走过，直接跳过
vis[x] = 1;                       //标记已访问
for (ll i = head[x]; i != -1; i = t[i].nxt)
{
ll y = t[i].to, z = t[i].w;
if (dis[y] > dis[x] + z)
{
dis[y] = dis[x] + z;           //更新起点到y最短路
q.push(make_pair(-dis[y], y)); //d[y]相反数入队，转小根堆
}
}
}
}
int main()
{
for (int i = 1; i <= n; ++i)
...
}
//后面省略
``````

#### vector

``````void dj(int s)
{
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof vis);
dis[s] = 0;
q.push(make_pair(0, s));
while (!q.empty())
{
ll x = q.top().second;
q.pop();
if (vis[x])
continue;
vis[x] = 1;
for (int i = 0; i < t[x].size(); ++i)
{
ll y = t[x][i].to, z = t[x][i].w;
if (dis[y] > dis[x] + z)
{
dis[y] = dis[x] + z;
q.push(make_pair(-dis[y], y));
}
}
}
}
``````

### SPFA

SPFA能处理负边权，可以判断负环。也可以求最长路。

#### 最短路

``````#include <queue>
queue<int> q;
void SPFA(int s)
{
fill(dis + 1, dis + 1 + n, 2147483647); //初始边无限大
memset(vis, 0, sizeof vis);
dis[s] = 0;
q.push(s);
while (!q.empty())
{
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = head[x]; i != -1; i = t[i].nxt)
{
int y = t[i].to, z = t[i].w;
if (dis[y] > dis[x] + z)
{
dis[y] = dis[x] + z;
if (vis[y] == 0)
{
q.push(y);
vis[y] = 1;
}
}
}
}
}
``````

#### 最长路

``````1. `dis` 数组赋初值时，如果没有负边权就赋 \$-1\$ ，如果有负边权就赋无限小。
``````
1. `dis[y]>dis[x]+z` 中的 `>` 改成 `<`

#### 判断负环

``````ll cnt[maxn]; //专门记录负环
void SPFA().....if (dis[y] > dis[x] + z)
{
dis[y] = dis[x] + z;
cnt[y]++;
if (cnt[y] >= n + 1) //出现超过n次表示就有负环
{
ans = 1; //ans=1代表有负环。
return;
}
if (vis[y] == 0)
{
q.push(y);
vis[y] = 1;
}
}
``````

### Floyd 全源最短路

``````inline void floyd()
{
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (e[i][j] > e[i][k] + e[k][j])
e[i][j] = e[i][k] + e[k][j];
}
``````

### 并查集

(n) 代表元素个数，(m) 为操作数。

(opt=1) 时，合并集合 (a,b)(opt=2) 时，如果 (a,b) 在同一集合，输出 `Y` 否则输出 `N`

``````int find(int k)
{
if (f[k] == k)
return k;
return f[k] = find(f[k]);
}

int main()
{
for (int i = 1; i <= n; ++i)
f[i] = i; //初始化自己的老大是自己

for (int i = 1; i <= m; ++i)
{
int opt, a, b;
if (opt == 1)
f[find(a)] = find(b);
else
{
if (find(a) == find(b))
printf("Yn");
else
printf("Nn");
}
}
return 0;
}
``````

### LCA

P3379 【模板】最近公共祖先（LCA）

``````struct node{...};

ll dep[500010], fa[500010][25];
ll n, m, s;

ll dep[N], fa[N][23];
void dfs(ll now, ll fath)
{
dep[now] = dep[fath] + 1;
fa[now][0] = fath;
for(int i = 1; i <= 22; ++i)
fa[now][i] = fa[fa[now][i - 1]][i - 1];
for(int i = head[now]; i; i = t[i].nxt)
if(t[i].to != fath)
dfs(t[i].to, now);
}

ll LCA(ll x, ll y)
{
if(dep[x] < dep[y]) swap(x, y);
for(int k = 22; k >= 0; --k)
if(dep[fa[x][k]] >= dep[y])
x = fa[x][k];
if(x == y) return x;
for(int k = 22; k >= 0; --k)
if(fa[x][k] != fa[y][k])
x = fa[x][k], y = fa[y][k];
return fa[x][0];
}

int main()
{
for (int i = 1; i <= n; ++i)
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);

for (int i = 1; i < n; ++i)
{
}

dfs(s, 0);
for (int i = 1; i <= m; ++i)
{
printf("%lldn", LCA(x, y));
}
return 0;
}
``````

### 最小生成树

#### Kruskal

``````const ll N = 2e5 + 3;
ll n, m, fa[N], ans;

struct node{
ll x, y, w;
}t[N];

bool cmp(node a, node b)
{
return a.w < b.w;
}

ll F(ll x)
{
if(fa[x] == x) return x;
return fa[x] = F(fa[x]);
}

int main()
{

for(int i = 1; i <= m; ++i)
sort(t + 1, t + m + 1, cmp);
for(int i = 1; i <= n; ++i)
fa[i] = i;

for(int i = 1; i <= m; ++i)
{
if(F(t[i].x) == F(t[i].y)) continue;
fa[F(t[i].x)] = F(t[i].y);
ans += t[i].w;
}

for(int i = 2; i <= n; ++i)
{
if(F(i) != F(1)) // if Lian Tong
{
puts("orz");
return 0;
}
}

printf("%lldn", ans);
return 0;
}
``````

#### Prim

``````int ans, cnt, now = 1; //Prim
void prim()
{
for (int i = 2; i <= n; ++i)
dis[i] = MAXN;

for (int i = head[1]; i; i = t[i].nxt)
dis[t[i].to] = min(dis[t[i].to], t[i].w);

while (++cnt < n)
{
int minn = MAXN;
vis[now] = 1;
for (int i = 1; i <= n; ++i)
{
if (vis[i])
continue;
if (minn > dis[i])
{
minn = dis[i];
now = i;
}
}

ans += minn;

for (int i = head[now]; i; i = t[i].nxt)
{
int y = t[i].to, z = t[i].w;
if (vis[y])
continue;
if (dis[y] > z)
{
dis[y] = z;
}
}
}
}
``````

### 拓扑排序

``````ll ans[100] ，cnt; //拓扑序列及其元素个数
ll deg[100];       //所有点的入度

void topsort()
{
queue<ll> q;
for (int i = 1; i <= n; ++i)
if (deg[i] == 0) //寻找最开始入度就为0的点
q.push(i);   //入队

while (!q.empty())
{
ll x = q.front();
q.pop();
ans[++cnt] = x; //把队首的元素放进拓扑序列
for (int i = head[x]; i; i = t[i].nxt)
{
ll y = t[i].to;    //寻找邻边
if (--deg[y] == 0) //邻边的入度-1，并且判断减后的入度是否为0
q.push(y);     //如果为0就入队
}
}
}

int main()
{
for (int i = 1; i <= m; ++i)
{
deg[v]++; //入度++
}

topsort(); //拓扑排序

if (cnt < n) //拓扑序列的元素个数小于点数，说明有环
puts("有环");
else
puts("无环");

for (int i = 1; i <= cnt; ++i)
printf("%lld ", ans[i]); //输出拓扑序列

return 0;
}
``````

### Tarjan

P3387 【模板】缩点

``````const ll N = 10002;

ll head[N], tott, w[N], n, m;
ll dfn[N], low[N], st[N], top, totx, cntscc;
ll belong[N], in[N], f[N];
bool vis[N], vis_out[N];

struct node{
ll to, nxt;
} t[N * 10];

{
t[tott].to = v;
}

struct Scc{
ll w;
vector<ll> to;
// vector<ll> have;
} SCC[N * 10];

void Tarjan(ll now)
{
low[now] = dfn[now] = ++totx;
st[++top] = now;
vis[now] = 1;
for(int i = head[now]; i;i = t[i].nxt)
{
ll y = t[i].to;
if(!dfn[y])
{
Tarjan(y);
low[now] = min(low[now], low[y]);
}
else if(vis[y])
low[now] = min(low[now], low[y]);
}
if(dfn[now] == low[now])
{
ll y;
++cntscc;
while(y = st[top--])
{
vis[y] = 0;
belong[y] = cntscc;
SCC[cntscc].w += w[y];
// SCC[cntscc].have.push_back(y); 存放此 SCC 里有哪些点
if(now == y) break;
}
}
return;
}

ll topo()
{
queue<ll> q;
for(int i = 1; i <= cntscc; ++i)
for(int j = 0; j < SCC[i].to.size(); ++j)
++in[SCC[i].to[j]];
for(int i = 1; i <= cntscc; ++i)
if(in[i] == 0)
q.push(i), f[i] = SCC[i].w;

while(!q.empty())
{
ll x = q.front();
q.pop();
for(int j = 0; j < SCC[x].to.size(); ++j)
{
ll y = SCC[x].to[j];
f[y] = max(f[y], f[x] + SCC[y].w);
if(--in[y] == 0)
q.push(y);
}
}
ll ans = 0;
for(int i = 1; i <= cntscc; ++i)
ans = max(f[i], ans);
return ans;
}

int main()
{

for(int i = 1; i <= n; ++i)

for(int i = 1; i <= m; ++i)
{
if(x == y) continue; //判断重边
}

for(int i = 1; i <= n; ++i)
{
if(!dfn[i])
Tarjan(i);
}

for(int i = 1; i <= n; ++i) // 重构图
for(int j = head[i]; j; j = t[j].nxt)
{
ll y = t[j].to;
if(belong[i] != belong[y])
SCC[belong[i]].to.push_back(belong[y]);
}

printf("%lldn", topo());
return 0;
}
``````

## 字符串

### 快速读入

``````void Init()
{
char ch;
ch = getchar();
while (ch < 'A' || ch > 'Z')
ch = getchar();
while (ch >= 'A' && ch <= 'Z')
{
A[++lena] = ch;
ch = getchar();
}

while (ch < 'A' || ch > 'Z')
ch = getchar();
while (ch >= 'A' && ch <= 'Z')
{
B[++lenb] = ch;
ch = getchar();
}
}
``````

### KMP

(A) 为大串，(B) 为小串。

(next) 数组

``````void make_nxt()
{
j = 0;
for (int i = 2; i <= lenb; ++i)
{
while (B[i] != B[j + 1] and j)
j = nxt[j];
if (B[i] == B[j + 1])
++j;
nxt[i] = j;
}
}
``````

``````void check()
{
j = 0;
for (int i = 1; i <= lena; i++)
{
while (A[i] != B[j + 1] and j)
j = nxt[j];
if (A[i] == B[j + 1])
++j;
if (j == lenb)
{
printf("%lldn", i - lenb + 1);
j = nxt[j];
}
}
}
``````

### AC自动机

#### 模板1

``````const int N = 1000005;
int n, len, tot, ch[N][30], End[N], fail[N];
char s[N];
queue<int> q;

void insert()
{
len = strlen(s + 1);
int now = 0;
for (int i = 1; i <= len; i++)
{
int c = s[i] - 'a';
if (!ch[now][c])
ch[now][c] = ++tot;
now = ch[now][c];
}

End[now]++;
}

void make_AC()
{
for (int i = 0; i < 26; i++)
{
if (ch[0][i])
{
fail[ch[0][i]] = 0; //特殊处理，避免跳回自己
q.push(ch[0][i]);
}
}
while (!q.empty())
{
int x = q.front();
q.pop();
for (int i = 0; i < 26; i++)
{
if (ch[x][i])
{
fail[ch[x][i]] = ch[fail[x]][i];
q.push(ch[x][i]);
}
else
ch[x][i] = ch[fail[x]][i];
}
}
}

int check_tot()
{
len = strlen(s + 1);
int now = 0, ans = 0;
for (int i = 1; i <= len; i++)
{
now = ch[now][s[i] - 'a'];
for (int t = now; t > 0 && End[t] != -1; t = fail[t])
{
ans += End[t];
End[t] = -1;
}
}
return ans;
}

int main()
{
for (int i = 1; i <= n; i++)
{
scanf("%s", s + 1);
insert();
}

make_AC();

scanf("%s", s + 1);
printf("%dn", check_tot());

return 0;
}
``````

#### 模板2

``````const int N = 1000005;
int n, len, cnt, tot, maxn;
int ch[N][30], End[N], fail[N];
int num[210], sum[210];
char t[N], s[210][210];
queue<int> q;

void C()
{
while (q.size())
q.pop();
maxn = 0;
cnt = 0;
tot = 0;
memset(ch, 0, sizeof(ch));
memset(sum, 0, sizeof(sum));
memset(End, 0, sizeof(End));
memset(ch, 0, sizeof(ch));
}

void insert(ll k)
{
len = strlen(s[k] + 1);
int now = 0;
for (int i = 1; i <= len; ++i)
{
int c = s[k][i] - 'a';
if (!ch[now][c])
ch[now][c] = ++tot;
now = ch[now][c];
}
End[now] = k;
}

void make_AC()
{
for (int i = 0; i < 26; i++)
{
if (ch[0][i])
{
fail[ch[0][i]] = 0; //特殊处理，避免跳回自己
q.push(ch[0][i]);
}
}
while (!q.empty())
{
int x = q.front();
q.pop();
for (int i = 0; i < 26; i++)
{
if (ch[x][i])
{
fail[ch[x][i]] = ch[fail[x]][i];
q.push(ch[x][i]);
}
else
ch[x][i] = ch[fail[x]][i];
}
}
}

void check()
{
len = strlen(t + 1);
int now = 0;
for (int i = 1; i <= len; i++)
{
now = ch[now][t[i] - 'a'];
for (int t = now; t > 0; t = fail[t])
{
++sum[End[t]];
}
}
}

int main()
{
while (1)
{
if (n == 0)
return 0;

for (int i = 1; i <= n; ++i)
{
scanf("%s", s[i] + 1);
insert(i);
}

make_AC();
scanf("%s", t + 1);
check();

for (int i = 1; i <= n; ++i)
{
if (sum[i] > maxn)
{
maxn = sum[i];
cnt = 1;
num[cnt] = i;
}
else if (sum[i] == maxn)
{
num[++cnt] = i;
}
}

printf("%dn", maxn);

for (int i = 1; i <= cnt; i++)
{
len = strlen(s[num[i]] + 1);
for (int j = 1; j <= len; j++)
{
printf("%c", s[num[i]][j]);
}
puts("");
}

C();
}
return 0;
}
``````

#### 模板3

``````const int N = 2000005;
int n, len, cnt, tot, maxn;
int ch[N][30], End[N], fail[N], in[N], ans[N];
int num[210], sum[210], Map[N], f[N];
char t[N], t2[N];
queue<int> q, q2;
vector<char> s[N];

void insert(int k)
{
int now = 0;
for (int i = 0; i < s[k].size(); i++)
{
int c = s[k][i] - 'a';
if (!ch[now][c])
ch[now][c] = ++tot;
now = ch[now][c];
}
if (!End[now])
End[now] = k;
Map[k] = End[now];
}

void make_AC()
{
for (int i = 0; i < 26; i++)
{
if (ch[0][i])
{
fail[ch[0][i]] = 0;
q.push(ch[0][i]);
}
}
while (!q.empty())
{
int x = q.front();
q.pop();
for (int i = 0; i < 26; i++)
{
if (ch[x][i])
{
fail[ch[x][i]] = ch[fail[x]][i];
in[fail[ch[x][i]]]++;
q.push(ch[x][i]);
}
else
ch[x][i] = ch[fail[x]][i];
}
}
}

void check()
{
int now = 0, len = strlen(t + 1);
for (int i = 1; i <= len; i++)
{
int c = t[i] - 'a';
now = ch[now][c];
f[now]++;
}
}

void top()
{
for (int i = 1; i <= tot; i++)
{
if (in[i] == 0)
q2.push(i);
}

while (!q2.empty())
{
int x = q2.front();
q2.pop();
in[fail[x]]--;
ans[End[x]] += f[x];
f[fail[x]] += f[x];
if (in[fail[x]] == 0)
{
q2.push(fail[x]);
}
}
}

int main()
{
for (int i = 1; i <= n; ++i)
{
scanf("%s", t2 + 1);
len = strlen(t2 + 1);
for (int j = 1; j <= len; ++j)
s[i].push_back(t2[j]);
insert(i);
}
make_AC();
scanf("%s", t + 1);
check();
top();
for (int i = 1; i <= n; i++)
printf("%dn", ans[Map[i]]);

return 0;
}
``````

### 扩展 KMP

``````
const int MAXN = 2e7 + 5;
char B[MAXN], A[MAXN];
int lenb, lena, z[MAXN], ext[MAXN];

void getZ() //求 z 数组
{
z[0] = lenb;
int now = 0;
while (now + 1 < lenb && B[now] == B[now + 1])
now++;
z[1] = now;
int p0 = 1;
for (int i = 2; i < lenb; ++i)
{
if (i + z[i - p0] < p0 + z[p0])
{
z[i] = z[i - p0]; //第一种情况
}
else
{
now = p0 + z[p0] - i;
now = max(now, 0);
while (now + i < lenb && B[now] == B[now + i])
now++;
z[i] = now;
p0 = i;
}
}
}

void exkmp() //求 B 与 A 的每一个后缀的 LCP 长度数组
{
int now = 0;
while (now < lenb && now < lena && B[now] == A[now])
now++;
ext[0] = now;
int p0 = 0;
for (int i = 1; i < lena; ++i)
{
if (i + z[i - p0] < p0 + ext[p0])
ext[i] = z[i - p0];
else
{
now = p0 + ext[p0] - i;
now = max(now, 0);
while (now < lenb && now + i < lena && B[now] == A[now + i])
now++;
ext[i] = now;
p0 = i;
}
}
}

int main()
{
scanf("%s%s", A, B);
lena = strlen(A); //文本串
lenb = strlen(B); //模式串

getZ();
exkmp();

得到 z[], p[];

}

``````

## STL

### string

``````#include<cstring>
string s1,s2;

s1 + s2;    // 将两个字符串拼接
[cur];      // 访问下标
s1.size();  // 返回字符串长度
s1.append(s2);          // 将 s2 添加到 s1 末尾
s1.replace(pos, n, s2); // 删除从 pos 开始的 n 个字符，然后在 pos 处插入串 s
s1.erase(pos, n);       // 删除从 pos 开始的 n 个字符
s1.insert(pos, s2);     // 在 pos 位置插入字符串 s
s1.substr(start, len);  // 从 start 截取一个长度为 len 的字符串
s1.find(char，st = 0);  // 查找并返回从 start 开始的字符 ch 的位置
s1.rfind(ch);           //从末尾开始，查找并返回第一个找到的字符 ch 的位置
// 找不到则返回 -1
``````

### queue

``````#include<queue>

queue<int> q;
// priority_queue<int> q（从大到小排序）;

q.empty();      // 判断队列是否为空
q.size();       // 返回队列长度
q.push(item);   // 对于 queue，在队尾压入一个新元素
// 对于 priority_queue，在基于优先级的适当位置插入新元素
q.pop();        // 弹出队首元素

// queue only:
q.front();      //返回队首元素的值，但不删除该元素
q.back();       //返回队尾元素的值，但不删除该元素

// priority_queue only:
q.top();        //返回具有最高优先级的元素值，但不删除该元素
``````

### stack

``````#include<set>
stack<int> s;
stack<int, vector<int> > stk;  // 覆盖基础容器类型，使用vector实现stk
s.empty();      // 判断 stack 是否为空，为空返回 true，否则返回 false
s.size();       // 返回 stack 中元素的个数
s.pop();        // 删除栈顶元素，但不返回其值
s.top();        // 返回栈顶元素的值，但不删除此元素
s.push(item);   // 在栈顶压入新元素 item
``````

### list

``````list<ll> l, l2;
list<ll>::iterator it;

/* 操作 */
l.clear();      // 清空
l.insert(it, 0);// 在迭代器前面插入一个元素，迭代器指向原来的元素
l.erase(it);    // 删除迭代器指向的元素
l.remove(0);    // 在 list 删除某一种元素（全删）
l.push_back(0); // 在 list 的末尾添加一个元素
l.push_front(0);// 在 list 的头部添加一个元素
l.pop_back();   // 删除最后一个元素
l.pop_front();  // 删除第一个元素
l.merge(l2);    // 合并两个 list
l.reverse();    // 把 list 的元素倒转
l.sort();       // 给 list 排序
l.swap(l2);     // 交换两个 list
l.unique();     // 删除 list 中重复的元素

/* 查询 */
l.begin();      // 返回指向第一个元素的迭代器
l.end();        // 返回末尾的迭代器
l.front();      // 返回第一个元素
l.back();       // 返回最后一个元素
l.empty();      // 如果 list 是空的则返回 1
l.size();       // 返回 list 中的元素个数

/* 遍历 */
for(it = l.begin(); it != l.end(); ++it)
cout<<*it<<' ';
``````

### set

``````set<int> s;
// multiset<int> s （不去重）
set<int>::const_iterator iter; // 迭代器

s.insert();   // 插入
s.erase();    // 若参数为元素值，则删除所有该元素值
// 若参数为迭代器，则删除该迭代器指向的值
s.empty();    // 判断 set 是否为空，为空返回 true，否则返回 false
s.count();    // 返回某个值元素的个数
s.clear();    // 清除所有元素
s.find();     // 查找某元素，找到则返回其迭代器，否则返回 s.end()
s.begin();    // 返回指向第一个元素的迭代器
--s.end();    // 返回指向最后一个元素的迭代器
*s.begin();   // 返回指向第一个元素的值
*--s.end();   // 返回指向最后一个元素的值
// 区间形式为 [ begin , end ) ，所以 end 要自减
s.size();     // 返回集合中元素的个数
*s.lower_bound(k);    // 返回第一个大于等于k的元素值
*s.upper_bound(k);    // 返回第一个大于k的元素值 （后继）
// 如果没有符合条件的值，则输出 s.size()

/* 遍历 */
for(iter = s.begin() ; iter != s.end() ; ++iter)
cout<<*iter<<" "; // 使用迭代器遍历
``````

#### unordered_set

``````#include <unordered_set>
// #include <unordered_multiset>
unordered_set<ll> s;
// unordered_multiser<ll> s;

s.insert(); // 在开头插入某元素
s.find();   // 查找，返回迭代器
s.count();  // 返回某个值元素的个数

/* 遍历 */
for(iter = s.begin() ; iter != s.end() ; ++iter)
cout<<*iter<<" ";
// 注意：新插入的元素遍历时先被扫到。
``````

### map

``````#include<map>
map<string, int> m;// string 是 key，int 是 value。

/* 基本操作 */
m.size();   // 输出元素个数
m.empty();  // 如果 map 为空则返回 true
m.clear();  // 删除所有元素

/* 插入 */
m["AKIOI"] = 10;
m.insert(make_pair("AKIOI", 10));

/* 修改 */
m["AKIOI"] = 10;
m.find("AKIOI")->second = ...;

/* 查找 */
m["AKIOI"];
m.find("AKIOI")->second;

/* 遍历 */

for(auto it = mp.begin(); it != mp.end(); ++it)
cout << it->second << ' ';
``````

#### multimap

``````#include <map>
multimap<int, string> mp; // 可重

mp.size(), mp.empty(), mp.clear(); // 常规操作
mp.count(k) // 找 key 为 k 的个数
mp.find(k)  // 返回第一个插入的 k 的迭代器
mp.erase(k) // 删除所有键值为 k 的元素

/* 插入 */
mp.insert(make_pair(int, string)); // 只能用 make_pair 构造键值对

/* 修改 */
m.find(k)->second = ...; // 修改第一个插入的 key 为 k 的
for(auto it = mp.find(k); it->first == k; ++it) // 修改 key 为 k，值为自己选的
if(it->second == "I") it->second = "Love";

/* 查找 */
mp.find(k)->second;

/* 遍历 */
for(auto it = mp.begin(); it != mp.end(); ++it)
cout << it->second << ' ';
``````

#### unordered_map

``````#include<unordered_map>

``````

### bitset

``````bitset<100> b;
bitset<100> f;

b = 10, f = 11;
b[0]; // 访问某一位

/* 相同大小的 bitset 可以进行运算符操作 */
/* == != & &= | |= ^ ^= ~ << <<= >> >>=  */

b.count();  // 返回 1 的数量
b.size();   // 返回 bitset 的大小
b.any();    // 若有 1， 返回 1
b.none();   // 若无 1， 返回 1
b.all();    // 若全是 1， 返回 1
b.set();    // 全部设为 1
b.set(0, 0);// 将第 pos 位设为 k
b.reset();  // 全部设为 0
b.flip();   // 翻转每一位
b.flip(0);  // 翻转某一位
``````

### rope

`rope` 的复制操作是 (O(log n)) 的，可以较轻松地实现可持久化。

``````#include <ext/rope>
using namespace __gnu_cxx;
``````

``````crope a;
``````

``````a.push_back(x);  // 在 a 的末尾添加字符串 x
a.insert(k, x);  // 在 a 的第 k 个字符后加入字符串 x
a.erase(k, x);   // 在 a 的第 k 个字符后删除 x 个字符
a.replace(k, x); // 将 a 的第 k 个字符后 x 的长度个字符删除，并插入 x
a.substr(k, x);  // 获取 a 的第 k 个字符后的长度为 x 的字符串
a.at(k);         // 获取 a 的第 k 个字符（从 0 开始）
``````