基本算法

快速排序

快速排序有两种实现方式，体现在分割方式的不同。不同于归并排序，快排的排序实现在分割的时候，而非合并的时候。

第一种为Lomuto划分方案：

#include <bits/stdc++.h>
using namespace std;

void quick_sort(int a[], int l, int r) {
    if(l >= r) return;
    swap(a[r], a[(l + r) >> 1]);//随机选取一个数作为中心(这里选取中间的数作为中心)
    int pivot = a[r];//作为比较的中心
    int pi_idx = l;//最终中心的下标

    for(int i = l; i <= r - 1; i++) {
        if(a[i] < pivot) {
            swap(a[i], a[pi_idx]);
            pi_idx++;
        }
    }
    swap(a[r], a[pi_idx]);
    quick_sort(a, l, pi_idx - 1);
    quick_sort(a, pi_idx + 1, r);

}

int b[1000006];
int main() {
    ios::sync_with_stdio(false);
    random_device rd;
    mt19937 rng(rd());
    
    int n;
    cin >> n;   
    for(int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    shuffle(b, b + n, rng);//打乱
    
    quick_sort(b, 0, n - 1);
    for(int i = 0; i < n; i++) {
        cout << b[i] << " ";
    }
}

这种方案具有其局限性：

数组排好序时会退化——我们通过取中点可以优化
数组逆序时会退化——我们通过打乱可以优化（打乱开销却很不合适）
无法解决的数组元素完全相同时，无法优化，一定是n^2

但这种方式也比较易于理解，我们采用尾作为比较对象，如果取其他元素就让其与尾部交换进而保持代码简便性，经过swap之后，我们得到的pi_idx，就是排好序的最终数组中pivot应该处于的位置，我们可以理解为有这么多个元素比他小。

为此，我们学习第二种Hoare划分方式。

#include <bits/stdc++.h>
using namespace std;

void quick_sort(int a[], int l, int r) {
    if(l >= r) return;

    int pivot = a[(l + r) >> 1];
    int i = l, j = r;

    while(i <= j) {
        while(a[i] < pivot) i++;//找到左边比pivot大的数
        while(a[j] > pivot) j--;//找到右边比pivot小的数
        if(i <= j) {//此处分为两种情况理解，小于的时候正常交换，等于的时候i和j都是pivot的下标，所以i++，j--，退出循环。
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }

    if(l < j) quick_sort(a, l, j);//只要理解上面<=的意思，这里就很好理解为什么是l到j和i到r了。
    if(i < r) quick_sort(a, i, r);//此时i - 1和 j + 1是pivot的下标，所以不用再次排序。
}

int b[1000006];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> b[i];
    }
    quick_sort(b, 0, n - 1);
    for(int i = 0; i < n; i++) {
        cout << b[i] << " ";
    }
}

写法和下面是等价的，但我更容易理解上面的操作。

while (i < j)
{
    do i ++ ; while (q[i] < x);
    do j -- ; while (q[j] > x);
    if (i < j) swap(q[i], q[j]);
}

归并排序

和快排相反，归并排序的排序体现在递归时回溯时的合并，只是先单纯的二分分割。

#include <bits/stdc++.h>
using namespace std;

int b[(int)1e5+6], tmp[(int)1e5+6];
void merge_sort(int a[], int l, int r) {
    if(l >= r) return;

    int mid = (l + r) >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);//注意好地板除mid，划分好范围
    
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r) {
        if(a[i] < a[j]) {
            tmp[k++] = a[i++];
        }else {
            tmp[k++] = a[j++];
        }
    }
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for(i = l, j = 0; i <= r; i++, j++) {
        a[i] = tmp[j];
    }
}
int main() {
    int n;
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> b[i];
    }
    merge_sort(b, 0, n - 1);
    for(int i = 0; i < n; i++) {
        cout << b[i] << " ";
    }
    return 0;
}

顺便通过归并排序还可以求逆序对的对数。某子任务的两个数组，都是单调递增的，只要左侧的数组的第x个数比右侧数组的某个数大，那么这个数到mid之间的所有数，和右面此数剩下的数均为逆序对。在计算这个的时候同样需要进行排序，不能单纯比较，这样才能保证得到符合我们需要的数组。

二分

#include <bits/stdc++.h>
using namespace std;

int low_bsearch(int a[], int l, int r, int x) {
    int flag = -1;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(a[mid] >= x) {
            l = mid + 1;
        } else {
            r = mid;
        }
    
    }
    if(a[l] != x) return -1;
    return l;
}

int up_bsearch(int a[], int l, int r, int x) {
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(a[mid] <= x) {
            l = mid;
        } else
            r = mid - 1;
        
    }
    if(a[l] != x) return -1;
    return r;
}

