OI模板

$\begin{matrix}\color{gold}\colorbox{black{______________________________________________________________________\kern{0.4pt}} \
\large \colorbox{black}{\color{gold}\underline{\texttt{Caution!!! \qquad Caution!!! \qquad Caution!!! \qquad Caution!!! }}}\
\Large \colorbox{black}{\color{gold}\underline\text{\Huge ☢:\Large本文使用了少量\LaTeX，可能会导致加载极快!\Huge :☢\Large\ \ !! \color{black}\kern{8.4pt}}} \
\large \colorbox{black}{\color{gold}\underline{\texttt{Caution!!! \qquad Caution!!! \qquad Caution!!! \qquad Caution!!! }}}\
\end{matrix}$

Update:

2021.6.29    
新增 KMP 和 LCA

历史更新记录

2021.6.28
新增 std::string
新增 Tarjan
 
2021.6.15
新增 Treap 和 左偏树<br>
 
2021.6.14
新增 Kruskal 最小生成树 <br>
 
2021.5.30
单源最短路径新增 vector 存图的 <br>
 
2021.5.16
动态规划新增 LCIS （最长公共上升子序列）<br>
 
2021.5.14
更新了区间dp的模板<br>
 
2021.4.29
新增了珂朵莉树
快速幂的代码锅了，现已修复
格式化了全部代码！！！<br>
 
2021.4.28
添加了单调队列，包含 “定长” 和 “不定长”。<br>
 
2021.4.23
求 gcd 的部分锅了，重新写了下。<br>
 
2021.4.20
新增线段树的区间加乘，区间修改。
重构了线段树的代码。
更新了部分标题名称。

考试必备

快速读入

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;
}

对拍

卡常小技巧

① 位运算乘除

\[x=x\times2^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];
ll n, m, a[100001];

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

ll ST_q(ll l, ll r)
{
    ll k = log(r - l + 1) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    ST_make();
    for (int i = 1; i <= m; ++i)
    {
        ll l = read(), r = read();
        printf("%lld\n", ST_q(l, r));
    }
    return 0;
}

单调队列

例题1

有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

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

struct node
{
    ll sum, id;
};

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

int main()
{
    n = read();
    k = read();
    node t;
    for (int i = 1; i <= n; ++i)
    {
        ll x = read();
        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]);
}

例题2

最大不定长子段和问题。

在一段长为 \(n\) 的数列中，找出一个长度 \(≤m\) 的子段，使得它的和是最大的。子段长度不能为0。

const ll maxn = 5000005;
#define INF 9223372036854775800

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

int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i)
    {
        ll x = read();
        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("%lld\n", 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()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i) //初始化
    {
        ll x = read();
        add(i, x);
    }
    for (int i = 1; i <= m; ++i)
    {
        ll opt = read();
        if (opt == 1) //单点修改
        {
            ll x = read(), k = read();
            add(x, k);
        }
        else if (opt == 2) //区间查询
        {
            ll x, y;
            x = read();
            y = read();
            ll ans = ask(x, y);
            printf("%lld\n", ans);
        }
    }
    return 0;
}

线段树

注：本线段树使用链表形式（指针），每个结点都是左闭右开区间。

单点加

作用等同于树状数组，但是线段树时间和空间的开销都非常大。

ll n, m;

struct node
{ //树结点
    ll L, R, sum, k;
    node *lc, *rc;
};

void build(node *now, ll l, ll r) //建树
{
    now->L = l;
    now->R = r;
    now->sum = 0;
    if (l + 1 < r) //不是叶子，继续递归
    {
        now->lc = new node;
        now->rc = new node;
        ll mid = (l + r) / 2;
        build(now->lc, l, mid);
        build(now->rc, mid, r);
    }
    else
        now->lc = now->rc = NULL; //是叶子，停下
}

ll check(node *now, ll l, ll r) //查询区间和
{
    if (l <= now->L && now->R <= r + 1) //勿忘 r+1
        return now->sum;
    else
    {
        ll ans = 0;
        ll mid = (now->L + now->R) / 2;
        if (l < mid)
            ans += check(now->lc, l, r);
        if (r >= mid)
            ans += check(now->rc, l, r); //右边需要取等
        return ans;
    }
}

void change(node *now, ll x, ll k) //单点修改
{
    if (now->L + 1 == now->R)
    {
        now->sum += k;
    }
    else
    {
        ll mid = (now->L + now->R) / 2;
        if (x < mid)
            change(now->lc, x, k);
        if (x >= mid)
            change(now->rc, x, k); //右边需要取等
        now->sum = now->lc->sum + now->rc->sum;
    }
}

