模板

模板 2.0

备忘录：

1. 线段树模板查询query和更新update操作初始化l, r, root默认值

2. Z函数、 KMP求循环节

关闭同步输入输出流

ios::sync_with_stdio(false)

控制小数位数

#include <iomanip>
cout<<fixed<<setprecision(6)<<res<<endl;

局部排序函数

partial_sort(a + 1, a + 1 + 20, a + n + 1, greater<int>());
partial_sort(a.begin(), a.begin() + 20, a.end(), greater<int>());

归并排序（求逆序对个数）

int a[N], tmp[N];

ll mergesort(int p[], int l, int r)
{
    if(l >= r) return 0;
    int mid = l + r >> 1;
    ll res = 0;
    res += mergesort(p, l, mid) + mergesort(p, mid + 1, r);
    int k = 1, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(p[i] <= p[j]) tmp[k ++] = p[i ++];
        else tmp[k ++] = p[j ++], res += mid - i + 1;
    }
    while(i <= mid) tmp[k ++] = p[i ++];
    while(j <= r) tmp[k ++] = p[j ++];
    for(int i = l, j = 1;i <= r;i ++, j ++) p[i] = tmp[j];
    return res;
}

快速排序

int a[N];

void quicksort(int p[], int l, int r)
{
    if(l >= r) return;
    int x = p[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i ++; while(p[i] < x);
        do j --; while(p[j] > x);
        if(i < j) swap(p[i], p[j]);
    }
    quicksort(p, l, j);
    quicksort(p, j + 1, r);
}

高精度加法

vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int>C;
    int t = 0;
    for(int i = 0;i < A.size() || i < B.size();i ++)
    {
        if(i < A.size()) t += A[i];
        if(i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if(t) C.push_back(t);
    return C;
}

int main()
{
    string a, b; cin>>a>>b;
    vector<int> A, B;
    for(int i = a.length() - 1;i >= 0;i --) A.push_back(a[i] - '0');
    for(int i = b.length() - 1;i >= 0;i --) B.push_back(b[i] - '0');
    auto C = add(A, B);
    for(int i = C.size() - 1;i >= 0;i --) cout<<C[i]; cout<<endl;
    return 0;
}

高精度减法

vector<int> cub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0;i < A.size() || i < B.size();i ++)
    {
        if(i < A.size()) t += A[i];
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if(t < 0) t = -1;
        else t = 0;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a, b; cin>>a>>b;
    vector<int> A, B;
    for(int i = a.length() - 1;i >= 0;i --) A.push_back(a[i] - '0');
    for(int i = b.length() - 1;i >= 0;i --) B.push_back(b[i] - '0');
    if(a.length() < b.length() || (a.length() == b.length() && a < b))
    {
        auto C = cub(B, A);
        cout<<"-";
        for(int i = C.size() - 1;i >= 0;i --) cout<<C[i]; cout<<endl;
    }
    else
    {
        auto C = cub(A, B);
        for(int i = C.size() - 1;i >= 0;i --) cout<<C[i]; cout<<endl;
    }
    return 0;
}

高精度乘法

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for(int i = 0;i < A.size() || t;i ++)
    {
        if(i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    int b;
    cin>>a>>b;
    vector<int>A;
    for(int i = a.length() - 1;i >= 0;i --) A.push_back(a[i] - '0');
    auto C = mul(A, b);
    for(int i = C.size() - 1;i >= 0;i --) cout<<C[i];
    cout<<endl;
    return 0;
}

高精度除法

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for(int i = A.size() - 1;i >= 0;i --)
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    int b, r;
    cin>>a>>b;
    vector<int>A;
    for(int i = a.length() - 1;i >= 0;i --) A.push_back(a[i] - '0');
    auto C = div(A, b, r);
    for(int i = C.size() - 1;i >= 0;i --) cout<<C[i];
    cout<<endl<<r<<endl;
    return 0;
}

二维差分

int a[N][N], pre[N][N];

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

int main()
{
    int n, m, q; cin>>n>>m>>q;
    for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++) cin>>a[i][j];
    for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++) insert(i, j, i, j, a[i][j]);
    for(int i = 1;i <= q;i ++)
    {
        int x1, y1, x2, y2, c; cin>>x1>>y1>>x2>>y2>>c;
        insert(x1, y1, x2, y2, c);
    }
    for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++)
        pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
    for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++)
        cout<<pre[i][j]<<(j == m ? '\n' : ' ');
    return 0;
}

离散化

int find(int x) {return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;}

sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

KMP

int nx[N];

int main()
{
    int n, m;
    string p, s;
    cin>>n>>p>>m>>s;
    p = '_' + p; s = '_' + s;

    for(int i = 2, j = 0;i <= n;i++)
    {
        while(j && p[i] != p[j + 1]) j = nx[j];
        if(p[i] == p[j + 1]) j ++;
        nx[i] = j;
    }

    for(int i = 1, j = 0;i <= m;i ++)
    {
        while(j && s[i] != p[j + 1]) j = nx[j];
        if(s[i] == p[j + 1]) j ++;
        if(j == n) cout<<i - n<<" ", j = nx[j];
    }
    return 0;
}

扩展KMP

char a[N], b[N];
int z[N], p[N];

// b 的 Z函数，即 b 与 b 的每一个后缀的 LCP 长度。
inline void Z(char *s, int n)
{
    for(int i = 1;i <= n;i ++) z[i] = 0;
    z[1] = n;
    for(int i = 2, l = 0, r = 0;i <= n;i ++)
    {
        if(i <= r) z[i] = min(z[i - l + 1], r - i + 1);
        while(i + z[i] <= n && s[i + z[i]] == s[z[i] + 1]) ++ z[i];
        if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
}

// b 与 a 的每一个后缀的 LCP 长度。
inline void exkmp(char *s, int n, char *t, int m)
{
    Z(t, m);
    for(int i = 1;i <= n;i ++) p[i] = 0;
    for(int i = 1, l = 0, r = 0;i <= n;i ++)
    {
        if(i <= r) p[i] = min(z[i - l + 1], r - i + 1);
        while(i + p[i] <= n && s[i + p[i]] == t[p[i] + 1]) ++ p[i];
        if(i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
    }
}

main()
{
    scanf("%s%s", a + 1, b + 1);
    int n = strlen(a + 1), m = strlen(b + 1);
    exkmp(a, n, b, m);
}

字典树

int son[N][26], cnt[N], idx;

void insert(string s)
{
    int p = 0;
    for(auto &c : s)
    {
        if(!son[p][c - 'a']) son[p][c - 'a'] = ++ idx;
        p = son[p][c - 'a'];
    }
    cnt[p] ++;
}

int query(string s)
{
    int p = 0;
    for(auto &c : s)
    {
        if(!son[p][c - 'a']) return 0;
        p = son[p][c - 'a'];
    }
    return cnt[p];
}

并查集

int parent[N];

int find_root(int x)
{
    if(parent[x] != x) parent[x] = find_root(parent[x]);
    return parent[x];
}

//初始化
for(int i = 1;i <= n;i ++) parent[i] = i;

//合并
parent[find_root(a)] = find_root(b);

模拟堆

int heap[N], idx;

void push_up(int x)
{
    while(x / 2 && heap[x / 2] > heap[x])
    {
        swap(x, x / 2);
        x >>= 1;
    }
}

void push_down(int x)
{
    int t = x;
    if(x * 2 <= idx && heap[x * 2] < heap[t]) t = x * 2;
    if(x * 2 + 1 <= idx && heap[x * 2 + 1] < heap[t]) t = x * 2 + 1;
    if(t != x)
    {
        swap(t, x);
        push_down(t);
    }
}

字符串双重哈希

class HASH
{
    vector<ull> hs, pn;
    int n, p = 131;
public:
    HASH(string s)
    {
        n = s.length();
        hs.resize(n + 1);
        pn.resize(n + 1);
        pn[0] = 1;
        for(int i = 1;i <= n;i ++)
        {
            hs[i] = hs[i - 1] * p + s[i - 1];
            pn[i] = pn[i - 1] * p;
        }
    }
    // 获得l - r区间上字符串的哈希值
    int gethash(int l, int r)
    {
        if(l > r) return 0ll;
        return hs[r] - hs[l - 1] * pn[r - l + 1];
    }
};

树的重心

int n, ans = 1e5 + 10;
bool vis[N];
vector<int> e[N];

int dfs(int u)
{
    vis[u] = true;
    int sum = 1, mx = 0;
    for(int i = 0;i < e[u].size();i ++)
    {
        int v = e[u][i];
        if(!vis[v])
        {
            int temp = dfs(v);
            mx = max(mx, temp);
            sum += temp;
        }
    }

    mx = max(mx, n - sum);
    ans = min(ans, mx);

    return sum;
}

拓扑排序

int n, m, indeg[N], ans[N], cnt;
vector<int> e[N];

bool topsort()
{
    queue<int> que;
    for(int i = 1;i <= n;i ++) if(!indeg[i]) que.push(i);
    while(!que.empty())
    {
        int u = que.front(); que.pop();
        ans[++ cnt] = u;
        for(int i = 0;i < e[u].size();i ++)
        {
            int v = e[u][i];
            indeg[v] --;
            if(!indeg[v]) que.push(v);
        }
    }
    return cnt == n;
}

朴素dijkstra

const int inf = 0x3f3f3f3f;

int a[N][N], dis[N], n, m;
bool vis[N];

int dijkstra()
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dis[1] = 0;
    for(int i = 1;i <= n;i ++)
    {
        int idx = 0;
        for(int j = 1;j <= n;j ++) if(!vis[j] && dis[j] <= dis[idx]) idx = j;
        vis[idx] = true;
        for(int j = 1;j <= n;j ++) if(dis[idx] + a[idx][j] < dis[j]) dis[j] = dis[idx] + a[idx][j];
    }
    return dis[n];
}

堆优化dijkstra

int n, m, dis[N];
bool vis[N];
vector<pair<int, int>> e[N];

int dijkstra(int start)
{
    memset(dis, 0x3f, sizeof dis);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    dis[start] = 0;
    heap.push({0, start});
    while(!heap.empty())
    {
        int u = heap.top().second; heap.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = 0;i < e[u].size();i ++)
        {
            int v = e[u][i].first, wi = e[u][i].second;
            if(dis[u] + wi < dis[v]) dis[v] = dis[u] + wi, heap.push({dis[v], v});
        }
    }
    return dis[n];
}