int main() {
    int n, q;
    ios::sync_with_stdio(false);
    cin >> n >> q;
    int a[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int x;
    for(int i = 0; i < q; i++) {
        cin >> x;
        cout << low_bsearch(a, 0, n - 1, x) << " " << up_bsearch(a, 0, n - 1, x) << "\n";
    }
    return 0;
}

记忆方式如下：

>=对应区间[l,mid],[mid + 1, r]，取第一个大于等于x的下标。 <=对应区间[l,mid - 1],[mid, r]，取第一个小于等于x的下标。

鉴于上面的记不住，还有另一个模板，这个模板是左闭右闭。

int a[];
int bsearch(int l, int r) {
    while (l <= r) {
        int mid = left + right >> 1;
        if(a[mid] >= x) {
            r = mid - 1; 
        } else {
            l = mid + 1;
        } 
    }
    return l;
}//左

int bsearch(int l, int r) {
    while (l <= r) {
        int mid = left + right >> 1;
        if(a[mid] <= x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        } 
    }
    return r;
}//右

假如说想要左侧的，即左逼近，就考虑

立方根，浮点数二分，二分最重要的要知道你分的是什么，最终答案是什么。

#include <bits/stdc++.h>
using namespace std;
int main() {
    double n;
    ios::sync_with_stdio(false);
    cin >> n;
    double l = -40, r = 40;
    while(r - l > 1e-7) {
        double mid = (l + r) / 2;
        if(mid * mid * mid < n) {
            l = mid;
        } else {
            r = mid;
        }
    }
    cout << fixed << setprecision(6) << l << "\n";
}

高精度

属于屁用没用的陈年老东西，但是是练习西巴模拟的好东西。

#include <bits/stdc++.h>
using namespace std;

vector<int> big_add(string x, string y) {
    int lenx = x.size();
    int leny = y.size();
    if(lenx < leny) return big_add(y, x);
    vector<int> a, b, c;
    for(int i = lenx - 1; i >= 0; i--)
        a.push_back(x[i] - '0');
    for(int i = leny - 1; i >= 0; i--)
        b.push_back(y[i] - '0');
    
    int sum = 0;
    for(int i = 0; i < lenx; i++) {
        if (i < leny)
            sum += a[i] + b[i];
        else
            sum += a[i];
        c.push_back(sum % 10);
        sum /= 10;
    }
    if(sum) c.push_back(sum);
    reverse(c.begin(), c.end());
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    string x, y;
    cin >> x >> y;
    auto a = big_add(x, y);
    for(int i = 0;  i < a.size(); i++)
        cout << a[i];
}

#include <bits/stdc++.h>
using namespace std;

bool is_bigger(string x, string y) {
    if(x.size() > y.size()) return true;
    if(x.size() < y.size()) return false;
    for(int i = 0; i < x.size(); i++) {
        if(x[i] > y[i]) return true;
        if(x[i] < y[i]) return false;
    }
    return true;
}

vector<int> big_del(string x, string y) {
    vector<int> a, b, c;
    int lenx = x.size(), leny = y.size();
    for(int i = lenx - 1; i >= 0; i--) a.push_back(x[i] - '0');
    for(int i = leny - 1; i >= 0; i--) b.push_back(y[i] - '0');
    for(int i = 0; i < lenx; i++) {
        if(i < leny) {
            if(a[i] < b[i]) {
                a[i] += 10;
                a[i + 1]--;
            }
            c.push_back(a[i] - b[i]);
        }else {
            if(a[i] < 0) {
                a[i] += 10;
                a[i + 1]--;
            }
            c.push_back(a[i]);
        }
    }
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    reverse(c.begin(), c.end());
    return c;

}

int main() {
    ios::sync_with_stdio(false);
    string x, y;
    cin >> x >> y;
    vector<int> a;
    if(is_bigger(x, y)) {
        a = big_del(x, y);
    }else {
        a = big_del(y, x);
        cout << "-";
    }
    for(auto i : a) cout << i;
}

前缀和

和高中学习的数列一样。

$$ \sum_{i=l}^r a[i] = S[j] - S[i - 1] $$

对于二维数组，不要妄图用一维数组实现

第一步是对从左上角开始的二维矩阵和的表示： $$ \sum_{i=1}^x\sum_{j=1}^y = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + a[i][j]; $$ 然后是对x1,y1,x2,y2矩阵和的表示。

s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]

注意的是我们要把它理解成方块，而不是点，不要忘记各处的-1

差分

差分是前缀和的逆运算，用于对数组进行频繁更改，查询较少情况。

例如对于数组a,若想要从l到r都加上x，我们如果采用循环，更改的复杂度是O(n)的，若采用差分则是O(1)更加合适。

对于差分数组b，数组a，我们有： $$ b[i] = a[i] - a[i-1] $$ 也就是说a是b的前缀和数组。b[i]作用于a[i]及其后面的所有数组。

所以上述l到r都加上x的操作就可以化简为：b[l] + x;b[r + 1] -x。要记得在r之后将操作撤回。

二维差分则不是很好理解。对于差分数组b，数组a仍应该是它的前缀和，对于差分数组我们的构造其实相当于于a全为0再进行更新，只不过范围是一格而已。所以构造和更新是等价的。