int main()
{
    n = read();
    m = read();
    node *root;
    root = new node; //创建根结点
    build(root, 1, n + 1);

    for (int i = 1; i <= n; ++i) //初始化
    {
        ll x = read();
        change(root, i, x);
    }

    for (int i = 1; i <= m; ++i)
    {
        ll opt = read();
        if (opt == 1) //区间修改
        {
            ll x = read(), k = read();
            change(root, x, k);
        }
        else if (opt == 2) //区间查询
        {
            ll l = read(), r = read();
            ll res = check(root, l, r);
            printf("%lld\n", res);
        }
    }
    return 0;
}

区间加

需要延迟修改。

对于结点，新加 \(k\)，代表延迟修改量。

新增延迟信息下传函数 update()

对于修改和查询函数新增延迟操作。

ll n, m;

struct node
{                    //树结点
    ll L, R, sum, k; //多出了延迟修改量 k
    node *lc, *rc;
};

void build(node *now, ll l, ll r) //建树

void update(node *now) //更新
{
    now->lc->sum += now->k * (now->lc->R - now->lc->L);
    now->rc->sum += now->k * (now->rc->R - now->rc->L);
    now->lc->k += now->k;
    now->rc->k += now->k;
    now->k = 0;
}

ll check(node *now, ll l, ll r) //查询区间和
{
    if (l <= now->L && now->R <= r + 1) //勿忘 r+1
        return now->sum;
    else
    {
        update(now); //多了更新这一步
        ll ans = 0;
        ll mid = (now->L + now->R) / 2;
        if (l < mid)
            ans += check(now->lc, l, r);
        if (r >= mid)
            ans += check(now->rc, l, r); //右边需要取等
        return ans;
    }
}

void change(node *now, ll l, ll r, ll k) //区间修改
{
    if (l <= now->L && now->R <= r + 1)
    {
        now->sum += k * (now->R - now->L);
        now->k += k;
    }
    else
    {
        update(now); //同样多了更新这一步
        ll mid = (now->L + now->R) / 2;
        if (l < mid)
            change(now->lc, l, r, k);
        if (r >= mid)
            change(now->rc, l, r, k);
        now->sum = now->lc->sum + now->rc->sum;
    }
}

int main()
{
    n = read();
    m = read();
    node *root;
    root = new node; //创建根结点
    build(root, 1, n + 1);

    for (int i = 1; i <= n; ++i) //初始化
    {
        ll x = read();
        change(root, i, i, x); //区间修改单点
    }

    for (int i = 1; i <= m; ++i)
    {
        ll opt = read();
        if (opt == 1) //区间修改（加）
        {
            ll l = read(), r = read(), k = read();
            change(root, l, r, k);
        }
        else if (opt == 2) //区间查询
        {
            ll l = read(), r = read();
            ll res = check(root, l, r);
            printf("%lld\n", res);
        }
    }
    return 0;
}

区间加乘

操作为加或乘，最后答案模 \(mod\)。

打两个标记，分别为 add 和 mul 。

ll n, m, mod;

struct node
{                           //树结点
    ll L, R, sum, mul, add; //多了 mul 和 add
    node *lc, *rc;
};

void build(node *now, ll l, ll r) //建树
{
    now->L = l;
    now->R = r;
    now->sum = 0;
    now->mul = 1;
    if (l + 1 < r) //不是叶子，继续递归
    {
        now->lc = new node;
        now->rc = new node;
        ll mid = (l + r) / 2;
        build(now->lc, l, mid);
        build(now->rc, mid, r);
    }
    else
        now->lc = now->rc = NULL; //是叶子，停下
}

void update(node *now) //更新
{
    now->lc->sum = ((now->mul * now->lc->sum) % mod + (now->add * (now->lc->R - now->lc->L) % mod) % mod) % mod;
    now->rc->sum = ((now->mul * now->rc->sum) % mod + (now->add * (now->rc->R - now->rc->L) % mod) % mod) % mod;
    now->lc->mul = (now->mul * now->lc->mul) % mod;
    now->rc->mul = (now->mul * now->rc->mul) % mod;
    now->lc->add = ((now->mul * now->lc->add) % mod + now->add) % mod;
    now->rc->add = ((now->mul * now->rc->add) % mod + now->add) % mod;
    now->add = 0;
    now->mul = 1;
}

