线段树

#include <iostream>

using namespace std;
const int N = 1e5 + 10, INF = 2147483648;
int n, m;
int w[N];
struct node
{
    int l, r;
    int maxx;
}tr[N * 4];

void pushup(int u)
{
    tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxx;
    int mid = tr[u].l + tr[u].r >> 1;
    int maxx = -INF;
    if (l <= mid) maxx = max(maxx, query(u << 1, l, r));
    if (r > mid) maxx = max(maxx, query(u << 1 | 1, l, r));
    return maxx;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &w[i]);

    build(1, 1, n);

    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(1, l, r));
    }
    return 0;
}

线段树

#include <iostream>

using namespace std;
int n, m;
const int N = 1e5 + 10;
int w[N];
struct node
{
    int l, r;
    int sum;
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (l <= mid) sum += query(u << 1, l, r);
    if (r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}

void modify(int u, int x, int v)
{
    if (tr[u].l == tr[u].r) tr[u].sum += v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &w[i]);

    build(1, 1, n);
    while (m -- )
    {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        if (!k) printf("%d\n", query(1, x, y));
        else modify(1, x, y);
    }
    return 0;
}

树状数组 ### 线段树 ### ST表

P3374 【模板】树状数组 1 https://www.luogu.com.cn/problem/P3374
P3368 【模板】树状数组 2 https://www.luogu.com.cn/problem/P3368
1267 清点人数 https://www.acwing.com/problem/content/1269/
1265 数星星 https://www.acwing.com/problem/content/1267/
P1816 忠诚 https://www.luogu.com.cn/problem/P1816
P2880 [USACO07JAN] Balanced Lineup G https://www.luogu.com.cn/problem/P2880
P3865 【模板】ST 表 https://www.luogu.com.cn/problem/P3865
464.数数 http://oj.daimayuan.top/problem/464

KMP

kmp找子串

L - Oulipo https://vjudge.net/contest/502186#problem/L

next数组找最小循环节

M - Power Strings https://vjudge.net/contest/502186#problem/M

next数组找所有公共前后缀

K - Seek the Name, Seek the Fame https://vjudge.net/contest/502186#problem/K

字符串hash

单调栈 单调队列

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

const int N = 15010, M = 32010;
int tree[M];
int n;
int cnt[N];
int lowbit(int x)
{
    return x & -x;
}

void add(int x, int k)
{
    while (x <= M)
    {
        tree[x] += k;
        x += lowbit(x);
    }
}

int sum(int x)
{
    int res = 0;
    while (x)
    {
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x ++; y ++;
        cnt[sum(x)] ++;
        add(x, 1);
    }

    for (int i = 0; i < n; i ++ ) printf("%d\n", cnt[i]);
    return 0;
}

#include <iostream>
#include <queue>
#include <cstring>
#define ft first
#define sd second
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, pair<int, int>> PIII;
const int N = 1010, M = 20010;
int n, m, S, T, k;
int h[N], sh[N], e[M], w[M], ne[M], idx;
int d[N];
bool st[N];
void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void Dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    memset(d, 0x3f, sizeof d);
    q.push({0, T}); d[T] = 0;
    while (q.size())
    {
        auto t = q.top(); q.pop();
        int val = t.sd;
        if (st[val]) continue;
        st[val] = true;
        for (int i = sh[val]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] > d[val] + w[i])
            {
                d[j] = d[val] + w[i];
                q.push({d[j], j});
            }
        }
    }
}

int Astar()
{
    if (d[S] == 0x3f3f3f3f) return -1;
    priority_queue<PIII, vector<PIII>, greater<PIII>> q;
    q.push({d[S], {0, S}});
    int cnt = 0;
    while (q.size())
    {
        auto t = q.top(); q.pop();
        int val = t.sd.sd, dist = t.sd.ft;
        if (val == T) cnt ++;
        if (cnt == k) return dist;
        for (int i = h[val]; i != -1; i = ne[i])
        {
            int j = e[i];
            q.push({dist + w[i] + d[j], {dist + w[i], j}});
        }
    }
    return -1;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    memset(sh, -1, sizeof sh);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(h, a, b, c);
        add(sh, b, a, c);
    }

    scanf("%d%d%d", &S, &T, &k);
    if (S == T) k ++;

    Dijkstra();
    printf("%d\n", Astar());
    return 0;
}

#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define ft first
#define sd second
using namespace std;

string s, en = "12345678x";
unordered_map<string, pair<string, char>> pre;
unordered_map<string, char> red;
unordered_map<string, int> d;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
char op[4] = {'u', 'r', 'd', 'l'};
struct node
{
    string s;
    int w;
    bool operator< (const node &t) const
    {
        return w > t.w;
    }
};