#include <bits/stdc++.h>
#define N 1006
using namespace std;
int b[N][N];

void update(int x1, int x2, int y1, int y2, int c) {
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    int tmp;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> tmp;
            update(i,i,j,j,tmp);
        }
    }
    int x1, y1, x2, y2, c;
    while(q-- ) {
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        update(x1, x2, y1, y2, c);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cout << b[i][j] << " ";
        }
        cout << "\n";
    }
}

这种做法只使用一个二维数组。原始的形式如下：

a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];

但是上面代码中的b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]经过不断地迭代已经相当于a这个前缀和数组，只有b[i][j]自己才是差分数组的值。

双指针

也叫做滑动窗口，可以减少一层嵌套的复杂度。

如最长连续子序列（字串）的求出。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+6;
int a[N], cnt[N];

int main() {
    int n, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0, j = 0; i < n; i++) {
        while (j < n && cnt[a[j]] == 0){
            cnt[a[j]]++;
            j++;
        }
        ans = ans > j - i ? ans : j - i;//j指向右侧下一位
        cnt[a[i]]--;
    }
    cout << ans;
}

算法的关键是cnt[a[j]] == 0这个确保了j不会二次访问相同的元素。所以时间复杂度才是O(n)

类似的还有两数之和，三数之和，这两个是左右指针，上面的例子是快慢指针。

lowbit

1
2
3

int lowbit(int x) {
    return x&-x;
}

区间合并

贪心

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
vector<PII> a, ans;

bool operator < (const PII& a, const PII& b) {
    if(a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int l, r;
    while(n--) {
        cin >> l >> r;
        a.push_back({l, r});
    }
    sort(a.begin(), a.end());

    vector<PII>::iterator j = a.begin();
    for(auto i = a.begin(); j != a.end(); i = j) {
        j = i + 1;
        while(j != a.end() && (*i).second >= (*j).first) {
            (*i).second = max((*i).second, (*j).second);
            j++; 
        }
        ans.push_back(*i);
    }
    cout << ans.size();
}

使用erase可能会被卡常数
对于可随机访问的迭代器可以比较大小，双向迭代器不行，注意题中i可能跑到end之后导致陷入死循环，<end也不是很好的写法，j != end是可以的。

数据结构

无stl，我就用数组，我看谁卡我常。

链表

单链表，双链表，典中典反转链表，容易理解难debug的屎。

栈

四个操作，入栈，出栈，是否为空，查询栈顶。

int cstack[114514];
int tt = 0;
cstack[++tt] = num;//push
tt--;//pop;
tt == 0;//empty
cstack[tt];//query

队列

四个操作同上。

int q[114514];
int head = 0, tail = 0;
q[++tail] = num;//入队
head++;//出队
tail >= head //空
q[head];//对头

单调の栈和队列

单调栈用来找某元素离他最近的比他大/小的值。

单调队列则是找一个区间最大/最小的值。

注意这里面的栈和队列存储的都是下标而不是值。

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) {
        while(top && a[ps[top]] >= a[i]) top--;
        if(top) cout << a[ps[top]] << " ";
        else cout << "-1 ";
        ps[++top] = i;//@1
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) {
        if (i - k + 1 > pq[hh]) ++ hh;                  
        // 若队首出窗口，hh加1
        while (hh <= tt && a[i] <= a[pq[tt]]) -- tt;    
        // 若队尾不单调，tt减1&&队列非空
        pq[++ tt] = i;//@2                                 
        // 下标加到队尾
        if (i + 1 >= k) printf("%d ", a[pq[hh]]);       
        // 输出结果
    }
    cout << '\n';
    hh = 0, tt = -1;
    for(int i = 0; i < n; i++) {
        if (i - k + 1 > pq[hh]) ++ hh;                  
        // 若队首出窗口，hh加1
        while (hh <= tt && a[i] >= a[pq[tt]]) -- tt;    
        // 若队尾不单调，tt减1&&队列非空
        pq[++ tt] = i;                                  
        // 下标加到队尾
        if (i + 1 >= k) printf("%d ", a[pq[hh]]);       
        // 输出结果
    }
}

注意@1和@2两行，对于单调栈，我们先查询，再入栈，这是因为这是一个左闭右开的区间，而对于单调队列，我们前入队，再查询，这是因为这个滑动窗口包含两端。

KMP

kmp是双指针算法。某位哲人说，kmp的关键不在于你的顺境，而在于你逆境的时候能否找到原来的自己。我们称原字符串为S长度n，模板串为P长度m。我们求能够匹配的所有下标。

kmp算法一共分为相似的两步，第一步是next数组的生成，第二步是模板串的匹配。我们采用字符串均从1开始的模板进行学习（背诵）。我们进行第一轮模拟，首先，假设两个指针i, j。i之前的j个字符，和模板串的前j个字符相同，但是S[i] != P[j+1]，如果采用暴力的方法，我们只能从i开始进行新一轮的j = 0 -> j = m的循环，最终复杂度变成了O(nm)，这是不好的。