ll check(node *now, ll l, ll r) //查询区间和
{
    if (l <= now->L && now->R <= r + 1) //勿忘 r+1
        return now->sum;
    else
    {
        update(now);
        ll ans = 0;
        ll mid = (now->L + now->R) / 2;
        if (l < mid)
            ans = (ans + check(now->lc, l, r)) % mod;
        if (r >= mid)
            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 && now->R <= r + 1)
    {
        now->sum = now->sum + (k * (now->R - now->L)) % mod;
        now->add = (now->add + k) % mod;
    }
    else
    {
        update(now);
        ll mid = (now->L + now->R) / 2;
        if (l < mid)
            add(now->lc, l, r, k);
        if (r >= mid)
            add(now->rc, l, r, k);
        now->sum = (now->lc->sum + now->rc->sum) % mod;
    }
}

void mul(node *now, ll l, ll r, ll k) //区间乘
{
    if (l <= now->L && now->R <= r + 1)
    {
        now->mul = (k * now->mul) % mod;
        now->add = (k * now->add) % mod;
        now->sum = (k * now->sum) % mod;
    }
    else
    {
        update(now);
        ll mid = (now->L + now->R) / 2;
        if (l < mid)
            mul(now->lc, l, r, k);
        if (r >= mid)
            mul(now->rc, l, r, k);
        now->sum = (now->lc->sum + now->rc->sum) % mod;
    }
}

平衡树

Treap

您需要写一种数据结构，来维护一些数，其中需要提供以下操作：

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

第一行为 \(n\)，表示操作的个数,下面 \(n\) 行每行有两个数 \(\text{opt}\) 和 \(x\)，\(\text{opt}\) 表示操作的序号\(( 1≤opt≤6 )\)

对于操作 \(3,4,5,6\) 每行输出一个数，表示对应答案

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

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

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

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)
    {
        add(s[p].r, x);
        if (s[p].rk < s[s[p].r].rk)
            zag(p);
    }
    if (s[p].v > x)
    {
        add(s[p].l, 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();
    n = read();
    for (int i = 1; i <= n; i++)
    {
        ll op = read(), x = read();
        if (op == 1)
            add(root, x);
        if (op == 2)
            delt(root, x);
        if (op == 3)
            printf("%lld\n", getrank(root, x) - 1);
        if (op == 4)
            printf("%lld\n", getval(root, x + 1));
        if (op == 5)
            printf("%lld\n", getpre(x));
        if (op == 6)
            printf("%lld\n", getnxt(x));
    }
    return 0;
}

左偏树

一开始有 \(n\) 个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：

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

第一行包含两个正整数 \(n,m\)，分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含 \(n\) 个正整数，其中第 \(i\) 个正整数表示第 \(i\) 个小根堆初始时包含且仅包含的数。

接下来 \(m\) 行每行 \(2\) 个或 \(3\) 个正整数，表示一条操作。

输出包含若干行整数，分别依次对应每一个操作 \(2\) 所得的结果。

#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()
{
    N = read(), T = read();
    S[0].dis = -1;
    for (i = 1; i <= N; ++i)
        S[i].rt = i, S[i].val = read();
    for (i = 1; i <= T; ++i)
    {
        A = read(), B = read();
        if (A == 1)
        {
            C = read();
            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("%lld\n", S[Get(B)].val), Pop(Get(B));
        }
    }
    return 0;
}

珂朵莉树

神奇的暴力数据结构

例题

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

操作：

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

数据随机，时限 \(2s\)。

关键操作：推平一段区间，使一整段区间内的东西变得一样。保证数据随机

#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()
{
    n = read();
    m = read();
    seed = read();
    vmax = read();
    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)
            add(l, r, x);
        else if (op == 2)
            assign(l, r, x);
        else if (op == 3)
            printf("%lld\n", rnk(l, r, x));
        else
            printf("%lld\n", sum(l, r, x, y));
    }
    return 0;
}

数学

线性筛素数

给定一个整数 \(n\) ，求出 $[2,n] $ 之间的所有素数。

思路：prime 数组存放已经筛出的素数， \(m\) 代表素数个数（也就是说遍历时从 \(1\) 遍历到 \(m\) 即可），v 数组代表有没有被标记，避免重复筛。

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("%d\n", 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); //其实可以在主函数里直接用这个
}

分治

快速乘法取余