bellman-ford

const int inf = 0x3f3f3f3f;

struct node
{
    int u, v, w;
}edge[M];

int n, m, k, dis[N], updis[N];

int bellman_ford()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    for(int i = 1;i <= k;i ++)
    {
        memcpy(updis, dis, sizeof dis);
        for(int j = 1;j <= m;j ++)
            if(updis[edge[j].u] + edge[j].w < dis[edge[j].v])
                dis[edge[j].v] = updis[edge[j].u] + edge[j].w;
    }
    return dis[n];
}

SPFA最短路

int dis[N], n, m;
bool vis[N];
vector<pair<int, int>> e[N];

int spfa(int start)
{
    memset(dis, 0x3f, sizeof dis);
    queue<int> que;
    que.push(start);
    dis[start] = 0;
    while(!que.empty())
    {
        int u = que.front(); que.pop();
        vis[u] = false;
        for(int i = 0;i < e[u].size();i ++)
        {
            int v = e[u][i].first, wi = e[u][i].second;
            if(dis[u] + wi < dis[v])
            {
                dis[v] = dis[u] + wi;
                if(!vis[v]) que.push(v), vis[v] = true;
            }
        }
    }
    return dis[n];
}

SPFA判负环

int dis[N], cnt[N], n, m;
bool vis[N];
vector<pair<int, int>> e[N];

bool spfa()
{
    queue<int> que;
    for(int i = 1;i <= n;i ++) que.push(i), vis[i] = true;
    while(!que.empty())
    {
        int u = que.front(); que.pop();
        vis[u] = false;
        for(int i = 0;i < e[u].size();i ++)
        {
            int v = e[u][i].first, wi = e[u][i].second;
            if(dis[u] + wi < dis[v])
            {
                dis[v] = dis[u] + wi;
                cnt[v] = cnt[u] + 1;
                if(cnt[v] >= n) return true;
                if(!vis[v]) que.push(v), vis[v] = true;
            }
        }
    }
    return false;
}

Floyd最短路

const int inf = 0x3f3f3f3f;

int dis[N][N], n, m, k;

void floyd()
{
    for(int k = 1;k <= n;k ++)
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

朴素prim最小生成树

const int inf = 0x3f3f3f3f;

int e[N][N], dis[N], n, m;
bool vis[N];

int prim()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    int res = 0;
    for(int i = 1;i <= n;i ++)
    {
        int idx = 0;
        for(int j = 1;j <= n;j ++) if(!vis[j] && dis[j] < dis[idx]) idx = j;
        if(idx == 0) return -1;
        vis[idx] = true;
        res += dis[idx];
        for(int j = 1;j <= n;j ++) if(e[idx][j] < dis[j]) dis[j] = e[idx][j];
    }
    return res;
}

堆优化prim最小生成树

int dis[N], n, m;
bool vis[N];
vector<pair<int, int>> e[N];

int prim()
{
    memset(dis, 0x3f, sizeof dis);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    dis[1] = 0;
    heap.push({0, 1});
    int res = 0, cnt = 0;
    while(!heap.empty())
    {
        int u = heap.top().second; heap.pop();
        if(vis[u]) continue;
        vis[u] = true;
        res += dis[u];
        cnt ++;
        for(int i = 0;i < e[u].size();i ++)
        {
            int v = e[u][i].first, wi = e[u][i].second;
            if(!vis[v] && wi < dis[v])
            {
                dis[v] = wi;
                heap.push({dis[v], v});
            }
        }
    }
    if(cnt < n) return -1;
    return res;
}

kruskal 最小生成树

int parent[N];
struct node
{
    int u, v, w;
    bool operator< (const node &y)const{
        return w < y.w;
    }
}e[M];

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

int main()
{
    int n, m; cin>>n>>m;
    for(int i = 1;i <= n;i ++) parent[i] = i;
    for(int i = 1;i <= m;i ++) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e + 1, e + m + 1);
    int res = 0, cnt = 0;
    for(int i = 1;i <= m;i ++)
    {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if(find(u) == find(v)) continue;
        parent[find(u)] = find(v);
        res += w;
        cnt ++;
    }
    if(cnt == n - 1) cout<<res<<endl;
    else cout<<"impossible"<<endl;
    return 0;
}

二分图判断

int head[N], e[M], nx[M], idx = 1;
int col[N], n, m;

void add(int u, int v)
{
    e[idx] = v;
    nx[idx] = head[u];
    head[u] = idx ++;
}

bool dfs(int u, int c)
{
    col[u] = c;
    for(int i = head[u];~i;i = nx[i])
    {
        int v = e[i];
        if(!col[v]) dfs(v, 3 - c);
        if(col[u] == col[v]) return false;
    }
    return true;
}