但是我们已知S的[1, i - 1]和P的[1, j]是相等的，并且这两个相等字串都是P的子串，所以我们只需要先考虑这个子串，如果采用暴力的方法我们就会浪费了已知的信息，导致复杂度很高，我们并不想让j从头开始，由此我们引出P串可能存在的性质，从前往后的子串等于一个从后往前的子串，例如aabcabaa，从前往后的aa的从后往前的aa是相等的，我们便可以让i代表的字符作为后面aa的字符构成一个新的子串（所以此时i不代表子串的头），然后再将j退回至前面的aa的位置，而非从头开始进行模板串的比较。

从上面来看，下一步我们的重点就是如何知道P不同长度下前后字符最大的重复个数。但是转念一想我们都知道kmp的时间复杂度是O(n+m)，如果采用暴力的两重循环这不就是m^2了吗，所以这就kmp的难点，next数组的构造。

next数组的用途是如果当前下标不匹配，j应该何去何从。（next数组的含义其实更像before数组）为了化简，我们应当考虑能否想之前P和S之间的比较一样，从已知的信息得到些什么化简复杂度，而不是浪费掉。我们用例子来说明。(同样使用i，j两个指针, i = 2 -> i = m j表示相等子串长度从0开始)。

P = "aabaabaaaa"
ne[1] = 0
ne[2] = 1
ne[3] = 0
ne[4] = 1
ne[5] = 2
ne[6] = 3
ne[7] = 4
ne[8] = 5
ne[9] = 2
ne[10] = 2

这里的子串是不包括自身的，所以ne[1]毫无疑问的是0。如果P[i] == P[j+1]那么我们就顺风顺水地j++并且更新ne数组。但是第一个转折出现在i = 3的时候，（我们拒绝暴力！）此时j = 1, i = 3,但不幸地是P[i] != P[j+1]，但是我们已知ne[i - 1] = 1，我们不必从头再来，可以退而求其次，将j放到i = 2时的情况即j = ne[j] = ne[2] = 1 ，如果还不匹配就一直循环下去，当然最后确实没匹配上，所以ne[3] = 0。

最助于理解的点在i = 9的时候，我们看到ne[9]从ne[8]陡降至2，我们模拟一下，虽然P的第9(i = 9)个和第6(j + 1 = 6)个不相同，但是我们可以考虑前5（j）个里面存在的最长前后相同子串2（ne[5]）个是否能符合条件，但是并不符合，所以我们继续到1（ne[2]）个时终于P[i] == P[j+1]，这时我们再j++并更新数组。

以上我们便假装理解如何构造next数组了，下面进行正式匹配，令i从1开始，j从0开始。

j回滚的条件是S[i] != P[j+1]，我们像最开始说的那样找到子串的最长能相等的前面的那个子串，让j = ne[j]。
j增加的条件是S[i] == P[j+1]，j的下一位和i这一位相同。
输出条件是j == m代表全匹配。

最后给出代码