给定三个整数 \(a,n,mod\) ，求 \(a \times n ~\%~mod\) 的值。

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;
}

这个东西好像没有必要的样子，貌似只需要 \((a~\%~mod)×(n~\%~mod)~\%~mod\) 即可。

快速幂

给定三个整数 \(a,n,mod\) ，求 \(a^n~\%~mod\) 的值。

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

LIS

求一个序列的最长上升子序列个数。
本程序采用边读边处理 + 二分法。

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

int main()
{
    ll n = read();
    for (int i = 1; i <= n; ++i)
    {
        int x = read();
        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("%lld\n", 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;
}

输出结果：4 7

②结构体内

结构体内使用 lower_bound 需要重载，下面我们主要对结构体中的 \(a\) 进行操作。

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()
{
    int n = read(); //数列中数的个数
    for (int i = 1; i <= n; ++i)
    {
        t[i].a = read(); //读入数列
        t[i].id = i;
    }
    sort(t + 1, t + n + 1, cmp); //按小到大排序

    int x, xiabiao, ans;
    x = read();                                              //需要查找的数字
    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 %d\n", xiabiao, ans);
    return 0;
}

输入：
5
20 40 30 10 50
35
输出：
4 40

另：upper_bound 的使用与 lower_bound 的使用类似，只不过是严格大于（>）。

动态规划

基础模型

数字金字塔

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()
{
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    m = read();
    for (int i = 1; i <= m; ++i)
        b[i] = read();

    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("%lld\n", f[n][ans]);
    for (int p = 1; p <= f[n][ans]; ++p)
        printf("%lld ", lcis[ans][p]);
    puts("");
    return 0;
}

基础背包

01背包

背包数量为 \(V\)，有 \(n\)件物品，重量为 \(w_i\)，价值为 \(c_i\)。求能获得最大价值。

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

int main()
{
    V = read();
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        w[i] = read();
        c[i] = read();
    }
    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("%lld\n", f[V]);
    return 0;
}

01-方案数

一种物品只能选一次，组合出固定价值的方案数问题。

例题：ybt1291：数字组合

ll a[21], f[1003], n, t;
int main()
{
    n = read();
    t = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read();
    }
    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("%lld\n", 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];
    }

完全-方案数

一种物品可以选无限次，组合出固定价值的方案数问题。
例题：ybt1293：买书

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

int main()
{
    m = read();
    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("%lld\n", f[m]);
    return 0;
}

混合背包

一种物品可以选 \(p\) 次。

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

int main()
{
    m = read();
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        w[i] = read();
        c[i] = read();
        p[i] = read();
    }
    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("%lld\n", f[m]);
    return 0;
}

二维费用背包

再加一重循环，多开一维数组即可。

例题：ybt1271：【例9.15】潜水员

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;
    v = read();
    u = read();
    k = read();
    for (int i = 1; i <= k; ++i)
    {
        a[i] = read();
        b[i] = read();
        c[i] = read();
    }
    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("%lld\n", 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

未完成，待补充。

例题：[HNOI2008]玩具装箱

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()
{
    n = read();
    L = read();
    for (int i = 1; i <= n; ++i)
    {
        sum[i] = read();
        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("%lld\n", 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;
    t[tot].nxt = head[u];
    head[u] = tot;
}

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});
}

Dijkstra 最短路

求单源 \(s\) 到任意一点的最短路径。最短路径保存在数组 dis 中。

链式前向星

#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)
        head[i] = -1;
    ...
}
//后面省略

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$ ，如果有负边权就赋无限小。