int get_d(string str)
{
    int res = 0;
    for (int i = 0; i < 9; i ++ )
        for (int j = 0; j < 9; j ++ )
            if (str[i] == en[j] && str[i] != 'x')
                {res += abs(i / 3 - j / 3) + abs(i % 3 - j % 3); break;}
    return res;
}

void bfs()
{
    priority_queue<node> q;
    q.push({s, get_d(s)});
    d[s] = 1;
    while (q.size())
    {
        node t = q.top(); q.pop();
        string str = t.s; int w = t.w;
        // cout << str << ' ' << w << endl;
        if (str == en) break;
        for (int i = 0; i < 4; i ++ )
        {
            string cpy(str);
            int j;
            for (j = 0; j < 9; j ++ ) if (cpy[j] == 'x') break;
            int x = j / 3 + dx[i], y = j % 3 + dy[i];
            if (x < 0 || y < 0 || x >= 3 || y >= 3) continue;
            swap(cpy[x * 3 + y], cpy[j]);

            if (!d.count(cpy) || d[cpy] > d[str] + 1)
            {
                d[cpy] = d[str] + 1;
                q.push({cpy, d[cpy] + get_d(cpy)});
                pre[cpy] = {str, op[i]};
            }
        }
    }

    string res;
    while (en != s)
    {
        res += pre[en].sd;
        en = pre[en].ft;
    }
    reverse(res.begin(), res.end());
    cout << res << endl;
}
int main()
{
    char c;
    while (cin >> c) s += c; 
    int x = 0;
    for (int i = 0; i < 9; i ++ )
        for (int j = i + 1; j < 9; j ++ )
            if (s[i] != 'x' && s[j] != 'x' && s[i] > s[j])
                x ++;
    if (x & 1) cout << "unsolvable" << endl;
    else bfs();
    return 0;
}

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
string a, b;
string s1[10];
string s2[10];
unordered_map<string, int> d1;
unordered_map<string, int> d2;
int cnt;
int bfs()
{
    if (a == b) return 0;
    queue<string> ft, en;
    ft.push(a); d1[a] = 1;
    en.push(b); d2[b] = 1;
    while (ft.size() && en.size())
    {
        auto t1 = ft.front(); ft.pop();
        auto t2 = en.front(); en.pop();
        for (int i = 0; i < cnt; i ++ )
        {
            int lena = t1.size();
            int lenb = t2.size();
            int len1 = s1[i].size();
            int len2 = s2[i].size();
            //正向搜
            for (int j = 0; j <= lena - len1; j ++ )
            {
                if (t1.substr(j, len1) == s1[i])
                {
                    string str;
                    str += t1.substr(0, j);
                    str += s2[i];
                    str += t1.substr(j + len1, lena - len1 - j);

                    if (d1[str]) continue;
                    d1[str] = d1[t1] + 1, ft.push(str);
                    if (d2[str]) return d1[str] + d2[str] - 2;
                }
            }
            //反向搜
             for (int j = 0; j <= lenb - len2; j ++ )
            {
                if (t2.substr(j, len2) == s2[i])
                {
                    string str;
                    str += t2.substr(0, j);
                    str += s1[i];
                    str += t2.substr(j + len2, lenb - len2 - j);

                    if (d2[str]) continue;
                    d2[str] = d2[t2] + 1, en.push(str);
                    if (d1[str]) return d1[str] + d2[str] - 2;
                }
            }
        }
    }
    return 11;
}

int main()
{
    cin >> a >> b;
    while (cin >> s1[cnt] >> s2[cnt ++ ]); cnt --;
    int res = bfs();
    if (res <= 10) cout << res << endl;
    else cout << "NO ANSWER!" << endl;
    return 0;
}

#include <iostream>
#include <deque>
#include <cstring>
#define ft first
#define sd second
using namespace std;
typedef pair<int, int> PII;
const int N = 510;
char g[N][N];
int d[N][N];
bool st[N][N];
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
char s[5] = "\\/\\/";
int n, m;
int bfs()
{
    memset(d, 0x3f, sizeof d);
    memset(st, false, sizeof st);
    deque<PII> q;
    q.push_back({0, 0});
    d[0][0] = 0;
    while (q.size())
    {
        auto t = q.front();
        q.pop_front();
        int x = t.ft, y = t.sd;
        if (st[x][y]) continue;
            st[x][y] = true;
        // cout << x << ' ' << y << endl;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || b < 0 || a > n || b > m) continue;

            int w = (g[x + ix[i]][y + iy[i]] != s[i]);
            int dd = d[x][y] + w;
            if (d[a][b] > dd)
            {
                d[a][b] = dd;
                if (w) q.push_back({a, b});
                else q.push_front({a, b});
            }
            if (a == n && b == m)
            {
                cout << x << ' ' << y << endl;
                return d[a][b];
            }

        }
    }
    return -1;
}
int main()
{
    int Q;
    scanf("%d", &Q);
    while (Q -- )
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i ++ ) scanf("%s", &g[i]);
        if (n + m & 1) puts("NO SOLUTION");
        else
        {
            printf("%d\n", bfs());
        }
    }
}