char s[1000006], p[100006];
int ne[100006];
int main() {
    int n, m;
    cin >> s + 1 >> p + 1;
    m = strlen(s + 1), n = strlen(p + 1);
    ne[1] = 0;
    for(int i = 2, j = 0; i <= n; i++) {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
    
    for(int i = 1, j = 0; i <= m; i++) {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j++;
        if(j == n) {
            cout << i - n + 1 << "\n";
        }
    }
}

并查集

并查集用于进行多次合并集合，查询元素是否在同一集合。缺点就是元素的范围有限。

我们通过存储节点的父节点是谁来实现，令根节点等于自身。

朴素的并查集的查询的时间复杂度取决于树的长度，在密集操作时不是很方便，所以引出第一个优化——压缩路径。当我们搜索某元素的根节点时，我们让它父节点存储的父节点也变成根节点，尽量让树变成菊花图。实现如下:

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

第二个优化，按秩合并，一般来讲作用很小，我们很简单的认为，对于一个元素更少的集合找到根更方便，对另一个合并进去的集合进行路径压缩的时候所需的操作更少。于此同时，我们需要一个数组来进行存储秩的大小。注：cnt数组初始化为1

for(int i = 1; i <= n; i++) p[i] = i, cnt[i] = 1;

void merge(int a, int b) {
    cnt[find(b)] += cnt[find(a)];
    p[find(a)] = find(b);
}

然后就是用并查集存储额外信息，经典例题食物链。注意递归和赋值的顺序。

int find(int x) {
    if(p[x] != x) {
        int tmp = find(p[x]);
        d[x] += d[p[x]];
        p[x] = tmp;
        // d[x] = d[p[x]] + d[x];
        // tmp的作用在压缩路径的同时，也为了更新d[x]的值。
        // d[x] += d[p[x]]; p[x] = find(p[x]); 这个写法是错误的，因为d[x]的值在find(p[x])后应改变。
    }
    return p[x];
}

堆

采用以1开始的idx，这样对于x来讲2 * x是左儿子，2 * x + 1是右儿子。堆的重要操作为3个，一个是up，一个是down，另一个是建堆。

void down(int u) {
    int t = u;
    if(2 * u <= idx && h[2 * u] <= h[t]) t = 2 * u;
    if(2 * u + 1 <= idx && h[2 * u + 1] <= h[t]) t = 2 * u + 1;
    if(t != u) {
        swap(h[t], h[u]);
        down(t);
    }
}

void up(int u) {
    if(u /2 && h[u / 2] > h[u]) {
        swap(h[u], h[u / 2]);
        up(u / 2);
    }
}

//h为堆数组，从n/2开始可以实现O(n)建堆，总操作数为首项为n/2，公比为1/2的无穷级数。
for(int i = 1; i <= n; i++) cin >> h[i];
for(int i = n / 2; i; i--) down(i);

我们实现的操作：

插入，堆末尾加入，一直up上去
删除某个，将其与末尾交换，idx–，然后up,down(实际只会执行一个，这样的减少代码量及思考)
去头，同2，但只需down
编辑，修改然后up,down

哈希

哈希我们通常不需要自己实现，但是要知道原理。最简单的，我们先实现大数的哈希，类似于之前的离散化操作，但这是更为普遍的，操作也受限，只能查询是否存在。

有两种方法：

拉链法

拉链法，通过单链表实现，我们将数模上一个数，然后使其为头节点，如果该头节点存在下一个节点则证明哈希碰撞，我们采用头插法，插入这个数。

int e[M], ne[M], h[M], idx;
int insert(int x) {
    int k = (x % M + M) % M;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}
//输入n个数均小于N，(n远小于N)
//此处M为大于n的最小质数

//查询操作
bool find(int x) {
    int k = (x % M + M) % M;
    for(int i = h[k]; i != -1; i = ne[i])
        if(e[i] == x)
            return true;
    return false;
}

开放寻址法

不同于拉链法，这种方法开两到三倍n大小的数组，同样模上一个数，如果冲突则向后移动至不冲突为止，如果到末尾则从头开始。改方法实现的关键是返回hash数组的下标。

const int N = 2e5+3;
int h[N], null = 0x3f3f3f3f;
int find(int x) {
    int k = (x % N + N) % N;
    while(h[k] != null && h[k] != x) {
        k ++;
        if(k == N) k = 0;
    }
    return k;
}
//找下标
int k = find(x);
//插入x
h[k] = x;
//是否存在
h[k] == null //不存在,反之

然后我们学习更难一点的字符串哈希，我们限制其为ASCII码范围。我们实现的功能是判断两个子串是否相等。

将字符串化为P进制整数(P为经验值131或13331)，左为高位，右为低位。
我们从下标1存储字符串，实现求[L, R]的哈希值，类似于前缀和的思想，我们可以很容易的知道[0, R]的哈希值，然后我们只需要用[0, R] - [0, L - 1]即可，但是并非直接相见，因为位数没有对其，因此我们将L-1乘上对应P次方再相减。
P次方运用过于频繁，所以通过预处理jian’hua

#include <iostream>
using namespace std;
typedef unsigned long long ull;
const int N = 1e5+6;
char str[N];
ull p[N], h[N];
int P = 131;

ull strtohash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    int n, m;
    cin >> n >> m >> str + 1;
    p[0] = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }
    while(m--) {
        int l1,r1,l2,r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(strtohash(l1, r1) == strtohash(l2, r2)) cout << "Yes" << '\n';
        else cout << "No" << '\n';
        
    }
}

图&树

对于无向图可以视作双向有向图，对于树，也可以视作图。

所以我们将这两者的存储简化成有向图的存储。对于稠密图可以采用邻接矩阵的方法，但是通常我们只采用邻接表来做题。

邻接表本质上就是n个单链表，我们存储n个头节点，然后得知节点通向何处。

以下时最基本的加边操作。