int main()
{
    memset(head, -1, sizeof head);
    cin>>n>>m;
    for(int i = 1;i <= m;i ++)
    {
        int u, v; cin>>u>>v;
        add(u, v); add(v, u);
    }
    bool flag = true;
    for(int i = 1;i <= n;i ++)
    {
        if(!col[i] && !dfs(i, 1))
        {
            flag = false;
            break;
        }
    }
    if(flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

匈牙利算法

int head[N], e[M], nx[M], idx = 1;
int n, ns, m, match[N];
bool vis[N];

void add(int u, int v)
{
    e[idx] = v;
    nx[idx] = head[u];
    head[u] = idx ++;
}

bool find(int u)
{
    for(int i = head[u];~i;i = nx[i])
    {
        int v = e[i];
        if(!vis[v])
        {
            vis[v] = true;
            if(match[v] == 0 || find(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int query()
{
    int res = 0;
    for(int i = 1;i <= n;i ++)
    {
        memset(vis, 0, sizeof vis);
        if(find(i)) res ++;
    }
    return res;
}

int main()
{
    memset(head, -1, sizeof head);
    cin>>n>>ns>>m;
    for(int i = 1;i <= m;i ++)
    {
        int u, v; cin>>u>>v;
        add(u, v);
    }
    cout<<query()<<endl;
    return 0;
}

欧拉路径 点序列(有向图-vector)

int del[N];
int deg[N][2];
stack<int> st;
vector<int> e[N];

void dfs(int now)
{
    for(int i = del[now];i < e[now].size();i = del[now])
    {
        del[now] = i + 1;
        dfs(e[now][i]);
    }
    st.push(now);
}

void solve()
{
    int n, m; cin>>n>>m;
    for(int i = 1;i <= m;i ++)
    {
        int u, v; cin>>u>>v;
        e[u].push_back(v);
        deg[u][1] ++; deg[v][0] ++;
    }
    for(int i = 1;i <= n;i ++) sort(e[i].begin(), e[i].end());
    // 有向图欧拉路径判断
    int start = 1, cnt[2] = {0};
    bool flag = true;
    for(int i = 1;i <= n;i ++)
    {
        if(deg[i][1] != deg[i][0]) flag = false;
        if(deg[i][1] - deg[i][0] == 1) cnt[1] ++, start = i;
        if(deg[i][0] - deg[i][1] == 1) cnt[0] ++;
    }
    if(!flag && !(cnt[0] == cnt[1] && cnt[0] == 1)) {cout<<"No"<<endl; return;}
    dfs(start);
    while(!st.empty()) cout<<st.top()<<" ", st.pop();
    cout<<endl;
}

欧拉回路 边序列(有向图链式前向星)

int h[N], e[M], ne[M], idx;
int deg[N][2];
bool used[M];
stack<int> st;

void add(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx ++;
}

void dfs(int now)
{
    for(int &i = h[now];~i;)
    {
        if(used[i]) {i = ne[i]; continue;}
        used[i] = true;
        
        int temp = i + 1;
        
        int j = e[i];
        i = ne[i];
        dfs(j);
        
        st.push(temp);
    }
}

signed main()
{
    int n, m; cin>>n>>m;
    for(int i = 1;i <= n;i ++) h[i] = -1;
    for(int i = 1;i <= m;i ++)
    {
        int u, v; cin>>u>>v;
        add(u, v);
        deg[u][1] ++;
        deg[v][0] ++;
    }
    // 有向图欧拉回路判断
    for(int i = 1;i <= n;i ++)
        if(deg[i][0] != deg[i][1]) {cout<<"NO"<<endl; return 0;}
    
    for(int i = 1;i <= n;i ++)
        if(h[i] != -1) {dfs(i); break;}
    
    if(st.size() < m) cout<<"NO"<<endl;
    else
    {
        cout<<"YES"<<endl;
        while(!st.empty()) cout<<st.top()<<" ", st.pop();
        cout<<endl;
    }
    
    return 0;
}

欧拉回路 边序列(无向图链式前向星)

int h[N], e[M], ne[M], idx;
int deg[N][2];
bool used[M];
stack<int> st;

void add(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx ++;
}

void dfs(int now)
{
    for(int &i = h[now];~i;)
    {
        if(used[i]) {i = ne[i]; continue;}
        used[i] = true; used[i ^ 1] = true;

        int temp;
        temp = i / 2 + 1;
        if(i & 1) temp = -temp;

        int j = e[i];
        i = ne[i];
        dfs(j);

        st.push(temp);
    }
}

signed main()
{
    int n, m; cin>>n>>m;
    for(int i = 1;i <= n;i ++) h[i] = -1;
    for(int i = 1;i <= m;i ++)
    {
        int u, v; cin>>u>>v;
        add(u, v); add(v, u);
        deg[u][1] ++; deg[v][0] ++;
    }
    // 无向图欧拉回路判断
    for(int i = 1;i <= n;i ++)
        if((deg[i][0] + deg[i][1]) % 2 == 1) {cout<<"NO"<<endl; return 0;}

    for(int i = 1;i <= n;i ++)
        if(h[i] != -1) {dfs(i); break;}

    if(st.size() < m) cout<<"NO"<<endl;
    else
    {
        cout<<"YES"<<endl;
        while(!st.empty()) cout<<st.top()<<" ", st.pop();
        cout<<endl;
    }

    return 0;
}

欧拉筛(线性求欧拉函数)

int prm[N], pre[N], phi[N], cnt;

void get_prm()
{
    for(int i = 2;i < N;i ++)
    {
        if(!pre[i]) 
        {
            pre[i] = prm[++ cnt] = i;
            // phi[i] = i - 1;
        }
        for(int j = 1;i * prm[j] < N;j ++)
        {
            pre[i * prm[j]] = prm[j];
            if(i % prm[j] == 0)
            {
                // phi[i * prm[j]] = phi[i] * prm[j];
                break;
            }
            // phi[i * prm[j]] = phi[i] * (prm[j] - 1);
        }
    }
}

[L, R]区间质数筛

// 先将[1, sqrt(r)] 内的质数通过欧拉筛预处理
// 通过埃氏筛对[L, R] 内的质数进行筛选
// 区间长度不超过1e6
int l, r; cin>>l>>r;
for(int i = 1;i <= cnt && prm[i] <= r;i ++)
{
	int w = (l + prm[i] - 1) / prm[i];
	for(int j = max(2ll, w);prm[i] * j <= r;j ++)
	vis[prm[i] * j - l] = true;
}
vector<int> prime;
for(int i = l;i <= r;i ++)
{
	if(!vis[i - l]) prime.push_back(i);
	vis[i - l] = false;
}

GCD

int gcd(int x, int y)
{
    if(x % y == 0) return y;
    return gcd(y, x % y);
}

扩展欧几里得

// 求 xa + by = gcd(a, b) 的一组解
// 最小正整数解 : (x % (b / gcd) + (b / gcd)) % (b / gcd)
int edgcd(int a, int b, int &x, int &y)
{
    if(a % b == 0)
    {
        x = 0; y = 1;
        return b;
    }
    int d = edgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

线性求逆元

inv[1] = 1;
for(int i = 2;i <= n;i ++) inv[i] = (p - p / i) * inv[p % i] % p;

中国剩余定理

int edgcd(int a, int b, int &x, int &y)
{
    if(a % b == 0)
    {
        x = 0; y = 1;
        return b;
    }
    int d = edgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

signed main()
{
    int n; cin>>n;
    int a1, m1; cin>>m1>>a1;
    bool flag = true;
    for(int i = 2;i <= n;i ++)
    {
        int a2, m2; cin>>m2>>a2;
        int k1, k2;
        int d = edgcd(m1, -m2, k1, k2);
        if((a2 - a1) % d != 0)
        {
            flag = false;
            break;
        }
        int x = m2 / d;
        k1 = k1 * (a2 - a1) / d;
        k1 = (k1 % x + x) % x;

        int m = abs(m1 / d * m2);
        a1 = k1 * m1 + a1;
        m1 = m;
    }
    if(flag) cout<<(a1 % m1 + m1) % m1<<endl;
    else cout<<-1<<endl;
    return 0;
}

高斯消元求解线性方程组

double mt[N][N];

int gauss(int n, int m) // n 个不等式， m 个未知数， 增广矩阵大小 n * (m + 1)
{
    int col, row;
    for(col = 1, row = 1;col <= m;col ++)
    {
        int t = row;
        for(int i = row;i <= n;i ++) if(mt[i][col] > mt[t][col]) t = i;
        if(fabs(mt[t][col]) < eps) continue;
        for(int i = col;i <= m + 1;i ++) swap(mt[row][i], mt[t][i]);
        for(int i = m + 1;i >= col;i --) mt[row][i] /= mt[row][col];
        for(int i = row + 1;i <= n;i ++) for(int j = m  + 1;j >= col;j --)
            mt[i][j] -= mt[row][j] * mt[i][col] / mt[row][col];
        row ++;
    }

    if(row <= n)
    {
        for(int i = row;i <= n;i ++) if(fabs(mt[i][m + 1]) > eps) return 0; //无解
        return 1; //无穷多解
    }

    for(int i = n - 1;i >= 1;i --) for(int j = i + 1;j <= m;j ++)
        mt[i][m + 1] -= mt[n - m + j][m + 1] * mt[i][j];
    return 2; //有唯一解
}

1000 * 1000 求组合数

int c[N][N];

void init()
{
    for(int i = 0;i < N;i ++) for(int j = 0;j <= i;j ++)
    {
        if(!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
}

费马小定理 快速幂求组合数

const int mod = 1e9 + 7;

int fact[N], infact[N];

int quickpow(int x, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = res * x % mod;
        k >>= 1;
        x = x * x % mod;
    }
    return res;
}

void init()
{
    fact[0] = infact[0] =1;
    for(int i = 1;i < N;i ++)
    {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = quickpow(fact[i], mod - 2);
    }
}

卢卡斯定理 求组合数 取模的数小基数大时使用

int quickpow(int x, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = res * x % p;
        k >>= 1;
        x = x * x % p;
    }
    return res;
}

int C(int a, int b, int p)
{
    int c1 = 1, c2 = 1;
    for(int i = 1, j = a;i <= b;i ++, j --) c1 = c1 * j % p, c2 = c2 * i % p;
    return c1 * quickpow(c2, p - 2, p) % p;
}

int lucas(int a, int b, int p)
{
    if(a < p && b < p) return C(a, b, p);
    return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

最长上升子序列

int a[N], f[N];

int main()
{
    int n; cin>>n;
    for(int i = 1;i <= n;i ++) cin>>a[i];
    int len = 1;
    f[1] = a[1];
    for(int i = 2;i <= n;i ++)
    {
        int temp = lower_bound(f + 1, f + len + 1, a[i]) - f;
        len = max(len, temp);
        f[temp] = a[i];
    }
    cout<<len<<endl;
    return 0;
}

多重背包 转化成 01背包

int f[N], v[M], w[M];

int main()
{
    int n, m; cin>>n>>m;
    int cnt = 0;
    for(int i = 1;i <= n;i ++)
    {
        int a, b, s; cin>>a>>b>>s;
        int k = 1;
        while(k <= s)
        {
            v[++ cnt] = k * a;
            w[cnt] = k * b;
            s -= k;
            k <<= 1;
        }
        if(s)
        {
            v[++ cnt] = s * a;
            w[cnt] = s * b;
        }
    }
    for(int i = 1;i <= cnt;i ++) for(int j = m;j >= 0;j --)
        if(j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout<<f[m]<<endl;
    return 0;
}

Stirling 阶乘位数

int get_len(int n)
{
    int len = 1;
    if (n > 3)
        len = log10(2 * PI * n) / 2 + n * log10(n / E) + 1;
    return len;
}

2的n次幂位数

n*log10(2) + 1;

ST表（查询区间最大值）

int f[N][21], log2n[N];

int main()
{
    int n = read(), m = read();
    for(int i = 1;i <= n;i++) f[i][0] = read();
    log2n[1] = 0; log2n[2] = 1;
    for(int i = 3;i <= n;i++) log2n[i] = log2n[i / 2] + 1;
    for(int j = 1;j <= 20;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]);
    for(int i = 1;i <= m;i++)
    {
        int l = read(), r = read();
        int k = log2n[r - l + 1];
        printf("%d\n", max(f[l][k], f[r - (1 << k) + 1][k]));
    }
    return 0;
}

Zeller 求星期几

int Zeller(int year,int month,int date)
{
    if(month == 1||month == 2) year --, month += 12;
    int c = year / 100;
    year -= c * 100;
    int week = year + year / 4 + c / 4 - 2 * c + 26 * (month + 1) / 10 + date-1;
    while(week < 0) week += 7;
    week %= 7;
    return week;
}

Zeller 日期 <----> id

int getid(int y, int m, int d) // 年月日 -> id
{
    if(m < 3) {y--; m += 12;}
    return 365 * y + y / 4 - y / 100 + y / 400 + (153 * (m - 3) + 2) / 5 + d - 307;
}

vector<int> date(int id) //  id -> 年月日
{
    int x = id + 1789995, n, i, j, y, m, d;
    n = 4 * x / 146097;
    x -= (146097 * n + 3) / 4;
    i = (4000 * (x + 1)) / 1461001; x -= 1461 * i / 4 - 31;
    j = 80 * x / 2447; d = x - 2447 * j / 80; x = j / 11;
    m = j + 2 - 12 * x; y = 100 * (n - 49) + i + x;
    return vector<int>({y, m, d});
}

加权并查集

int parent[N], val[N];
void initialise()
{
    memset(parent, -1, sizeof(parent));
    memset(val, 0, sizeof(val));
}

int find_root(int x)
{
    if (parent[x] == -1)
        return x;
    int t = parent[x];
    parent[x] = find_root(parent[x]);
    val[x] += val[t];
    return parent[x];
}

bool union_root(int x, int y, int v)
{
    int x_root = find_root(x);
    int y_root = find_root(y);
    if (x_root == y_root)
        return false;
    parent[x_root] = y_root;
    val[x_root] = val[y] - val[x] + v;
    return true;
}

区间赋值线段树

// 方便扩展其他功能，因此保留结点定义
// 建树时将所有lazy标记赋值成 操作中不可能被赋值的值 默认为 -1
struct node
{
    int lazy = -1;
};

node tree[N << 2];
int a[N];

void pushdown(int root)
{
    if (tree[root].lazy != -1)
    {
        tree[root << 1].lazy = tree[root].lazy;
        tree[root << 1 | 1].lazy = tree[root].lazy;

        tree[root].lazy = -1;
    }
}

void buildtree(int l, int r, int root)
{
    tree[root].lazy = -1;
    if (l == r)
    {
        tree[root].lazy = a[l];
        return;
    }
    int m = l + r >> 1;
    buildtree(l, m, root << 1);
    buildtree(m + 1, r, root << 1 | 1);
}

// 将[L, R]区间上的数赋值为num
void modify(int l, int r, int L, int R, int root, int num)
{
    if (l == L && r == R)
    {
        tree[root].lazy = num;
        return;
    }
    if (l == r) return;
    pushdown(root);
    int m = l + r >> 1;
    if (R <= m)
        modify(l, m, L, R, root << 1, num);
    else if (L > m)
        modify(m + 1, r, L, R, root << 1 | 1, num);
    else
    {
        modify(l, m, L, m, root << 1, num);
        modify(m + 1, r, m + 1, R, root << 1 | 1, num);
    }
}

// 查询下标为pos的值
int query(int l, int r, int root, int pos)
{
    if (l == r) return tree[root].lazy;
    pushdown(root);
    int m = l + r >> 1;
    if(pos <= m) return query(l, m, root << 1, pos);
    return query(m + 1, r, root << 1 | 1, pos);
}

区间最小值线段树

struct node {int mn = 0, lazy = 0;};

node tree[N << 2];
int a[N];

void pushup(int root)
{
    tree[root].mn = min(tree[root << 1].mn, tree[root << 1 | 1].mn);
}

void pushdown(int root, int left, int right)
{
    int mid = left + right >> 1;
    if (tree[root].lazy)
    {
        tree[root << 1].lazy += tree[root].lazy;
        tree[root << 1].mn += tree[root].lazy;
        tree[root << 1 | 1].lazy += tree[root].lazy;
        tree[root << 1 | 1].mn += tree[root].lazy;
        tree[root].lazy = 0;
    }
}

void buildtree(int l, int r, int root)
{
    tree[root].lazy = 0;
    if (l == r)
    {
        tree[root].mn = a[l];
        return;
    }
    int m = l + r >> 1;
    buildtree(l, m, root << 1);
    buildtree(m + 1, r, root << 1 | 1);
    pushup(root);
}

// [L, R] all add num
void updata(int l, int r, int L, int R, int root, int num)
{
    if (l >= L && r <= R)
    {
        tree[root].lazy += num;
        tree[root].mn += num;
        return;
    }
    pushdown(root, l, r);
    int m = l + r >> 1;
    if(L <= m) updata(l, m, L, R, root << 1, num);
    if(R > m) updata(m + 1, r, L, R, root << 1 | 1, num);
    pushup(root);
}

// query the min-number of [L, R]
int query(int l, int r, int L, int R, int root)
{
    if (l >= L && r <= R) return tree[root].mn;
    pushdown(root, l, r);
    int m = l + r >> 1;
    int res = inf;
    if(L <= m) res = min(res, query(l, m, L, R, root << 1));
    if(R > m) res = min(res, query(m + 1, r, L, R, root << 1 | 1));
    pushup(root);
    return res;
}

区间最大值线段树

struct node {int mx = 0, lazy = 0;};

node tree[N << 2];
int a[N];

void pushup(int root)
{
    tree[root].mx = max(tree[root << 1].mx, tree[root << 1 | 1].mx);
}

void pushdown(int root, int left, int right)
{
    int mid = left + right >> 1;
    if (tree[root].lazy)
    {
        tree[root << 1].lazy += tree[root].lazy;
        tree[root << 1].mx += tree[root].lazy;
        tree[root << 1 | 1].lazy += tree[root].lazy;
        tree[root << 1 | 1].mx += tree[root].lazy;
        tree[root].lazy = 0;
    }
}

void buildtree(int l, int r, int root)
{
    tree[root].lazy = 0;
    if (l == r)
    {
        tree[root].mx = a[l];
        return;
    }
    int m = l + r >> 1;
    buildtree(l, m, root << 1);
    buildtree(m + 1, r, root << 1 | 1);
    pushup(root);
}

// [L, R] all add num
void updata(int l, int r, int L, int R, int root, int num)
{
    if (l >= L && r <= R)
    {
        tree[root].lazy += num;
        tree[root].mx += num;
        return;
    }
    pushdown(root, l, r);
    int m = l + r >> 1;
    if(L <= m) updata(l, m, L, R, root << 1, num);
    if(R > m) updata(m + 1, r, L, R, root << 1 | 1, num);
    pushup(root);
}

// query the max-number of [L, R]
int query(int l, int r, int L, int R, int root)
{
    if (l >= L && r <= R) return tree[root].mx;
    pushdown(root, l, r);
    int m = l + r >> 1;
    int res = 0;
    if(L <= m) res = max(res, query(l, m, L, R, root << 1));
    if(R > m) res = max(res, query(m + 1, r, L, R, root << 1 | 1));
    pushup(root);
    return res;
}

区间求和线段树

struct node {int sum = 0, lazy = 0;};

node tree[N << 2];
int a[N];

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

void pushdown(int root, int left, int right)
{
    int mid = left + right >> 1;
    if (tree[root].lazy)
    {
        tree[root << 1].lazy += tree[root].lazy;
        tree[root << 1].sum += tree[root].lazy * (mid - left + 1);
        tree[root << 1 | 1].lazy += tree[root].lazy;
        tree[root << 1 | 1].sum += tree[root].lazy * (right - mid);
        tree[root].lazy = 0;
    }
}

void buildtree(int l, int r, int root)
{
    tree[root].lazy = 0;
    if (l == r)
    {
        tree[root].sum = a[l];
        return;
    }
    int m = l + r >> 1;
    buildtree(l, m, root << 1);
    buildtree(m + 1, r, root << 1 | 1);
    pushup(root);
}

// [L, R] all add num
void updata(int l, int r, int L, int R, int root, int num)
{
    if (l >= L && r <= R)
    {
        tree[root].lazy += num;
        tree[root].sum += num * (r - l + 1);
        return;
    }
    if (l == r) return;
    pushdown(root, l, r);
    int m = l + r >> 1;
    if(L <= m) updata(l, m, L, R, root << 1, num);
    if(R > m) updata(m + 1, r, L, R, root << 1 | 1, num);
    pushup(root);
}

// query the sum of [L, R]
int query(int l, int r, int L, int R, int root)
{
    if (l >= L && r <= R) return tree[root].sum;
    pushdown(root, l, r);
    int m = l + r >> 1;
    int res = 0;
    if(L <= m) res += query(l, m, L, R, root << 1);
    if(R > m) res += query(m + 1, r, L, R, root << 1 | 1);
    pushup(root);
    return res;
}

可持久化线段树 (求区间第k小值)

const int N = 2e5 + 10;

struct node
{
    int l, r, sum;
}tree[N << 5];
int cnt, a[N], root[N];
vector<int> alls;

int find(int x) {return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;}

void insert(int l, int r, int pre, int &now, int p)
{
    tree[++ cnt] = tree[pre];
    now = cnt;
    tree[now].sum ++;
    if(l == r) return;
    int mid = l + r >> 1;
    if(p <= mid) insert(l, mid, tree[pre].l, tree[now].l, p);
    else insert(mid + 1, r, tree[pre].r, tree[now].r, p);
}

int query(int l, int r, int L, int R, int k)
{
    if(l == r) return l;
    int mid = l + r >> 1;
    int temp = tree[tree[R].l].sum - tree[tree[L].l].sum;
    if(k <= temp) return query(l, mid, tree[L].l, tree[R].l, k);
    return query(mid + 1, r, tree[L].r, tree[R].r, k - temp);
}


void solve()
{
    int n, m; n = read(); m = read();
    for(int i = 1;i <= n;i ++) a[i] = read();

    for(int i = 1;i <= n;i ++) alls.push_back(a[i]);
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    for(int i = 1;i <= n;i ++) insert(1, n, root[i - 1], root[i], find(a[i]));

    for(int i = 1;i <= m;i ++)
    {
        int l, r, k;
        l = read(); r = read(), k = read();
        printf("%d\n", alls[query(1, n, root[l - 1], root[r], k) - 1]);
    }
}

可持久化线段树 (实现可持久化数组 查询及更新历史版本数组)

const int N = 1e6 + 10;

struct node
{
    int l, r, val;
}tree[N << 5];

int cnt, root[N], a[N];

// now:初始建树版本的根节点
void build(int l, int r, int &now)
{
    now = ++ cnt;
    if(l == r)
    {
        tree[now].val = a[l];
        return;
    }
    int m = l + r >> 1;
    build(l, m, tree[now].l);
    build(m + 1, r, tree[now].r);
}

// ver:历史版本根节点，now:当前版本根节点，pos:更新节点下标，num:更新的值
void modify(int l, int r, int ver, int &now, int pos, int num)
{
    tree[now = ++ cnt] = tree[ver];
    if(l == r)
    {
        tree[now].val = num;
        return;
    }
    int m = l + r >> 1;
    if(pos <= m) modify(l, m, tree[ver].l, tree[now].l, pos, num);
    else modify(m + 1, r, tree[ver].r, tree[now].r, pos, num);
}

// now:查询版本的根节点，pos:查询节点的下标
int query(int l, int r, int now, int pos)
{
    if(l == r) return tree[now].val;
    int m = l + r >> 1;
    if(pos <= m) return query(l, m, tree[now].l, pos);
    return query(m + 1, r, tree[now].r, pos);
}

可持久化并查集

const int N = 2e5 + 10;

struct node
{
    int l, r, val;
}tree[N << 5];

int cnt, rootfa[N], rootdep[N], n;

// now:初始建树版本的根节点
void build(int l, int r, int &now)
{
    now = ++ cnt;
    if(l == r)
    {
        tree[now].val = l;
        return;
    }
    int m = l + r >> 1;
    build(l, m, tree[now].l);
    build(m + 1, r, tree[now].r);
}

// ver:历史版本根节点，now:当前版本根节点，pos:更新节点下标，num:更新的值
void modify(int l, int r, int ver, int &now, int pos, int num)
{
    tree[now = ++ cnt] = tree[ver];
    if(l == r)
    {
        tree[now].val = num;
        return;
    }
    int m = l + r >> 1;
    if(pos <= m) modify(l, m, tree[ver].l, tree[now].l, pos, num);
    else modify(m + 1, r, tree[ver].r, tree[now].r, pos, num);
}

// now:查询版本的根节点，pos:查询节点的下标
int query(int l, int r, int now, int pos)
{
    if(l == r) return tree[now].val;
    int m = l + r >> 1;
    if(pos <= m) return query(l, m, tree[now].l, pos);
    return query(m + 1, r, tree[now].r, pos);
}

// 查询第ver个版本x结点的根节点（不能使用路径压缩）
int find(int ver, int x)
{
    int rx = query(1, n, rootfa[ver], x);
    if(rx == x) return x;
    return find(ver, rx);
}

// 按秩合并ver版本的 x 与 y 集合
void merge(int ver, int x, int y)
{
    x = find(ver - 1, x);
    y = find(ver - 1, y);
    if(x == y)
    {
        rootfa[ver] = rootfa[ver - 1];
        rootdep[ver] = rootdep[ver - 1];
        return;
    }

    int depx = query(1, n, rootdep[ver - 1], x);
    int depy = query(1, n, rootdep[ver - 1], y);

    if(depx < depy)
    {
        modify(1, n, rootfa[ver - 1], rootfa[ver], x, y);
        rootdep[ver] = rootdep[ver - 1];
    }
    else if(depx > depy)
    {
        modify(1, n, rootfa[ver - 1], rootfa[ver], y, x);
        rootdep[ver] = rootdep[ver - 1];
    }
    else
    {
        modify(1, n, rootfa[ver - 1], rootfa[ver], x, y);
        modify(1, n, rootdep[ver - 1], rootdep[ver], y, depy + 1);
    }
}

void solve()
{
    n = read();
    int m = read();
    build(1, n, rootfa[0]);
    for(int i = 1;i <= m;i ++)
    {
        int opt = read();
        int a, b, k;
        switch (opt)
        {
        case 1: // 当前版本基础上合并a b集合
            a = read();
            b = read();
            merge(i, a, b);
            break;
        case 2: // 回溯到第k个版本
            k = read();
            rootfa[i] = rootfa[k];
            rootdep[i] = rootdep[k];
            break;
        case 3: // 查询当前版本 a b 是否属于同一集合
            a = read();
            b = read();
            rootfa[i] = rootfa[i - 1];
            rootdep[i] = rootdep[i - 1];
            int ra = find(i, a), rb = find(i, b);
            if(ra == rb) printf("1\n");
            else printf("0\n");
        }
    }
}

替罪羊树（平衡树 动态查询排名、分数、前驱和后继）

const int N = 1e5 + 10;
const double alpha = 0.75;

struct node
{
    int l, r, val;
    int size, fact; // size: 树的大小， fact:实际有效数字大小
    bool exist; // 是否存在  1: 存在   0: 删除
}tree[N];

int cnt, root;

// 新建结点 赋值为val
void newnode(int &now, int val)
{
    now = ++ cnt;
    tree[now].l = tree[now].r = 0;
    tree[now].val = val;
    tree[now].size = tree[now].fact = 1;
    tree[now].exist = true;
}

// 判断当前子树是否平衡
bool imbalance(int now)
{
    if(std::max(tree[tree[now].l].size, tree[tree[now].r].size) > tree[now].size * alpha
       || tree[now].size - tree[now].fact > tree[now].size * 0.3)
       return true;
    return false;
}

std::vector<int> vec;
// 中序遍历序列存入数组vec
void dfs(int now)
{
    if(!now) return;
    dfs(tree[now].l);
    if(tree[now].exist) vec.push_back(now);
    dfs(tree[now].r);
}

// 对vec[l, r] 区间二分建平衡树
void lift(int l, int r, int &now)
{
    if(l == r)
    {
        now = vec[l];
        tree[now].l = tree[now].r = 0;
        tree[now].size = tree[now].fact = 1;
        tree[now].exist = true;
        return;
    }
    int m = l + r >> 1;
    while(l < m && tree[vec[m]].val == tree[vec[m - 1]].val) m --;
    now = vec[m];
    if(l < m) lift(l, m - 1, tree[now].l);
    else tree[now].l = 0;
    lift(m + 1, r, tree[now].r);
    tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
    tree[now].fact = tree[tree[now].l].fact + tree[tree[now].r].fact + 1;
}

// 暴力重建 now 结点为根的子树
void rebuild(int &now)
{
    vec.clear();
    dfs(now);
    if(vec.empty())
    {
        now = 0;
        return;
    }
    lift(0, vec.size() - 1, now);
}

// 向上更新树的大小 - size
void updata(int now, int end)
{
    if(!now) return;
    if(tree[end].val < tree[now].val) updata(tree[now].l, end);
    else updata(tree[now].r, end);
    tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
}

// 由顶至下检查是否平衡
void check(int &now, int end)
{
    if(now == end) return;
    if(imbalance(now))
    {
        rebuild(now);
        updata(root, now);
        return;
    }
    if(tree[end].val < tree[now].val) check(tree[now].l, end);
    else check(tree[now].r, end);
}

// 向平衡树中插入一个数
void insert(int &now, int val)
{
    if(!now)
    {
        newnode(now, val);
        check(root, now);
        return;
    }
    tree[now].size ++;
    tree[now].fact ++;
    if(val < tree[now].val) insert(tree[now].l, val);
    else insert(tree[now].r, val);
}

// 在平衡树中删除一个数
void del(int now, int val)
{
    if(tree[now].exist && tree[now].val == val)
    {
        tree[now].exist = false;
        tree[now].fact --;
        check(root, now);
        return;
    }
    tree[now].fact --;
    if(val < tree[now].val) del(tree[now].l, val);
    else del(tree[now].r, val);
}

// 获得排名（排名定义为比当前数小的数的个数 +1）
int getrank(int val)
{
    int now = root, rank = 1;
    while(now)
    {
        if(val <= tree[now].val) now = tree[now].l;
        else
        {
            rank += tree[tree[now].l].fact + tree[now].exist;
            now = tree[now].r;
        }
    }
    return rank;
}

// 查询排名为 rank 的数
int getnum(int rank)
{
    int now = root;
    while(now)
    {
        if(tree[now].exist && tree[tree[now].l].fact + tree[now].exist == rank)
            break;
        else if(tree[tree[now].l].fact >= rank)
            now = tree[now].l;
        else
        {
            rank -= tree[tree[now].l].fact + tree[now].exist;
            now = tree[now].r;
        }
    }
    return tree[now].val;
}

// 查询值为 x 的前驱
int get_pre(int x)
{
    return getnum(getrank(x) - 1);
}

// 查询值为 x 的后继
int get_next(int x)
{
    return getnum(getrank(x + 1));
}

treap (树旋转)

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

const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;

struct node
{
    int l, r;
    int key, val;
    int size, cnt;
}treap[N];

int root, idx;

int get_node(int key)
{
    treap[++ idx].key = key;
    treap[idx].val = rand();
    treap[idx].size = treap[idx].cnt = 1;
    return idx;
}

void pushup(int p)
{
    treap[p].size = treap[treap[p].l].size + treap[treap[p].r].size + treap[p].cnt;
}

void zig(int &p) // 右旋
{
    int q = treap[p].l;
    treap[p].l = treap[q].r, treap[q].r = p, p = q;
    pushup(treap[p].r), pushup(p);
}

void zag(int &p) // 左旋
{
    int q = treap[p].r;
    treap[p].r = treap[q].l, treap[q].l = p, p = q;
    pushup(treap[p].l), pushup(p);
}

void build()
{
    root = get_node(-inf);
    treap[root].r = get_node(inf);
    pushup(root);
    if(treap[root].val < treap[treap[root].r].val) zag(root);
}

void insert(int &p, int key)
{
    if(!p) p = get_node(key);
    else if(treap[p].key == key) treap[p].cnt ++;
    else if(treap[p].key > key)
    {
        insert(treap[p].l, key);
        if(treap[treap[p].l].val > treap[p].val) zig(p);
    }
    else
    {
        insert(treap[p].r, key);
        if(treap[treap[p].r].val > treap[p].val) zag(p);
    }
    pushup(p);
}

void remove(int &p, int key)
{
    if(!p) return;
    if(treap[p].key == key)
    {
        if(treap[p].cnt > 1) treap[p].cnt --;
        else if(treap[p].l || treap[p].r)
        {
            if(!treap[p].r || treap[treap[p].l].val > treap[treap[p].r].val)
            {
                zig(p);
                remove(treap[p].r, key);
            }
            else
            {
                zag(p);
                remove(treap[p].l, key);
            }
        }
        else p = 0;

    }
    else if(treap[p].key > key)
        remove(treap[p].l, key);
    else 
        remove(treap[p].r, key);
    pushup(p);
}

int get_rank_by_key(int p, int key)
{
    if(!p) return 0;
    if(treap[p].key == key) return treap[treap[p].l].size + 1;
    if(treap[p].key > key) return get_rank_by_key(treap[p].l, key);
    return treap[treap[p].l].size + treap[p].cnt + get_rank_by_key(treap[p].r, key);
}

int get_key_by_rank(int p, int rank)
{
    if(!p) return inf;
    if(treap[treap[p].l].size >= rank) return get_key_by_rank(treap[p].l, rank);
    if(treap[treap[p].l].size + treap[p].cnt >= rank) return treap[p].key;
    return get_key_by_rank(treap[p].r, rank - treap[treap[p].l].size - treap[p].cnt);
}

int get_pre_by_key(int p, int key) // 严格小于key的最大数
{
    if(!p) return -inf;
    if(treap[p].key >= key) return get_pre_by_key(treap[p].l, key); // 去掉等号变成不严格
    return max(treap[p].key, get_pre_by_key(treap[p].r, key));
}

int get_next_by_key(int p, int key) //严格大于key的最小数
{
    if(!p) return inf;
    if(treap[p].key <= key) return get_next_by_key(treap[p].r, key); // 去掉等号变成不严格
    return min(treap[p].key, get_next_by_key(treap[p].l, key));
}

int main()
{
    int n; cin>>n;
    build();
    for(int i = 1;i <= n;i ++)
    {
        int opt, x; cin>>opt>>x;
        if(opt == 1) insert(root, x);
        else if(opt == 2) remove(root, x);
        else if(opt == 3) cout<<get_rank_by_key(root, x) - 1<<endl; // 有两个哨兵结点(-inf, inf)
        else if(opt == 4) cout<<get_key_by_rank(root, x + 1)<<endl; // 排名对应原本会多1
        else if(opt == 5) cout<<get_pre_by_key(root, x)<<endl;
        else cout<<get_next_by_key(root, x)<<endl;
    }
    return 0;
}

fhq treap（按值合并 平衡树 动态查询排名、分数、前驱和后继）

const int N = 1e5 + 10;

struct node
{
    int l, r;
    int val, key; // val: 结点值, key: 结点标记值（维护二叉堆）
    int size; // 树的大小
}tree[N];

int cnt, root;

// 新建结点 赋值为val
std::mt19937 rnd(233);
inline int newnode(int val)
{
    tree[++ cnt].val = val;
    tree[cnt].key = rnd();
    tree[cnt].size = 1;
    return cnt;
}

// 向上更新树的大小 - size
inline void updata(int now)
{
    tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
}

// 将平衡树 按值 分裂为两棵树 根分别为 x, y ;
// x 树上的值全部小于等于 val， y 树上的值全部大于 val
void split(int now, int val, int &x, int &y)
{
    if(!now) x = y = 0;
    else
    {
        if(tree[now].val <= val)
        {
            x = now;
            split(tree[now].r, val, tree[now].r, y);
        }
        else
        {
            y = now;
            split(tree[now].l, val, x, tree[now].l);
        }
        updata(now);
    }
}

// 将两颗平衡树合并为一颗平衡树 返回根节点
int merge(int x, int y)
{
    if(!x || !y) return x + y;
    if(tree[x].key > tree[y].key)
    {
        tree[x].r = merge(tree[x].r, y);
        updata(x);
        return x;
    }
    else
    {
        tree[y].l = merge(x, tree[y].l);
        updata(y);
        return y;
    }
}

int x, y, z;

// 向平衡树中插入一个数
inline void insert(int val)
{
    split(root, val, x, y);
    root = merge(merge(x, newnode(val)), y);
}

// 在平衡树中删除一个数
inline void del(int val)
{
    split(root, val, x, z);
    split(x, val - 1, x, y);
    y = merge(tree[y].l, tree[y].r);
    root = merge(merge(x, y), z);
}

// 获得排名（排名定义为比当前数小的数的个数 +1）
inline int getrank(int val)
{
    split(root, val - 1, x, y);
    int res = tree[x].size + 1;
    root = merge(x, y);
    return res;
}

// 查询排名为 rank 的数
inline int getnum(int rank)
{
    int now = root;
    while(now)
    {
        if(tree[tree[now].l].size + 1 == rank) break;
        else if(tree[tree[now].l].size >= rank) now = tree[now].l;
        else
        {
            rank -= tree[tree[now].l].size + 1;
            now = tree[now].r;
        }
    }
    return tree[now].val;
}

// 查询值为 val 的前驱
inline int get_pre(int val)
{
    split(root, val - 1, x, y);
    int now = x;
    while(tree[now].r) now = tree[now].r;
    int res = tree[now].val;
    root = merge(x, y);
    return res;
}

// 查询值为 val 的后继
inline int get_next(int val)
{
    split(root, val, x, y);
    int now = y;
    while(tree[now].l) now = tree[now].l;
    int res = tree[now].val;
    root = merge(x, y);
    return res;
}

fhq treap（按大小合并 维护区间的动态分裂，合并和翻转）

const int N = 1e5 + 10;

struct node
{
    int l, r;
    int val, key; // val: 结点值, key: 结点标记值（维护二叉堆）
    int size; // 树的大小
    bool reverse; // 区间是否被翻转
}tree[N];

int cnt, root;

// 新建结点 赋值为val
std::mt19937 rnd(233);
inline int newnode(int val)
{
    tree[++ cnt].val = val;
    tree[cnt].key = rnd();
    tree[cnt].size = 1;
    return cnt;
}

// 向上更新树的大小 - size
inline void update(int now)
{
    tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
}

// 向下传递懒标记 是否翻转 - reverse
inline void pushdown(int now)
{
    if(tree[now].reverse)
    {
        std::swap(tree[now].l, tree[now].r);
        tree[tree[now].l].reverse ^= 1;
        tree[tree[now].r].reverse ^= 1;
        tree[now].reverse = false;
    }
}

// 将平衡树 按大小 分裂为两棵树 根分别为 x, y ;
// x 树的大小等于 siz， y 树为剩下的部分
void split(int now, int siz, int &x, int &y)
{
    if(!now) x = y = 0;
    else
    {
        pushdown(now);
        if(tree[tree[now].l].size < siz)
        {
            x = now;
            split(tree[now].r, siz - tree[tree[now].l].size - 1, tree[now].r, y);
        }
        else
        {
            y = now;
            split(tree[now].l, siz, x, tree[now].l);
        }
        update(now);
    }
}

// 将两颗平衡树合并为一颗平衡树 返回根节点
int merge(int x, int y)
{
    if(!x || !y) return x + y;
    if(tree[x].key < tree[y].key)
    {
        pushdown(x);
        tree[x].r = merge(tree[x].r, y);
        update(x);
        return x;
    }
    else
    {
        pushdown(y);
        tree[y].l = merge(x, tree[y].l);
        update(y);
        return y;
    }
}

// 翻转 [l, r] 区间
void reverse(int l, int r)
{
    int x, y, z;
    split(root, l - 1, x, y);
    split(y, r - l + 1, y, z);
    tree[y].reverse ^= 1;
    root = merge(merge(x, y), z);
}

// 中序遍历输出
void output(int now)
{
    if(!now) return;
    pushdown(now);
    output(tree[now].l);
    printf("%d ", tree[now].val);
    output(tree[now].r);
}

// merge(root, newnode(val)) 为向数组尾插入一个值为val的元素
// 将数组初始化为[1, n]的操作代码为：
for(int i = 1;i <= n;i ++) root = merge(root, newnode(i));

最小圆覆盖

const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;

struct node
{
    double x, y;
} e[N], o; //点集， 圆心
int n;
double ans = inf, r = 0;
double get_dis(node a, node b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

// 三个点中任意选取两对点之间连两条线段，它们垂直平分线的交点就是圆心
void getr(node p1, node p2, node p3)
{
    double a, b, c, d, e, f;
    a = p2.y - p1.y;
    b = p3.y - p1.y;
    c = p2.x - p1.x;
    d = p3.x - p1.x;
    f = p3.x * p3.x + p3.y * p3.y - p1.x * p1.x - p1.y * p1.y;
    e = p2.x * p2.x + p2.y * p2.y - p1.x * p1.x - p1.y * p1.y;
    o.x = (a * f - b * e) / (2 * a * d - 2 * b * c);
    o.y = (d * e - c * f) / (2 * a * d - 2 * b * c);
    r = get_dis(o, p1);
}
int circular()
{
    random_shuffle(e + 1, e + 1 + n);
    o.x = e[1].x, o.y = e[1].y, r = 0;
    for (int i = 2; i <= n; i++)
    {
        if (get_dis(e[i], o) > r + eps)
        {
            o.x = e[i].x, o.y = e[i].y, r = 0;
            for (int j = 1; j < i; j++)
            {
                if (get_dis(e[j], o) > r + eps)
                {
                    o.x = (e[i].x + e[j].x) / 2;
                    o.y = (e[i].y + e[j].y) / 2;
                    r = get_dis(o, e[i]);
                    for (int k = 1; k < j; k++)
                    {
                        if (get_dis(e[k], o) > r + eps)
                            getr(e[i], e[j], e[k]);
                    }
                }
            }
        }
    }
    return r;
}

固定半径圆 最大覆盖点数

const int N = 1e2 + 10;
const double eps = 1e-8;

struct Point
{
    double x, y;
    Point(){}
    Point(double tx, double ty) {x = tx; y = ty;}
}a[N];

double get_dist(Point p1, Point p2)
{
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

// 求过两点的半径为 r 的圆，返回圆心
Point get_circle(Point p1, Point p2, double r)
{
    Point mid = Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
    double angle = atan2 (p1.x - p2.x,p2.y - p1.y);
    double dist = sqrt(r * r - get_dist(mid, p1) * get_dist(mid, p1));
    return Point(mid.x + dist * cos(angle), mid.y + dist * sin(angle));
}

// 求点集 p 中 半径为 r 的圆覆盖点的最大数量
int CircleAndPoints(Point p[], int n, double r)
{
    int res = 1;
    if(n == 1) return res;
    for(int i = 1;i <= n;i ++) for(int j = i + 1;j <= n;j ++)
    {
        Point central = get_circle(p[i], p[j], r);
        int cnt = 0;
        for(int k = 1;k <= n;k ++) if(get_dist(p[k], central) < r + eps) cnt ++;
        res = max(res, cnt);
    }
    return res;
}

Graham's Scan算法（求点集的凸包）

const int N = 1e3 + 10;

struct node
{
    double x, y;
}p[N], P[N]; // p 代表初始点集， P 代表凸包上的点集

// 叉积
double X(node A, node B, node C)
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

// 求两点间距离
double get_dist(node A, node B)
{
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

// 按斜率从小到大排序
bool cmp(node A, node B)
{
    double pp = X(p[0], A, B);
    if(pp > 0) return true;
    if(pp < 0) return false;
    return get_dist(p[0], A) < get_dist(p[0], B);
}

void solve()
{
    int n = read();
    for(int i = 0;i < n;i ++) p[i].x = read(), p[i].y = read();
    if(n == 1) printf("%.2f\n", 0.000);
    else if(n == 2) printf("%.2f\n", get_dist(p[0], p[1]));
    else
    {
        for(int i = 0;i < n;i ++)
        {
            if(p[i].y < p[0].y) swap(p[0], p[i]);
            else if(p[0].y == p[i].y && p[i].x < p[0].x) swap(p[0], p[i]);
        }
        sort(p + 1, p + n, cmp);
        P[0] = p[0]; P[1] = p[1];
        int tot = 1;
        for(int i = 2;i < n;i ++)
        {
            while(tot > 0 && X(P[tot - 1], P[tot], p[i]) <= 0) tot --;
            P[++ tot] = p[i];
        }
        double ans = 0;
        for(int i = 0;i < tot;i ++) ans += get_dist(P[i], P[i + 1]);
        ans += get_dist(P[0], P[tot]);
        printf("%.2f\n", ans);
    }
}

从子集的和还原数组 // 可包含负数元素

vector<int> recoverArray(int n, vector<int>& sums)
{
    int mn = 1e5;
    for(auto &p : sums) mn = min(mn, p);
    mn = -mn;
    multiset<int> st;
    for(auto &p : sums) st.insert(p + mn);
    st.erase(st.begin());
    vector<int> ans;
    ans.push_back(*st.begin());
    for(int i = 1;i < n;i ++)
    {
        for(int k = 0;k < (1 << i);k ++) if(k >> (i - 1) & 1){
                int temp = 0;
                for(int j = 0;j < i;j ++) if(k >> j & 1) temp += ans[j];
                st.erase(st.find(temp));
            }
        ans.push_back(*st.begin());
    }
    for(int i = 0;i < (1 << n);i ++)
    {
        int temp = 0;
        for(int j = 0;j < n;j ++) if(i >> j & 1) temp += ans[j];
        if(temp == mn)
        {
            for(int j = 0;j < n;j ++) if(i >> j & 1) ans[j] = -ans[j];
            break;
        }
    }
    return ans;
}

组合数学

（1）Cn0+Cn2+Cn4+……+Cnn=2^(n-1)(n为偶数）
（2）Cn1+Cn3+Cn5+……+Cn(n-1)=2^(n-1) (n为偶数）
（3）Cn0+Cn2+Cn4+……+Cn(n-1)=2^(n-1) (n为奇数）
（4）Cn1+Cn3+Cn5+……+Cnn=2^(n-1) (n为奇数）
（5）Cn0-Cn1+Cn2-Cn3+……+(-1)^nCnn=0

具体数学

1² + 2² + 3² + ··· + n² = n * (n + 1) * (n * 2 + 1) / 6

莫队 (离线查询多个区间不同数的个数)

struct query
{
    int l, r, id;
}q[N];

int n, m, sz, bnum, now;
int a[N], ans[N], cnt[N], belong[N];

bool cmp(query a, query b)
{
    return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}

void solve()
{
    n = read(); // 数组大小
    sz = (int)sqrt(n);
    bnum = ceil((double)(n) / sz);
    for(int i = 1;i <= n;i ++) cnt[i] = 0;
    now = 0;
    for(int i = 1;i <= bnum;++ i) for(int j = (i - 1) * sz + 1;j <= i * sz;++ j)
        belong[j] = i;
    for(int i = 1;i <= n;i ++) a[i + n] = a[i] = read(); // 数值过大需要先对数据进行离散化
    m = read(); // 区间查询数
    for(int i = 1;i <= m;i ++)
    {
        q[i].l = read();
        q[i].r = read();
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp);
    int l = 1, r = 0;
    for(int i = 1;i <= m;i ++)
    {
        int ql = q[i].l, qr = q[i].r;
        while(l < ql) now -= !--cnt[a[l++]];
        while(l > ql) now += !cnt[a[--l]]++;
        while(r < qr) now += !cnt[a[++r]]++;
        while(r > qr) now -= !--cnt[a[r--]];
        ans[q[i].id] = now;
    }
    for(int i = 1;i <= m;i ++) printf("%d\n", ans[i]);
}

长度不小于len的子数组的最大平均值

double sum[N];

// 数组 p, 数组长度 n, 子数组最小长度 len, 测试平均值 x;
bool check(int p[], int n, int len, double x)
{
    for(int i = 1;i <= n;i ++) sum[i] = sum[i - 1] + p[i] - x;
    double mn = 1e5;
    for(int i = len, j = 0;i <= n;i ++, j ++)
    {
        mn = min(mn, sum[j]);
        if(sum[i] - mn >= 0) return true;
    }
    return false;
}

// 数组 p, 数组长度 n, 子数组最小长度 len, 元素最小值 left, 元素最大值 right
double get_average(int p[], int n, int len, double left, double right)
{
    while(right - left > 1e-7)
    {
        double mid = (left + right) / 2;
        if(check(p, n, len, mid)) left = mid;
        else right = mid;
    }
    return right;
}

表达式求值（可带括号，首个数字不能含前导符号,）

// 计算过程中所有中间结果不得超过 int 范围，若有可能越界手动改为long long
inline int expre(string &s)
{
    stack<int> sta1;
    stack<char> sta2;
    for(int i = 0;i < s.length();i ++)
    {
        if(s[i] >= '0' && s[i] <= '9')
        {
            int j = i, num = 0;
            while(j < s.length() && s[j] >= '0' && s[j] <= '9')
                num = num * 10 + s[j ++] - '0';
            i = j - 1;
            if(!sta2.empty() && (sta2.top() == '*' || sta2.top() == '/'))
            {
                char opt = sta2.top(); sta2.pop();
                int temp = sta1.top(); sta1.pop();
                if(opt == '*') sta1.push(temp * num);
                else sta1.push(temp / num);
            }
            else sta1.push(num);
        }
        else if(s[i] == ')')
        {
            int sum = 0;
            while(sta2.top() != '(')
            {
                int num = sta1.top(); sta1.pop();
                int opt = sta2.top(); sta2.pop();
                if(opt == '+') sum += num;
                else sum -= num;
            }
            sta2.pop();
            sum += sta1.top(); sta1.pop();
            sta1.push(sum);
            if(!sta2.empty() && (sta2.top() == '*' || sta2.top() == '/'))
            {
                int num2 = sta1.top(); sta1.pop();
                int num1 = sta1.top(); sta1.pop();
                int opt = sta2.top(); sta2.pop();
                if(opt == '*') sta1.push(num1 * num2);
                else sta1.push(num1 / num2);
            }
        }
        else sta2.push(s[i]);
    }
    int sum = 0;
    while(!sta2.empty())
    {
        int num = sta1.top(); sta1.pop();
        int opt = sta2.top(); sta2.pop();
        if(opt == '+') sum += num;
        else sum -= num;
    }
    return sta1.top() + sum;
}

高斯消元求解行列式

int det(int n) {
    int res = 1;
    for(int i = 1;i <= n;i ++)
    {
        int qaq = quickpow(a[i][i], mod2 - 2);
        for(int j = i + 1;j <= n;j ++)
        {
            int tmp = 1ll * a[j][i] * qaq % mod2;
            for(int k = 1;k <= n;k ++)
                a[j][k] = (a[j][k] - 1ll * a[i][k] * tmp % mod2 + mod2) % mod2;
        }
    }
    for(int i = 1;i <= n;i ++) res = 1ll * res * a[i][i] % mod2;
    return (res % mod2 + mod2) % mod2;
}

LCA 倍增

vector<int> e[N];
int depth[N], fa[N][16];

void bfs(int root) // 预处理 depth 和 fa
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    queue<int> que;
    que.push(root);
    while(!que.empty())
    {
        int u = que.front(); que.pop();
        for(auto &v : e[u])
        {
            if(depth[v] > depth[u] + 1)
            {
                depth[v] = depth[u] + 1;
                que.push(v);
                fa[v][0] = u;
                for(int i = 1;i <= 15;i ++)
                    fa[v][i] = fa[fa[v][i - 1]][i - 1];
            }
        }
    }
}

int lca(int x, int y) // 查询 x, y 的最近公共祖先
{
    if(depth[x] < depth[y]) swap(x, y);
    for(int i = 15;i >= 0;i --)
        if(depth[fa[x][i]] >= depth[y])
            x = fa[x][i];
    if(x == y) return x;
    for(int i = 15;i >= 0;i --)
        if(fa[x][i] != fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    return fa[x][0];
}

int main()
{
    int n; cin>>n;
    int root = 0;
    for(int i = 1;i <= n;i ++)
    {
        int u, v; cin>>u>>v;
        if(v == -1) root = u;
        else e[u].push_back(v), e[v].push_back(u);
    }

    bfs(root);

    int m; cin>>m;
    for(int i = 1;i <= m;i ++)
    {
        int x, y; cin>>x>>y;
        int tot = lca(x, y);
    }
    return 0;
}

LCA tarjan 算法

vector<int> e[N];
vector<pair<int, int>> query[N];
pair<int, int> Data[M];
int parent[N];
int p[M], st[N];

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

void tarjan(int u)
{
    st[u] = 1;
    for(auto &v : e[u])
    {
        if(!st[v])
        {
            tarjan(v);
            parent[v] = u;
        }
    }
    
    for(auto &item : query[u])
    {
        int v = item.first, id = item.second;
        if(st[v] == 2) p[id] = find(v);
    }
    
    st[u] = 2;
}

int main()
{
    int n; cin>>n;
    for(int i = 1;i < N;i ++) parent[i] = i;
    int root = 0;
    for(int i = 1;i <= n;i ++)
    {
        int u, v; cin>>u>>v;
        if(v == -1) root = u;
        else
        {
            e[u].push_back(v);
            e[v].push_back(u);
        }
    }
    
    int m; cin>>m;
    for(int i = 1;i <= m;i ++)
    {
        int x, y; cin>>x>>y;
        query[x].push_back(make_pair(y, i));
        query[y].push_back(make_pair(x, i));
        Data[i] = make_pair(x, y);
    }
    
    tarjan(root);
    
    return 0;
}

整除分块

$ans={\sum }_{i=1}^n{\displaystyle \frac{n}{i}}ans\; =\; \backslash sum\_\{i\; =\; 1\}^\{n\}\; \backslash displaystyle\{\backslash frac\{n\}\{i\}\}$

for(int l = 1, r;l <= n;l = r + 1)
{
	r = n / (n / l);
	ans += (r - l + 1) * (n / l);
}

AC自动机(trie图)

// 字典集中每个模式串在匹配串中出现次数
struct node
{
    int fail;
    int ch[26];
    int ans;
};
struct node NIL = {0};
struct trie
{
    vector<node> tr;
    vector<int> in;
    map<int, int> ref;
    int siz = 0;
    void insert(string s,int x)
    {
        if(!tr.size())
            tr.push_back(NIL);
        int place = 0;
        for (int i = 0; i < s.length();i++)
        {
            if (tr[place].ch[s[i] - 97] == 0)
            {
                tr[place].ch[s[i] - 97] = ++siz;
                tr.push_back(NIL);
                in.push_back(0);
            }
            place = tr[place].ch[s[i] - 97];
            // tr[place].ans ++; 统计每个字典串在字典中出现的次数，计数后topo()
        }
        ref[x] = place;
    }
    void build()
    {
        queue<int> q;
        for (int i = 0; i < 26;i++)
            if(tr[0].ch[i])
                q.push(tr[0].ch[i]);
        while(!q.empty())
        {
            int tp = q.front();
            q.pop();
            for (int i = 0; i < 26;i++)
                if(tr[tp].ch[i])
                {
                    tr[tr[tp].ch[i]].fail = tr[tr[tp].fail].ch[i];
                    in[tr[tr[tp].fail].ch[i]]++;
                    q.push(tr[tp].ch[i]);
                }
                else
                    tr[tp].ch[i] = tr[tr[tp].fail].ch[i];
        }
    }
    void query(string t)
    {
        int place = 0;
        for (int i = 0; i < t.length();i++)
        {
            place = tr[place].ch[t[i] - 97];
            tr[place].ans++;
        }
    }
    void topo()
    {
        queue<int> q;
        for (int i = 1; i <= siz;i++)
            if(!in[i])
                q.push(i);
        while(!q.empty())
        {
            int tp = q.front();
            q.pop();
            tr[tr[tp].fail].ans += tr[tp].ans;
            in[tr[tp].fail]--;
            if(!in[tr[tp].fail])
                q.push(tr[tp].fail);
        }
        //for (int i = 0; i <= siz;i++)
        //    printf("ANS:%d %d\n", i, tr[i].ans);
    }
};
 
void solve()
{
    int n; cin>>n;
    trie tr;
    for(int i = 1;i <= n;i ++)
    {
        string t; cin>>t;
        tr.insert(t, i);
    }
    tr.build();
    string s; cin>>s;
    tr.query(s);
    tr.topo();
    for(int i = 1;i <= n;i ++)
        cout<<tr.tr[tr.ref[i]].ans<<endl;
}
 
signed main()
{
    ios;
    int t = 1; // cin>>t;
    while(t --) solve();
    return 0;
}