<ol start="2">
<li>把 <code>dis[y]>dis[x]+z</code> 中的 <code>></code> 改成 <code><</code> 。</li>
</ol>
<h4 id="判断负环">判断负环</h4>
<p>可在最短路代码基础上进行修改。需新加入一个数组 <code>cnt</code> ，专门记录负环。</p>
<p>补充代码：</p>
```cpp
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()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i)
        f[i] = i; //初始化自己的老大是自己

    for (int i = 1; i <= m; ++i)
    {
        int opt, a, b;
        opt = read();
        a = read();
        b = read();
        if (opt == 1)
            f[find(a)] = find(b);
        else
        {
            if (find(a) == find(b))
                printf("Y\n");
            else
                printf("N\n");
        }
    }
    return 0;
}

LCA

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

邻接表存图。

struct node{...};
void add(...){}

ll dep[500010], fa[500010][21], lg[500002];
ll head[500010], tot;
ll n, m, s;

void dfs(ll now, ll fath)
{
    fa[now][0] = fath;
    dep[now] = dep[fath] + 1;
    for (int i = 1; i <= lg[dep[now]]; ++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);
    while (dep[x] > dep[y])
        x = fa[x][lg[dep[x] - dep[y]] - 1];
    if (x == y)
        return x;
    for (int k = lg[dep[x]] - 1; k >= 0; --k)
        if (fa[x][k] != fa[y][k])
            x = fa[x][k], y = fa[y][k];
    return fa[x][0];
}

int main()
{
    n = read();
    m = read();
    s = read();
    for (int i = 1; i <= n; ++i)
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
        
    for (int i = 1; i < n; ++i)
    {
        ll x = read(), y = read();
        add(x, y);
        add(y, x);
    }
    
    dfs(s, 0);
    for (int i = 1; i <= m; ++i)
    {
        ll x = read(), y = read();
        printf("%lld\n", LCA(x, y));
    }
    return 0;
}

最小生成树

Kruskal

前置：并查集

struct node
{
    ll u, v, w;
} t[200005];

ll fa[200005], n, m, ans, eu, ev, cnt;

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

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

inline void K()
{
    sort(t, t + m, cmp);
    for (int i = 1; i <= m; ++i)
    {
        eu = find(t[i].u), ev = find(t[i].v);
        if (eu == ev)
            continue;
        ans += t[i].w;
        fa[ev] = eu;
        if (++cnt == n)
            break;
    }
}

int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
    for (int i = 1; i <= m; ++i)
        t[i].u = read(), t[i].v = read(), t[i].w = read();
    K();
    printf("%lld\n", ans);
    Edison Ba;
}

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()
{
    n = read();
    m = read(); //点，边
    for (int i = 1; i <= m; ++i)
    {
        ll x = read(), y = read();
        add(x, y);
        deg[v]++; //入度++
    }

    topsort(); //拓扑排序

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

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

    return 0;
}

Tarjan

std::vector<int> t[maxn]; //vector 存图
std::vector<int> SCC[maxn];
std::stack<int> stk;

int n, m, tot, cnt;
int vis[maxn], dfn[maxn], low[maxn], belong[maxn];

void Tarjan(const int x)
{
    dfn[x] = low[x] = ++tot;
    vis[x] = 1;
    stk.push(x);
    for (int i = 0; i < t[x].size(); ++i)
    {
        int y = t[x][i];
        if (!dfn[y])
        {
            Tarjan(y);
            low[x] = std::min(low[x], low[y]);
        }
        else if (vis[y])
            low[x] = std::min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        int Last;
        cnt++;
        do
        {
            Last = stk.top();
            vis[Last] = 0;
            belong[Last] = cnt;
            stk.pop();
        } while (stk.size() && Last != x);
    }
    return;
}

signed main()
{
    Init();
    for (int i = 1; i <= n; ++i)
        if (!dfn[i])
            Tarjan(i);
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < t[i].size(); ++j)
            if (belong[i] != belong[t[i][j]])
                SCC[belong[i]].push_back(belong[t[i][j]]);
    ......
    
}

字符串

快速读入

可以根据题目描述自行修改。

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()
{
    k = 1;
    for (int i = 2; i <= lenb; ++i)
    {
        while ((B[k] != B[i] && k > 1) || k > i)
            k = nxt[k - 1] + 1;
        if (B[k] == B[i])
            nxt[i] = k++;
    }
}

匹配

void check()
{
    k = 1;
    for (int i = 1; i + lenb <= lena + 1;)
    {
        while (A[i + k - 1] == B[k] && k <= lenb)
            ++k;
        if (k == lenb + 1)
            printf("%d\n", i);
        if (nxt[k - 1] == 0)
        {
            ++i;
            k = 1;
            continue;
        }
        --k;
        i += k - nxt[k];
        k = nxt[k] + 1;
    }
}

常用 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，start=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

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<<" ";//使用迭代器遍历 
}

map

#include<map>
map<string,int> m;//string 是 key，int 是 value。
m.size();   //输出元素个数
m.empty();  //如果 map 为空则返回 true
m.clear();  //删除所有元素
......

m["AKIOI"] = 10;
cout << m["AKIOI"];
输出结果：10

unordered

#include<unordered_map>
用法：与 map 差别不大。
优点：因为内部实现了哈希表，因此其查找速度非常的快
缺点：哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用 unordered_map