const int N = 1e5+6;
int h[N], e[N], ne[2*N], idx;
memeset(h, -1, sizeof h);
void add(int a, int b) { // a->b
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

搜索

图论

拓扑排序

结论：有向无环图一定存在，有环图一定不存在

感觉说人话就是不重复的遍历一遍整个图。

思路：

找到入度为0的点
将此点加入答案容器，遍历其出边，并将指向节点的入度-1，若此时节点入度也为0则加入队列
结束时如果答容器元素个数等于节点数则输出，否则返回不存在

拓展：如何输出最大/最小字典序的拓扑排序。

最短路

朴素dijkstra

dijkstra均不能存在负权边。该算法基于贪心的思想，我不会证明。

进行n次循环（或n-1次），每次循环可确定一个点到起点最短。

实现如下：

找到未确认到起点最短距离的点

int t = -1;
for(int j = 1; j <= n; j++){
    if(!s[j] && ( t == -1 || dist[j] < dist[t]) ) {
        t = j;
    }
}

通过此点更新其它点到起点的距离

1
2

for(int j = 1; j <= n; j++)
    dist[j] = min(dist[j], dist[t] + g[t][j]);

标记其为已确定s[t] = true;

需要注意的，我们最好将t == -1利用c语言逻辑短路的性质写在dist[j] < dist[t]前面，减少不必要的越界，然后对于两点之间不联通的情况，我们即可以特判，也可以像多数情况在建图的时候将图的距离初始化为一个大于最大权的数，保证加上权后不会溢出，这样永远不会成为min值。

对于上面提到的n-1次是因为倒数第二次循环已经可以确定到终点的距离，以1到n为例，最后求的dist[n]无非就是起点到1~n-1的距离加上到点n的权。

堆优化dijkstra

我们不难发现最耗时的是上面提到的第1步，想要持续找到最小值，我们联想到堆这个结构，只需O(1)就可以实现，但是有得有失，我们第2步的修改便变成了logn复杂度。

首先我们采用带权邻接表存图

void add(int a, int b, int c) {
    e[idx] = b;   
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

然后是stl优先队列的定义

typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII> > heap;
//pair先比first，然后比second，默认存在比较重载，然后我们需要小根堆
//fist我们存距离，second我们存节点

然后是朴素dijkstra的第2步等效实现。

dist[1] = 0;
heap.push({0, 1});
while(heap.size()) {
    auto t = heap.top();heap.pop();
    int v = t.second;// dis = t.first;
    if(!s[v]) {
        s[v] = true;
        for(int i = h[v]; i != -1; i = ne[i]) {
            int j = e[i];
            if(dist[j] > dist[v] + w[i]) {
                dist[j] = dist[v] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

bellman-ford

基于动态规划的O(nm)复杂度算法。核心操作是松弛。设dist数组存到起点距离，初始化dist[起点] = 0，对于一条加权边,dist[b] = min(dist[b], dist[a] + w)。

我们总共需要进行n-1轮松弛，每k轮可以确定经过k条边的最短路。所以我们可以特殊地求出最多经过k条边时地最短路。但是我们要注意，更新的时候不能直接用dist更新，应该用上一次的dist数组，防止同一次循环中一次更新对下一次更新造成影响。

注意：对于未联通的边可能存在0x3f3f3f3f加上负权边导致dist[终点]不再是定义中的无限大，所以我们要通过类似dist[终点] > 0x3f3f3f3f / 2来判断是否存在最短路。

SPFA

基于队列的bellman-ford算法，复杂度一般为O(km),最坏退化O(nm)。

通过一个队列存储哪些点被更新了，进而减少操作，此外我们需要一个bool数组来避免重复入队。

我们还可以用SPFA求负环。

和bf求负环一样利用抽屉原理，如果我们到一个点用了n条边，证明经过了n + 1个点说明存在负环，所以我们利用cnt数组来记录。

并且此时我们无需初始化dist数组为无穷大，和起始dist为0，因为只要存在负环就一定会更新。（突然发现两个操作要是都做就相当于没做！）

SPFA_DFS（todo）

Floyd

求多元最短路，用于稠密图（此时比dijkstra复杂度低），O(n^3)复杂度。允许负权，不允许负环。

三重循环，第一重是使用1~k节点，第二三重i,j无影响可互换，表示从第i到第j。我们可以得到递推表达式d[k][i][j] = min(d[k - 1][i][j], d[k - 1][i][k] + d[k - 1][k][j])。但是我们只用到了k-1的层的数据，所以可以化简为二维去掉k层。（dp深坑todo）。

最小生成树

最小生成树不应出现自环，建图的时候要注意。

朴素prim

用于稠密图。

和dijkstra类似，但是与松弛操作不同的是dist表示的是未确定的点到这个已经建树集合距离最小的点。

注意prim需要迭代n次，因为本质上每一次确定是是一个点，而非一个边。并且不需要初始化dist[起点]为0。(其实也不是不行，否则判断短路的时候就需要看是否是第一次)，然后要注意最后答案是ans，不是dist[n]了。

int ans = 0;
dist[1] = 0;//可去掉
for(int i = 0; i < n; i++) {
    int t = -1;
    for(int j = 1; j <= n; j++) {
        if(!s[j] && (t == -1 || dist[j] < dist[t])) t = j;
    }

    if(dist[t] == 0x3f3f3f3f) {//上面去掉后这里变成(i && dist[t] == 0x3f3f3f3f)
        cout << "impossible";
        return 0;
    }

    s[t] = true;
    if(i) ans += dist[t];

    for(int j = 1; j <= n; j++) {
        dist[j] = min(dist[j], g[t][j]);
    }

}

cout << ans;

kruskal

将所有边按权排序
枚举每条边，如果a,b不连通将其加入集合。（通过并查集实现）

二分图

首先要明白什么是二分图。

染色法判断

开始对任意一未染色的顶点染色。
判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。
若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。

深搜广搜均可。

匈牙利算法

目的是找最大匹配

我们将二分图抽象为男女找对象，对于男生，我们遍历其喜欢的女生，如果单身，就将女生对象标记成它。对于女生，如果她有新的追求者，就看原先的对象有没有备胎，如果有备胎就让他找备胎去，否则保留原来的对象。

我们需要match[] int数组标记女生的对象，vis[] bool数组标记每一轮女生是否被遍历过。

数论

质数

约数

欧拉函数

快速幂

想要求a ^ b。对于朴素我们逐个乘是O(n)的，但是我们可以通过二进制表示b来减少不必要的乘法，将其优化至对数级。

对于b，我们一定可以将其写成二进制的形式，所以 $$ a^b = a^{\log_{2}{2^b}} \ 2^b = 2^x * 2^y * … * 2^k*… $$ 通过b&1判断最低位是否为1，通过>>=1来去掉最低位。这样复杂度就变成了b的二进制位数。

int qm(int a, int b, int p) {
    int res = 1;
    while(b) {
        if(b&1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}

数据结构

树状数组

前缀和和差分只能实现查询修改二者之一的O(1)复杂度，而树状数组是会折中的，全变成了O(logn)!

注：树状数组的下标通常是从1开始的。这是因为在树状数组的数据结构中，每个节点表示的是其所有子节点的数据之和，而子节点的数量是通过二进制位来表示的。从1开始下标可以方便地使用位运算来计算子节点的位置和数量。

可知我们要实现的操作时区间求和，单点修改。

对于数组a[1],….,a[n],我们可以相邻两项求和存到另一层数组，并且逐渐递推直至只有一项（最终形成一个很多层的数组，即线段树），这样我们想要求区间和就会减少一些复杂度，但是我们会发现，当我们想要求a[1]到a[k]的和时，处于偶数位置的各层数组的元素都是没有必要的，所以我们便将其删去，这时我们惊奇地发现剩下的个数刚好是n个，这便是树状数组。

下面我们来实现区间求和，根据上面我们已知偶数位置存储的是区间和，奇数位置存的是原始数组的值，对于从a[1]到a[k]的和，我们可以将k用二进制来表示，例如7 = (111)~2~,我们需要求的区间长度便为4+2+1，但是对于这个长度为2的区间在4之后，同理1又在2+4之后，所以我们求的是a[4] + a[6] + a[7]，这不巧了吗，就是k不断减去lowbit(k)的过程。

int query(int n) {
    int ans = 0;
    for(int i = n; i; i -= lowbit(i)) ans += a[i];
    return ans;
}

然后我们再来实现单点修改（和之前的差分类似，建立数组的过程也就是将0数组不断单点修改的过程）。

int a[MAXN+1];
void add(int idx, int x) {
    for(int i = idx; i <= MAXN; i += lowbit(i)) 
        a[i] += x;
}

因为最终的目的是将该贡献加到最后一位，二进制表示为100000…000，所以我们将最右侧的1再加上1（即lowbit，如100100+100）直至达到末尾。

线段树

线段树是树状数组的plus版本，支持区间修改（虽然树状数组差分也可以实现），但是和树状数组所不同的是，线段树是从上向下建树，而不是从单点反馈到整体的过程。当然其也存在缺点，需要4n的空间（也有2n的神奇写法），先对为什么需要4n的空间进行简要说明。

对于一个二叉树来讲，如果它是完全二叉树，最底层的个数为m的情况下，一共能存n = 2*m - 1个节点。当然线段树并不是完全二叉树，但是我们既然要完整地存储所有的数据，就一定要保证空间足够。分两种情况讨论(n为输入数组长度, N为开辟数组长度)：

当n = 2^k的时候，巧了它就是完全二叉树，所以N = 2n > 2n - 1，这种情况下2n就足够了
但n = 2^k + x的时候，就相当于上面那种情况再加上一层，我们在N = 4n的时候，能够保证存的下。

建树：

void build(int p, int l, int r) {
    //以p为父节点，对[l,r]这个闭区间建立线段树
    if(l == r) {
        f[p] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
    //按照[l, mid],[mid+1, r]的方式建树
    f[p] = f[p<<1] + f[p<<1|1];
}

单点修改:

void add(int p, int l, int r, int x, int dx) {
    //单点修改
    //p为当前节点，[l,r]为当前节点的区间，
    //x为要修改的位置，dx为修改的值
    f[p] += dx;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) add(p<<1, l, mid, x, dx);
    else add(p<<1|1, mid+1, r, x, dx);
}

查询区间和:

int query_sum(int p, int l, int r, int s, int e) {
    //查询区间和
    //p为当前节点，[l,r]为当前节点的区间
    //求[s,e]的区间和

    if(l == s && r == e) {
        return f[p];
    }
    int mid = (l + r) >> 1;
    if(e <= mid) 
        return query_sum(p<<1, l, mid, s, e);
    else if(s > mid) 
        return query_sum(p<<1|1, mid+1, r, s, e);
    else 
        return query_sum(p<<1, l, mid, s, mid) 
            + query_sum(p<<1|1, mid+1, r, mid+1, e);

}

可是我们发现，上面这些功能还不如用树状数组实现呢，下面是如何进行区间修改。

第一种是引入一个数组v[4*N]来记录修改值，但标记不下传。

这也是所谓的标记永久化操作。

区间修改：

void add_interval(int p, int l, int r, int s, int e, int dx) {
    //区间修改
    //p为当前节点，[l,r]为当前节点的区间
    //[s,e]为要修改的区间，dx为修改的值
    if(l == s && r == e) {
        v[p] += dx;
        return;
    }
    f[p] += dx * (e - s + 1);
    int mid = (l + r) >> 1;
    if(e <= mid) 
        add_interval(p<<1, l, mid, s, e, dx);
    else if(s > mid) 
        add_interval(p<<1|1, mid+1, r, s, e, dx);
    else {
        add_interval(p<<1, l, mid, s, mid, dx);
        add_interval(p<<1|1, mid+1, r, mid+1, e, dx);
    }
}

注意！！！f[p]代表的是[l,r]的和，而v[p]是[l,r]的修改值，所以v[p]只改了一次(并且还是在尽量少的操作下O(logn))，而f[p]才是不断更新的；

区间求和:

long long interval_sum(int p, int l, int r, int s, int e, long long vsum = 0) {
    //区间查询
    //p为当前节点，[l,r]为当前节点的区间
    //[s,e]为要查询的区间，v为当前节点的懒标记
    vsum += v[p];
    if(l == s && r == e) {
        return f[p] + vsum * (e - s + 1);
    }
    int mid = (l + r) >> 1;
    if(e <= mid) 
        return interval_sum(p<<1, l, mid, s, e, vsum);
    else if(s > mid) 
        return interval_sum(p<<1|1, mid+1, r, s, e, vsum);
    else 
        return interval_sum(p<<1, l, mid, s, mid, vsum) 
            + interval_sum(p<<1|1, mid+1, r, mid+1, e, vsum);
}

然后我有一个疑问啊，既然有了+ vsum * (r - l + 1)那区间修改中f[p] += dx * (e - s + 1);还有什么用呢。通过举例理解，最极端的，l = s = 1, r = e = n，然后我们对其中l < s < e < r 的区间进行修改，这时v[1]是0，区间的更新靠的还是f[p]而不是v[x]，由此可以推出还是有用的。

第二种是经典的懒标记下放。

相对于最朴素的版本多了pushup和pushdown的操作,相对于第一种求区间时减少了vsum这个参数。

void pushup(int p) {
    //更新父节点的值
    f[p] = f[p<<1] + f[p<<1|1];
}

void pushdown(int p, int l, int r) {
    //下放懒标记
    int mid = (l + r) >> 1;
    v[p<<1] += v[p];
    v[p<<1|1] += v[p];
    
    f[p<<1] += v[p] * (mid - l + 1);
    f[p<<1|1] += v[p] * (r - mid);

    v[p] = 0;
}

然后相对于第一种的变化一个是区间改变的时候之后在l=s, r=e的情况下才对f[p]进行更新，因为它的懒标记是不断下放的，最后统一pushup回来。然后就是所谓老生常谈的，能增加代码量就尽量减少思考量，所以我们在查询和修改中都进行pushdown和pushup的操作，这样保证了只要有需要的情况下一定会执行，多执行对结果也没有任何影响（和堆的up down一样懒）。

void add_interval(int p, int l, int r, int x, int y, int k) {
    //区间修改
    //p为当前节点，[l,r]为当前节点的区间
    //[x,y]为要修改的区间，k为修改的值
    if(l == x && r == y) {
        v[p] += k;
        s[p] += k * (y - x + 1);
        return;
    }
    if(v[p]) pushdown(p, l, r);
    int m = l + ((r - l) >> 1);
    if(x <= m) add_interval(p<<1, l, m, x, min(m, y), k);
    if(y > m) add_interval(p<<1|1, m + 1, r, max(m+1, x), y, k);
    pushup(p);
}

long long query(int p,int l, int r, int x, int y) {
    //区间查询
    //p为当前节点，[l,r]为当前节点的区间
    //[x, y]为要查询的区间，v为当前节点的懒标记
    if(l == x && r == y) {
        return s[p];
    }
    if(v[p]) pushdown(p, l, r);
    int m = l + ((r - l) >> 1);
    long long ans = 0;
    if(x <= m) ans += query(p<<1, l, m, x, min(m, y));
    if(y > m) ans += query(p<<1|1, m + 1, r, max(m+1, x), y);
    return ans;
}

最后是关于pushdown的一个问题，以区间加和为例里面sum加的是这个数乘上该节点区间长度，而和当初输入的想要改变的区间毫无关系，这就回到了lazytag的定义上，它代表着节点指向的整个区间被修改，并且它的子区间尚并未被修改。