bfs

1、多源BFS最短路

173.矩阵距离 https://www.acwing.com/problem/content/175/

2、flood_fill

P1162 填涂颜色 https://www.luogu.com.cn/problem/P1162

3、最短路+花里胡哨的障碍

P1126 机器人搬重物 https://www.luogu.com.cn/problem/P1126
A计划 https://vjudge.net/problem/HDU-2102

4、最小步数模型

1107.魔板 https://www.acwing.com/problem/content/1109/

5、双端队列搜索

175.电路维修 https://www.acwing.com/problem/content/description/177/
作者：   小呆呆 (要求及删)
与堆优化Dijkstra 一样，必须在出队时才知道每个点最终的最小值，而和一般的bfs不一样，原因是如下图所示

6、BFS + 优先队列优化

P3956 [NOIP2017 普及组] 棋盘 https://www.luogu.com.cn/problem/P3956

为什么经典的走迷宫模型可以直接普通队列 BFS ？

不难得出：在这样的 BFS 中，每一次扩展的代价都相等且为正数，后进入队列的状态一定不如先进入队列的状态优（先进入队列的状态的代价 ≤ 后进入队列的状态的代价）。

基于这样的单调性，我们可以得出：第一次访问到某一个状态时，一定是这个状态的最优情况。

这是一个贪心思想。我们把这种思想应用到更具有普遍性的情况中：代价不一定相等。

优先队列( Dijkstra )
我们只要满足每一次都从状态队列中取出最小代价的状态，即可满足第一次访问最优性。优先队列可以实现这种操作。时间复杂度 O(nlogn) 。

7、双向BFS

190.字串变换 https://www.acwing.com/problem/content/192/
*不能每次扩展一个点交替搜索(每次扩展一层)

8、A*

178.第K短路 https://www.acwing.com/problem/content/180/
179.八数码 https://www.acwing.com/problem/content/description/181/

/*
A* 应用场景:
起点→终点的最短距离
状态空间 >> 1e10 
启发函数减小搜索空间

A*算法:
while(q.size())
    t ← 优先队列的队头  小根堆
        当终点第一次出队时 break;
        从起点到当前点的真实距离 d_real
        从当前点到终点的估计距离 d_estimate
        选择一个估计距离最小的点 min(d_estimate)
    for j in ne[t]:
        将邻边入队

A*算法条件:
估计距离<=真实距离
d[state] + f[state] = 起点到state的真实距离 + state到终点的估计距离=估计距离
                                                                       ^
d[state] + g[state] = 起点到state的真实距离 + state到终点的真实距离=真实距离

一定是有解才有 d[i]   >= d[最优] = d[u]+f[u]
        f[u] >= 0

证明终点第一次出队列即最优解

    1 假设终点第一次出队列时不是最优 
      则说明当前队列中存在点u
         有 d[估计]< d[真实]
      d[u] + f[u] <= d[u] + g[u] = d[队头终点]
      即队列中存在比d[终点]小的值,
    2 但我们维护的是一个小根堆,没有比d[队头终点]小的d[u],矛盾

    证毕

A* 不用判重
以边权都为1为例
  A o→o→o
    ↑   ↓
  S o→o→o→o→o→o→o T
      B
dist[A] = dist[S]+1 + f[A] = 7
dist[B] = dist[S]+1 + f[B] = 5
则会优先从B这条路走到T
B走到T后再从A这条路走到T

作者：仅存老实人
链接：https://www.acwing.com/solution/content/21233/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

dfs

1、搜索顺序与剪枝优化

1118 分成互质组 https://www.acwing.com/problem/content/1120/
165.小猫爬山 https://www.acwing.com/problem/content/167/

2、IDA*

DNA sequence https://vjudge.net/problem/HDU-1560#author=0

一、质数

基础：
1、试除法判定质数
时间复杂度：O(sqrt(n))
2、分解质因数 O(logn ~ sqrt(n))
特别的：数量多数值小的情况：可以考虑先筛质数再根据质数分解质因数（时间复杂度要小10倍左右）
3、筛质数
1)朴素筛O(nlogn)
2)埃筛O(nlognlogn)
3）线性筛O(n)
拓展:线性筛可以同时筛:
Ⅰ、欧拉函数
Ⅱ、莫比乌斯函数

二、约数

基础：
1、试除法求约数
时间复杂度：O(sqrt(n))
2、870. 约数个数
时间复杂度：O(nsqrt(ai))