ACM算法模板整理

史诗级ACM模板整理

基本语法

字符串函数

istream& getline (char* s, streamsize n );
istream& getline (char* s, streamsize n, char delim );

istream& getline (istream&  is, string& str, char delim);
istream& getline (istream&  is, string& str);

char * strncpy ( char * destination, const char * source, size_t num );
    if num > source, will padding with 0. no '\0' //strlen() + 1

const char * strrchr ( const char * str, int character );
const char * strchr ( const char * str, int character );
    NULL if not found

const char * strstr ( const char * str1, const char * str2 );
    return the first occurance, NULL if not found

size_t strspn ( const char * str1, const char * str2 );
    The length of the initial portion of str1 containing only characters that appear in str2.

size_t strcspn ( const char * str1, const char * str2 );

const char * strpbrk ( const char * str1, const char * str2 );
    return first occurance of ch among str2
char * strtok ( char * str, const char * delimiters);

控制精度

#include<iomanip>

cout<<fixed<<setprecision(2)<<3.14159<<endl;

Black-Tec

对拍

@echo off
:loop
echo %random% | ran >in.txt
bf <in.txt > std.txt
my <in.txt > my.txt
fc std.txt my.txt > nul
if not errorlevel 1 goto loop

fread读入优化

char buf[1<<21],*p1=buf,*p2=buf;
inline int getc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}

pbds

hash_table

#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <iostream>

using namespace std;
using namespace __gnu_pbds;
gp_hash_table<int, int> h;

void judge(int i) {
    if (h.find(i) == h.end())
        cout<<"No"<<endl;
    else
        cout<<"Yes"<<h[i]<<endl;
    return;
}
int main() {
    int i;
    h[15] = 1;
    h.insert(make_pair(12, 2));
    while (cin>>i)
        judge(i);
    return 0;
}

rb_tree

#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>

using namespace std;
using namespace __gnu_pbds;
tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> t, b;

signed main() {
    int v = 4;
    t.insert(5);
    t.insert(2);
    t.erase(t.lower_bound(0));
    t.order_of_key(5);
    t.find_by_order(1);
    t.join(b); // no repeat
    t.split(v, b);
    return 0;
}

字符串

KMP

void getFail(string &P,int *f) {
    int i,j;
    f[0]=f[1]=0;
    for (i=1;i<m;++i) {
        j=f[i];
        while (j&&P[i]!=P[j])   j=f[j];
        f[i+1]=P[i]==P[j]?j+1:0;
    }
    return;
}
void find(string &T,string &P,int *f) {
    int i,j;
    j=0;
    for (i=0;i<n;++i) {
        while (j&&T[i]!=P[j])   j=f[j];
        if (T[i]==P[j]) j++; //!!!
        if (j==m)
            printf("%d ",i-m+2);
    }
    return;
}

exKMP

#include <iostream>
#include <string>
#include <cstring>
#include <iterator>
using namespace std;

const int maxn = 1e5 + 1;
int nxtP[maxn], Lcp[maxn];
void exKMP(const char* P, int* nxt, const char* T, int* ext) {
    int i, mx = 0, p = 0, n = strlen(T), m = strlen(P); //mx: Position where doesn't fit.
    if (nxt == ext) {
        ext[0] = n;
        p = 1; mx = 1; i = 1;
        while (mx < n && mx - i < m && T[mx] == P[mx - i])  mx++;
    } else i = 0;

    for (; i < n; ++i)
        if (nxt[i - p] + i < mx)    ext[i] = nxt[i - p];
        else {
            if (i >= mx)    mx = i; //i >= mx
            while (mx < n && mx - i < m && T[mx] == P[mx - i])  mx++;
            ext[i] = mx - i;
            p = i;
        }
    return;
}
signed main() {
    string T, P;
    cin>>T>>P;
    exKMP(P.data(), nxtP, P.data(), nxtP);
    exKMP(P.data(), nxtP, T.data(), Lcp);
    copy(nxtP, nxtP + P.length(), ostream_iterator <int> (cout, " "));
    cout<<endl;
    copy(Lcp, Lcp + T.length(), ostream_iterator <int> (cout, " "));
    return 0;
}

Aho-Corasick 自动机

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <map>
using namespace std;

const int maxn = 2e5 + 1, maxm = 26;
int n, ans[maxn] = { 0 };
string P[maxn], T;
struct Trie {
    int ch[maxn][maxm], sz, val[maxn];
    int ind[maxn], lazy[maxn];
    map <int, int> e;
    Trie() {
        memset(ch[0], 0, sizeof(ch[0]));
        memset(val, 0, sizeof(val));
        sz = 1; //
    }
    void insert(const char *s, int v) {
        int len = strlen(s), u = 0, c;
        for (int i = 0; i < len; ++i) {
            c = s[i] - 'a';
            if (!ch[u][c]) {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0; //
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        if (val[u])
            ans[v - 1] = -val[u];
        else
            val[u] = v;
    }
};
struct Aho_Corasick: public Trie {
    int f[maxn], last[maxn];
    void get_Fail() {
        int j, u;
        queue <int> Q;
        f[0] = 0;
        for (auto x: ch[0])
            if (x) {
                Q.push(x);
                f[x] = 0;
                last[x] = 0;
            }
        while (!Q.empty()) {
            int r = Q.front();
            Q.pop();
            for (register int c = 0; c < maxm; ++c)
                if (ch[r][c]) {
                    u = ch[r][c];
                    Q.push(u);
                    j = f[r];
                    while (j && !ch[j][c])  j = f[j];
                    f[u] = ch[j][c];
                    last[u] = val[f[u]] ? f[u] : last[f[u]];
                    if (val[u] && last[u])
                        Add(val[u], val[last[u]]);
                }
        }
    }

    void find(const char* T) {
        int len = strlen(T), j = 0, c;
        for (register int i = 0; i < len; ++i) {
            c = T[i] - 'a';
            while (j && !ch[j][c])  j = f[j];
            j = ch[j][c];
            if (val[j]) print(j);
            else if (last[j])   print(last[j]);
        }
        return;
    }

    void print(int x) {
        lazy[val[x]]++;
/*          ans[val[x] - 1]++;
        if (last[x])
            print(last[x]); */
    }

    void Add(int x, int y) {
        ind[y]++;
        e.insert(make_pair(x, y));
    }
    void topocalc() {
        queue <int> Q;
        for (int x = 1; x <= n; ++x) if (!ind[x])
            Q.push(x);
        while (!Q.empty()) {
            int u, x = Q.front();   Q.pop();
            ans[x - 1] += lazy[x];
            if (e.find(x) != e.end()) {
                u = e[x];
                ind[u]--;
                lazy[u] += lazy[x];
                if (!ind[u])
                    Q.push(u);
            }
        }
    }
}AC;
void read() {
    cin>>n;
    for (int i = 0; i < n; ++i) {
        cin>>P[i];
        AC.insert(P[i].data(), i + 1);
    }
    cin>>T;
}
void solve() {
    AC.get_Fail();
    AC.find(T.c_str());
    AC.topocalc();
}
void print() {
    for (int i = 0; i < n; ++i)
        if (ans[i] >= 0)
            cout<<ans[i]<<endl;
        else
            cout<<ans[-ans[i] - 1]<<endl;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    read();
    solve();
    print();
    return 0;
}

后缀数组

#include <cstdio>
#include <iostream>

using namespace std;

int sa[maxn], l1[maxn], l2[maxn];
void build_SA(int n, int m, int *s) {
    int c[maxn], *x = l1, *y = l2, p;
    memset(c, 0, sezeof(c));
    for (i = 0; i < n; ++i) c[s[i]]++;
    for (i = 1; i < m; ++i) c[i] += c[i - 1];
    for (i = n - 1; i >= 0; --i)    x[--c[s[i]]] = s[i];
    for (k = 1; k <= n; k <<= 1) {
        p = 0;
        for (i = 0; i < k; ++i) y[++p] = x[i];
        for (i = 0; i < n - k; ++i)
            if (x[i] >= k)
                y[++p] = x[i] - k;

        memset(c, 0, sizeof(c));
        for (i = 0; i < n; ++i) c[x[i]]++;
        for (i = 1; i < m; ++i) c[i] += c[i - 1];
        for (i = n - 1; i >= 0; --i)    sa[--c[x[y[i]]]] = x[y[i]];
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        for (i = 0; i < n; ++i)
            x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
        if (p >= n) break;
        m = p;
    }
    return;
}
int main() {
    char s[255],l;
    scanf("%s", s);
    l = strlen(s);
    build_SA(l,s);
    return 0;
}

后缀自动机

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

const int sigma_size = 26, maxn = 1e6 + 1;
struct SAM {
    struct Node {
        int longest, fa;
        int ch[sigma_size];
        Node() {
            memset(ch, 0, sizeof(ch));
            longest = 0;
        }
    }am[maxn << 1];
    int las = 1, cnt = 1;
    int isnp[maxn << 1];
    void insert(int c) {
        int p = las, np = ++cnt;
        las = np;
        isnp[np] = 1;
        am[np].longest = am[p].longest + 1;
        for (; p && !am[p].ch[c]; p = am[p].fa) am[p].ch[c] = np;
        if (!p) am[np].fa = 1;
        else {
            int q = am[p].ch[c];
            if (am[q].longest == am[p].longest + 1) am[np].fa = q;
            else {
                int nq = ++cnt;
                am[nq] = am[q];
                am[np].fa = nq;
                am[nq].longest = am[p].longest + 1;
                am[q].fa = nq;
                for (; p && am[p].ch[c] == q; p = am[p].fa) am[p].ch[c] = nq;
            }
        }
    }
}AM;
long long ans;
int nxt[maxn << 2], head[maxn << 2], to[maxn << 2], cnt;
void Adde(int u, int v) {
    //cout<<"Add:"<<u<<' '<<v<<endl;
    to[++cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}
int dfs(int u) {
    int x, sz = AM.isnp[u];
    for (x = head[u]; x; x = nxt[x])
        sz += dfs(to[x]);
    if (sz != 1 && 1ll * sz * AM.am[u].longest > ans)
        ans = 1ll * sz * AM.am[u].longest;
    return sz;
}
signed main() {
    int n, i;
    string s;
    cin>>s;
    n = s.length();
    for (i = 0; i < n; ++i) AM.insert(s[i] - 'a');
    for (i = 1; i <= AM.cnt; ++i)
        Adde(AM.am[i].fa, i);
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

Manacher

#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn = 110001; //change this.
char s0[2 * maxn + 3],s[maxn];
int main() {
    int i,l = 0,mx = 1,len[2 * maxn + 3] = { 0 },ans = 0,p = 1;
    char ch;
    freopen("in.txt", "r", stdin);
    while ((ch = getchar())!= EOF)
        s0[l++] = ch;
    s0[l] = '\0';
    s[0] = '$';
    s[1] = '#';

    for (i = 0; i < l; ++i) {
        s[2 * (i + 1)] = s0[i];
        s[2 * i + 3] = '#';
    }
    s[2 * i + 2] = '\0';
    l = 2 * i + 1;
    for (i = 1; i < l; ++i) {
        if (i < mx)
            len[i] = min(mx - i, len[2 * p - i]); //chu zhi!!!
        else
            len[i] = 1;
        while (s[i + len[i]] == s[i - len[i]])  len[i]++;
        if (i + len[i] > mx) {
            mx = i + len[i];
            p = i;
        }
    }
    for (i = 1; i <= l; ++i)
        if (ans < len[i])
            ans = len[i];
    printf("%d\n",ans - 1);
    return 0;
}

回文自动机

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

const int maxn = 5e5 + 1, sigma_size = 26;
int ans;
struct PAM {
    int ch[maxn][sigma_size], fail[maxn], last, node[maxn], len[maxn], cnt, num[maxn];
    void insert(string& s) {
        int n = s.length();
        //cout<<s<<endl;
        fail[0] = 1;
        len[1] = -1;
        cnt = 1;
        last = 0;
        node[0] = '#';
        for (int i = 1; i < n; ++i) {
            int c = (s[i] - 97 + ans) % 26 + 97 - 'a', u;
            s[i] = (char)c + 'a';
            //cout<<s[i]<<' ';
            while (s[i] != s[i - len[last] - 1])    last = fail[last]; //bu yong pd !u
            if (!ch[last][c]) {
                node[++cnt] = c;
                len[cnt] = len[last] + 2;
                u = fail[last]; //last2
                while (s[i] != s[i - len[u] - 1])   u = fail[u];
                fail[cnt] = ch[u][c]; //ch
                ch[last][c] = cnt; //sequence!
                num[ch[last][c]] = num[fail[cnt]] + 1;
            }
            last = ch[last][c];
            ans = num[last];
            cout<<ans<<' ';
        }
        return;
    }
}P;
signed main() {
    string s;
    cin>>s;
    s.insert(0, 1, '#');
    P.insert(s);
    return 0;
}

数论算法

Lucas

#include <iostream>

using namespace std;
int P,px[100001];
int qp(int x,int a) {
    int ans = 1;
    if (a == 0)
        return 1;
    while (a) {
        if (a & 1)
            ans = 1ll * ans * x % P;
        x = 1ll * x * x % P;
        a = a >> 1;
    }
    return ans;
}
int inv(int x) {
    return qp(x, P - 2);
}
int C(int n,int m) {
    if (n < m)
        return 0;
    return 1ll * px[n] * inv(px[n - m]) * inv(px[m]) % P;
}
int Lucas(int n,int m) {
    if (m == 0)
        return 1;
    return 1ll * C(n % P, m % P) * Lucas(n / P, m / P) % P;
}
int main() {
    int n,m,i,T;
    cin>>T;
    while (T--) {
        cin>>n>>m>>P;
        px[0] = 1;
        for (i = 1; i < P; ++ i)
            px[i] = 1ll * px[i-1] * i % P;
        cout<<Lucas(n + m, m)<<endl;
    }
    return 0;
}

exLucas

#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;

long long n, m;
int P;

int C(long long int n, long long int m, int p, int pk);
int fac(long long int n, int p, int pk);
int CRT(int a, int m);
int inv (int m, int p);
void exgcd(int a, int b, long long int &x, long long int &y);
int main() {
    int pk, i, p, k;
    long long ans = 0;
    cin>>n>>m>>P;
    p = P;
    k = sqrt(p + 0.5);
    for (i = 2;i <= k; ++i)
        if (p % i == 0) {
            pk = 1;
            while (p % i == 0) {
                pk *= i;
                p /= i;
            }
            ans = (ans + 1ll * CRT(C(n, m, i, pk), P / pk)) % P;

        }
    if (p != 1)
        ans = (ans + 1ll * CRT(C(n, m, p, p), P / p)) % P;
    cout<<ans<<endl;
    return 0;
}

int ksm(int x, long long int n, int p) {
    int ans = 1;
    while (n) {
        if (n & 1)
            ans = 1ll * ans * x % p;
        n >>= 1;
        x = 1ll * x * x % p;
    }
    return ans;
}
int C(long long int n, long long int m, int p, int pk) {
    long long int k = 0;
    long long int i;
    if (n < m) //Important.Habit
        return 0;
    for (i = n; i; i /= p)
        k += i / p;
    for (i = m; i; i /= p)
        k -= i / p;
    for (i = n - m; i; i /= p)
        k -= i / p;
    return 1ll * fac(n, p, pk) * inv(1ll * fac(m, p, pk) * fac(n - m, p, pk) % pk, pk) % pk * ksm(p, k, pk) % pk;
}

int fac(long long int n, int p, int pk) {
    int ans = 1;
    register int i;
    if (!n)
        return 1;
    for (i = 1; i <= pk; ++i)
        if (i % p)
            ans = 1ll * ans * i % pk;
    ans = ksm(ans, n / pk, pk);
    for (i = 1; i <= n % pk; ++i)
        if (i % p)
            ans = 1ll * ans * i % pk;
    return 1ll * ans * fac(n / p, p, pk) % pk;
}
int CRT(int a, int m) {
    return 1ll * a * m % P * inv(m, P / m) % P;
}

int inv (int m, int p) {
    long long int x, y;
    exgcd(m, p, x, y);
    return (x + p) % p;
}

void exgcd(int a, int b, long long int &x, long long int &y) {
    int t;
    if (b == 0) {
        if (a != 1)
            printf("Error.\n");
        y = 0;
        x = 1;
        return;
    }
    exgcd(b, a % b, x, y);
    t = x;
    x = y;
    y = t - a / b * y;
    return;
}

Eular函数

int euler_phi(int n) {
    int m=(int)sqrt(n+0.5);
    int ans=n;
    for (int i=2;i<=m;++i)
        if (n%i==0) {
            ans=ans/i*(i-1);
            while (n%i==0)  n/=i;
        }
    if (n>1)    ans=ans/n*(n-1);
}

int phi[maxn];
void phi_table(int n) {
    for (int i=2;i<=n;++i)  phi[i]=0;
    phi[1]=1;
    for (int i=2;i<=n;++i)
        if (!phi[i])
            for (int j=i;j<=n;j+=i) {
                if (!phi[j])
                    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
}

BSGS

int log_mod(int a,int b,int n) {
    int m,v,e=1,i;
    m=(int)sprt(n+0.5);
    v=inv(pow_mod(a,m,n),n);
    map <int,int>x;
    x[1]=0;
    for (i=1;i<m;++i) {
        e=mul_mod(e,a,n);
        if (!x.count(e))    x[e]=i;
    }
    for (i=0;i<m;++i) {
        if (x.count(b)) return i*m+x[b];
        b=mul_mod(b,v,n);
    }
    return -1;
}

扩展的中国剩余定理

/*When using ExCluid, mind a large prime, better use gcd and divide.*/
#include <cstdio>
#include <utility>
#include <iostream>
#define ll long long int
using namespace std;

const int maxn = 1e5 + 1;
pair <ll, ll> P;
long long tmp;
void exgcd(long long int a, long long b, long long ans) {
    if (b == 0) {
        P.first = ans / a;
        P.second = 0;
    }
    else {
        exgcd(b, a % b, ans);
        tmp = P.second;
        P.second = P.first - a / b * P.second;
        P.first = tmp;
    }

    return;
}

ll gcd(ll a, ll b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll Gui_mul(ll x, ll n, ll mod) {
    ll ret = 0;
    int f = 1;
    if (n < 0) {
        f = -1;
        n = -n;
    }
    while (n) {
        if (n & 1)
            ret = (ret + x) % mod;
        n >>= 1;
        x = (x << 1) % mod;
    }
    return ret * f;
}
template <typename T>void gint(T& x) {
    char ch = getchar();
    x = 0;
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = 10 * x + (ch ^ 48);
        ch = getchar();
    }
    return;
}
int main() {
    int n, i;
    ll m[maxn], a[maxn], lcm, t, Gcd;
    gint(n);
    for (i = 1;i <= n; ++i) {
        gint(m[i]);
        gint(a[i]);
    }
    for (i = 2;i <= n; ++i) {
        Gcd = gcd(m[i], m[i - 1]);
        lcm = m[i] / Gcd * m[i - 1];
        t = a[i] - a[i - 1];

        exgcd(m[i - 1], m[i], Gcd);
        a[i] = (Gui_mul(Gui_mul(P.first, t / Gcd, m[i]), m[i - 1], lcm) + a[i - 1]) % lcm;
        m[i] = lcm;
        if (a[i] < 0)
            a[i] = (a[i] + m[i]) % m[i];
    }
    cout<<a[n]<<endl;
    return 0;
}

高斯消元

#include <cstdio>
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

const int maxn = 101;
typedef double Matrix[maxn][maxn];

int gauss_elimination(Matrix& A, int n) {
    int i, j, k, r;
    for (i = 0; i < n; ++i) {
        r = i;
        for (j = i + 1; j < n; ++j)
            if (fabs(A[j][i])>fabs(A[r][i]))
                r = j;
        if (r != i)
            for (j = i; j <= n; ++j)
                swap(A[r][j], A[i][j]);

        if (fabs(A[i][i]) < 1e-10)
            return -1;
        for (j = n; j >= i; --j)
            for (k = i + 1; k < n; ++k)
                A[k][j] -= A[k][i] / A[i][i] * A[i][j]; // -=

    }
    for (i = n - 1; i >= 0; --i) {
        for (j = n - 1; j > i; --j)
            A[i][n] -= A[j][n] * A[i][j];
        A[i][n] /= A[i][i];
    }
    return 0;
}
int main() {
    int n, i, j;
    Matrix A;
    cin>>n;
    for (i = 0; i < n; ++i)
        for (j = 0; j <= n; ++j)
            cin>>A[i][j];
    if (!gauss_elimination(A, n))
        for (i = 0; i < n; ++i)
            cout<<fixed<<setprecision(2)<<A[i][n]<<endl;
    else
        cout<<"No Solution"<<endl;
    return 0;
}

拉格朗日插值法

    ans = 0;
    for (i = 1; i <= n; ++i) {
        tmp = y[i];
        mot = 1;
        for (j = 1; j <= n; ++j)
            if (j != i) {
                tmp = tmp * (k - x[j]) % mod;
                mot = mot * (x[i] - x[j]) % mod;
            }
        ans = (ans + tmp * inv(mot)) % mod;
    }
    cout<<(ans + mod) % mod<<endl;

Mobius

    mu[1] = 1;
    for (register int i = 2; i < maxn; ++i) {
        if(!isnp[i]) {
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for (register int j = 0; j < cnt && i * prime[j] < maxn; ++j) {
            isnp[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
            mu[i * prime[j]] = -mu[i];
        }
    }

除法分块

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

int main() {
    int n, k, L, R, m;
    long long ans = 0;
    scanf("%d%d", &n, &k);
    m = min(n, k);
    for (L = 1; L <= m; L = R + 1) {
        R = min(k / (k / L), m);
        ans += (1ll * (R - L + 1) * (k % L + k % R) / 2);
    }
    if (n > k)
        ans += 1ll * k * (n - k);
    printf("%I64d\n", ans);
    return 0;
}

FFT

#include <cstdio>
#include <complex>
#include <iostream>
#include <cmath>
using namespace std;

const int maxn = 601;
const double PI = acos(-1);
int rev[maxn << 1], L;
void FFT(complex <double> *A, int len, int opt) {
    int i, j, k;

    complex <double> wn, w, t;
    for (i = 0; i < len; ++i)
        if (i < rev[i])
            swap(A[i], A[rev[i]]);
    for (i = 1; i < len; i <<= 1)  {
        wn = complex <double> (cos(PI / i), opt * sin(PI / i));
        for (j = 0; j < len; j += i * 2) {
            w = complex <double> (1, 0);
            for (k = 0; k < i; ++k) {
                t = w * A[j + i + k];
                A[j + k + i] = A[j + k] - t;  //
                A[j + k] = A[j + k] + t;
                w = w * wn;
            }
        }
    }
    return;
}
int main() {
    int i, len = 1, n, ans[maxn << 1] = { 0 };
    complex <double> A1[maxn << 1], A2[maxn << 1];
    char ch;
    cin>>n;
    while (len < 2 * n) {
        ++L;
        len <<= 1;
    }
    for (i = 0; i < len; ++i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1)<< (L - 1)); //
    ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    A1[n - 1] = ch ^ 48;
    for (i = n - 2; i >= 0; --i)
        A1[i] = getchar() ^ 48;
    ch = '0' - 1;
    while (ch < '0' || ch > '9')
        ch = getchar();
    A2[n - 1] = ch ^ 48;
    for (i = n - 2; i >= 0; --i)
        A2[i] = getchar() ^ 48;
    for (i = n; i < len; ++i) {
        A1[i] = 0;
        A2[i] = 0;
    }
    FFT(A1, len, 1);
    FFT(A2, len, 1);

    for (i = 0; i < len; ++i) //
        A1[i] = A1[i] * A2[i];

    FFT(A1, len, -1);

    for (i = 0; i < len; ++i) {
        ans[i] += (int)(real(A1[i]) / len + 0.1);// +0.1;+=
        if (ans[i] >= 10) {
            ans[i + 1] += ans[i] / 10;
            ans[i] = ans[i] % 10;
        }
    }
    while (len > 1)
        if (ans[len - 1])
            break;
        else
            len--;
    while (len--)
        printf("%d", ans[len]);
    putchar('\n');
    return 0;
}

数据结构

树状数组（区间修改，区间查询）

int vdi[maxn],vd[maxn];

int lowbit(int x) {
    return x&(-x);
}
void _add(int x,int vl,int *C) {
    while (x<=N + 1) {
        C[x]=(0ll + C[x]+vl)%P;
        x+=lowbit(x);
    }
    return;
}
int _sum(int x,int *C) {
    int ret=0;
    while (x>0) {
        ret=(0ll + ret+C[x])%P;
        x-=lowbit(x);
    }
    return ret;
}
void add(int x,int y,int vl) {
    if (x==0||y==0) {
        return;
    }
    _add(x,vl,vd);
    _add(y+1,P -vl,vd); //-vl
    _add(x,1ll * vl*x % P,vdi);
    _add(y+1,1ll * (P - vl)*(y+1) % P,vdi);
    return;
}
int sum(int x) { //Erred.
    return (P+1ll * _sum(x,vd)*(x+1)-_sum(x,vdi))%P;
}
int ask(int x,int y) {
    return (0ll+P+sum(y)-sum(x-1))%P;
}

线段树

#include <iostream>
#include <cstdio>

using namespace std;
/* setv != -1 */
const int maxn = 500001 * 2 + 1, INF = 0x7f7f7f7f;
int minv[maxn], maxv[maxn], sumv[maxn], setv[maxn], addv[maxn];
int ql, qr, v, p, _min, _max, _sum; //A[p] = v

void query(int o, int L, int R, int add);
void pushdown(int o);
void maintain(int o, int L, int R);
void updates(int o, int L, int R); //xian set hou add;
void updatea(int o, int L, int R);
int main() {
    int n, i, opt;
    cin>>n;
    for (i = 1; i <= n; ++i) {
        cin>>v;
        ql = qr = i;
        updates(1, 1, n);
    }
    for (i = 1; i <= 5; ++i) {
        cin>>opt>>ql>>qr;
        _sum = 0;
        _min = INF;
        _max = -INF;
        switch (opt) {
        case 0: cin>>v; updates(1, 1, n); break;
        case 1: cin>>v; updatea(1, 1, n); break;
        case 2: query(1, 1, n, 0); cout<<_min<<' '<<_max<<' '<<_sum<<endl;
        }
    }
    return 0;
}

void query(int o, int L, int R, int add) { //add shang wu set
    if (setv[o] != -1) {
        _sum += (setv[o] + add + addv[o]) * (min(qr, R) - max(ql, L) + 1);
        _min = min(_min, setv[o] + add + addv[o]);
        _max = max(_max, setv[o] + add + addv[o]);
    }
    else
        if (ql <= L && qr >= R) {
            _sum += sumv[o] + add * (R - L + 1);
            _min = min(_min, minv[o] + add);
            _max = max(_max, maxv[o] + add);
        }
        else {
            int lc = 2 * o, rc = 2 * o + 1, M = L + (R - L) / 2;
            if (ql <= M)
                query(lc, L, M, add + addv[o]);
            if (qr > M)
                query(rc, M + 1, R, add + addv[o]);
        }
    return;
}
void updates(int o, int L, int R) { //set qian wu add, set shang ke you add.
    if (L >= ql && qr >= R) {
        setv[o] = v;
        addv[o] = 0;
    }
    else {
        int lc = 2 * o, rc = 2 * o + 1, M = L + (R - L) / 2;
        pushdown(o);
        if (ql <= M)
            updates(lc, L, M);
        else
            maintain(lc, L, M);
        if (qr > M)
            updates(rc, M + 1, R);
        else
            maintain(rc, M + 1, R);
    }
    maintain(o, L, R);
    return;
}
void updatea(int o, int L, int R) {
    if (L >= ql && qr >= R)
        addv[o] += v;
    else {
        int lc = 2 * o, rc = 2 * o + 1, M = L + (R - L) / 2;
        pushdown(o);
        if (ql <= M)
            updatea(lc, L, M);
        else
            maintain(lc, L, M);
        if (qr > M)
            updatea(rc, M + 1, R);
        else
            maintain(rc, M + 1, R);
    }
    maintain(o, L, R);
    return;
}

void pushdown(int o) {
    int lc = 2 * o, rc = 2 * o + 1;
    if (setv[o] == -1) {
        addv[lc] += addv[o];
        addv[rc] += addv[o];
    }
    else {
        setv[lc] = setv[rc] = setv[o] + addv[o];
        addv[lc] = 0; addv[rc] = 0;
    }
    addv[o] = 0;
    setv[o] = -1;
}

void maintain(int o, int L, int R) {
    int lc = 2 * o, rc = 2 * o + 1;
    if (setv[o] != -1) {
        sumv[o] = setv[o] * (R - L + 1);
        minv[o] = setv[o];
        maxv[o] = setv[o];
    }
    else
        if (L < R) {
            sumv[o] = sumv[lc] + sumv[rc];
            minv[o] = min(minv[lc], minv[rc]);
            maxv[o] = max(maxv[lc], maxv[rc]);
        }
    sumv[o] += addv[o] * (R - L + 1);
    minv[o] += addv[o];
    maxv[o] += addv[o];
    return;
}

主席树

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 2e5 + 1;
int a[maxn], b[maxn], tot, p, v;
int cnt, C[maxn << 5], rt[maxn], lc[maxn << 5], rc[maxn << 5];
int build(int L, int R) {
    int mid = L + (R - L) / 2, u = cnt++;
    if (L == R) {
        C[u] = 0;
        return u;
    }
    lc[u] = build(L, mid);
    rc[u] = build(mid + 1, R);
    return u;
}
int update(int o, int L = 1, int R = tot) {
    int mid = L + (R - L) / 2, u = cnt++;
    if (L == R) {
        C[u] = C[o] + v;
        return u;
    };
    lc[u] = lc[o];  rc[u] = rc[o];
    if (p <= mid)   lc[u] = update(lc[u], L, mid);
    else    rc[u] = update(rc[u], mid + 1, R);
    C[u] = C[lc[u]] + C[rc[u]];

    return u;
}
int query(int o1, int o2, int k, int L = 1, int R = tot) {
    int mid = L + (R - L) / 2;
    if (L == R) return mid;
    if (k <= C[lc[o2]] - C[lc[o1]]) return query(lc[o1], lc[o2], k, L, mid);
    else    return query(rc[o1], rc[o2], k - (C[lc[o2]] - C[lc[o1]]), mid + 1, R);
}

signed main() {
    int n, m, i, l, r, k;
    freopen("testdata.in", "r", stdin);
    freopen("my.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for (i = 0; i < n; ++i) {
        cin>>a[i];
        b[i] = a[i];
    }
    sort(b, b + n);
    tot = unique(b, b + n) - b;
    rt[0] = build(1, tot);
    v = 1;
    for (i = 0; i < n; ++i) {
        p = lower_bound(b, b + tot, a[i]) - b + 1;
        rt[i + 1] = update(rt[i]);
    }
    while (m--) {
        cin>>l>>r>>k;
        cout<<b[query(rt[l - 1], rt[r], k) - 1]<<endl;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

Treap

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

const int maxn = 1e5 + 1, INF = 0x7f7f7f7f;
int size[maxn], v[maxn], fix[maxn], son[maxn][2], num[maxn], cnt, R;

void pushup(int p) {
    size[p] = size[son[p][0]] + size[son[p][1]] + num[p];
    return;
}
void rotate(int &p, int dir) {
    int t = son[p][dir];
    son[p][dir] = son[t][dir ^ 1];
    son[t][dir ^ 1] = p;
    p = t;
    pushup(son[p][0]);
    pushup(son[p][1]);
    return;
}
void ins(int &p, int x) {
    if (!p) {
        p = ++cnt;
        v[p] = x;
        num[p] = 1;
        size[p] = 1;
        fix[p] = rand();
        return;
    }
    if (v[p] == x) {
        num[p]++;
        size[p]++;
        return;
    }
    int d = (x > v[p]);
    ins(son[p][d], x);
    if ((fix[p] < fix[son[p][d]]) != d)
        rotate(p, d);
    pushup(p);
}
void del(int &p, int x) {
    if (!p) {
        cout<<"Not exist."<<endl;
        return;
    }
    if (v[p] > x)
        del(son[p][0], x);
    if (v[p] < x)
        del(son[p][1], x);
    if (v[p] == x) {
        if (!son[p][0] && !son[p][1]) {
            num[p]--;
            if (num[p] == 0)
                p = 0;
        }
        else if (!son[p][0] && son[p][1]) {
            rotate(p, 1);
            del(son[p][0], x);
        }
        else if (son[p][0] && !son[p][1]) {
            rotate(p, 0);
            del(son[p][1], x);
        }
        else if (num[p] > 1)
            num[p]--;
        else {
            int d = (fix[son[p][0]] < fix[son[p][1]]);
            rotate(p, d);
            del(son[p][d ^ 1], x);
        }
    }
    pushup(p);
    return;
}
int getrank(int p, int x) {
    if (!p)
        return 0;
    if (v[p] == x)
        return size[son[p][0]] + 1;
    if (v[p] > x)
        return getrank(son[p][0], x);
    else
        return size[son[p][0]] + num[p] + getrank(son[p][1], x);
}
int getnum(int p, int r) {
    int left = size[son[p][0]];
    if (!p)
        return -1;
    if (left >= r)
        return getnum(son[p][0], r);
    if (left < r && left + num[p] >= r)
        return v[p];
    else
        return getnum(son[p][1], r - left - num[p]);
}
int getpre(int p, int x) {
    if (!p)
        return -INF;
    if (v[p] >= x)
        return getpre(son[p][0], x);
    else
        return max(v[p], getpre(son[p][1], x));
}
int getsuf(int p, int x) {
    if (!p)
        return INF;
    if (v[p] <= x)
        return getsuf(son[p][1], x);
    else
        return min(v[p], getsuf(son[p][0], x));
}
int main() {
    int n, opt, x;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    while (n--) {
        cin>>opt>>x;
        switch (opt) {
            case 1:ins(R, x);break;
            case 2:del(R, x);break;
            case 3:cout<<getrank(R, x)<<endl;break;
            case 4:cout<<getnum(R, x)<<endl;break;
            case 5:cout<<getpre(R, x)<<endl;break;
            case 6:cout<<getsuf(R, x)<<endl;break;
        }
    }
    return 0;
}

Splay

#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstdlib>
using namespace std;

const int maxn = 1e5 + 5;
int n;
int ch[maxn][2], fa[maxn], size[maxn], num[maxn], cnt, R, v[maxn], rev[maxn];
void pushdown(int x) {
    if (rev[x]) {
        swap(ch[x][0], ch[x][1]);
        rev[ch[x][0]] ^= 1;
        rev[ch[x][1]] ^= 1;
        rev[x] = 0;
    }
}
void pushup(int x) {
    size[x] = num[x] + size[ch[x][0]] + size[ch[x][1]];
}
int kth(int k) {
    int cur = R;
    if (k > cnt)
        cout<<"Err"<<endl;
    while (1) {
        pushdown(cur);
        if (ch[cur][0] && k <= size[ch[cur][0]])
            cur = ch[cur][0];
        else if (k > size[ch[cur][0]] + num[cur]) {
            k -= (size[ch[cur][0]] + num[cur]);
            cur = ch[cur][1];
        }
        else
            return cur;
    }
}

void output(int x) {
    pushdown(x);
    if (ch[x][0])   output(ch[x][0]);
    if (num[x] != 0 && v[x] <= n && v[x] >= 1)
        for (int i = 1; i <= num[x]; ++i)
            cout<<v[x]<<' ';
    if (ch[x][1])   output(ch[x][1]);
}
void rotate(int x) {
    int d = (ch[fa[x]][1] == x), p = fa[x];
    pushdown(p);
    pushdown(x);
    fa[x] = fa[p];
    if (fa[p])
        ch[fa[p]][ch[fa[p]][1] == p] = x;
    ch[p][d] = ch[x][d ^ 1];
    if (ch[x][d ^ 1])
        fa[ch[x][d ^ 1]] = p;
    ch[x][d ^ 1] = p;
    fa[p] = x;

    pushup(x);
    pushup(p);
    return;
}

void splay(int x, int goal = 0) {
    while (fa[x] != goal) {
        int y = fa[x], z = fa[y];
        pushdown(z);
        pushdown(y);
        if (z != goal) {
            if ((ch[fa[x]][1] == x) == (ch[fa[y]][1] == y))
                rotate(y);
            else
                rotate(x);
        }
        rotate(x);

    }
    if (!goal)
        R = x;
}

void insert(int val) {
    int cur = R, p = fa[cur];
    while (cur && v[cur] != val) {
        p = cur;
        cur = ch[cur][val > v[cur]];
    }
    if (cur) {
        num[cur]++;
        size[cur++];
    }
    else {
        cur = ++cnt;
        if (p)
            ch[p][val > v[p]] = cur;
        v[cur] = val;
        fa[cur] = p;
        num[cur] = size[cur] = 1;
    }
    splay(cur);
}
void find(int val) {
    if (!R)
        return;
    int cur = R;
    while (v[cur] != val && ch[cur][v[cur] < val])
        cur = ch[cur][v[cur] < val]; //
    splay(cur);
}
void reverse(int l, int r) {
    int x = kth(l - 1), y = kth(r + 1);

    splay(x);
    splay(y, x);
    rev[ch[y][0]] ^= 1;
}
int pre(int val) {
    find(val);
    if (v[R] < val)
        return R;
    int cur = ch[R][0];
    while (ch[cur][1]) //
        cur = ch[cur][1];
    return cur;
}
int suc(int val) {
    find(val);
    if (v[R] > val)
        return R;
    int cur = ch[R][1];
    while (ch[cur][0])
        cur = ch[cur][0];
    return cur;
}
void remove(int val) {
    int nxt = suc(val), lst = pre(val);
    splay(lst);
    splay(nxt, lst);
    int del = ch[lst][0];
    if (num[del] > 1) {
        num[del]--;
        rotate(del);
    }
    else {
        ch[nxt][0] = 0;
        rotate(nxt);
    }
    return;
}
int buildtree(int x, int y, int fat) {
    int mid = x + (y - x) / 2;
    if (x < mid) {
        ch[mid + 1][0] = buildtree(x, mid - 1, mid + 1);
        size[mid + 1] += size[ch[mid + 1][0]];
    }
    size[mid + 1] += 1;
    num[mid + 1] = 1;
    v[mid + 1] = mid;
    fa[mid + 1] = fat;
    if (mid < y) {
        ch[mid + 1][1] = buildtree(mid + 1, y, mid + 1);
        size[mid + 1] += size[ch[mid + 1][1]];
    }
    return mid + 1;
}
int main() {
    int m, x, y;
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    R = buildtree(0, n + 1, 0);
    cnt = n + 2;
    while (m--) {
        cin>>x>>y;
        reverse(x + 1, y + 1);
    }
    output(R);
    return 0;
}

图论

Dijkstra

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;
const int maxn=100001,INF=1e9;
struct Edge {
    int from,to,dist;
    Edge(int u,int v,int d):
        from(u),
        to(v),
        dist(d){}
};
struct Dijkstra {
    int n;
    vector <Edge> edges;
    vector <int> G[maxn];
    int d[maxn];

    Dijkstra(int n1) {
        n=n1;
        for (int i=1;i<=n;++i)
            d[i]=INF;
        edges.clear();
        for (int i=1;i<=n;++i)
            G[i].clear();
        return;
    }
    void AddEdge(int u,int v,int dist) {
        edges.push_back((Edge) (u,v,dist));
        G[u].push_back(edges.size()-1);
        return;
    }
    struct HeapNode{
        int u,d;
        void HeapNode(int m,int k):
            u(m),
            d(k) {}
        bool operator <(const HeapNode& rhs) const {
            return d<rhs.d;
        }
    };
    void dijkstra(int S) {
        priority_queue <HeapNode> Q;
        d[S]=0;
        Q.push((HeapNode) (S,0));
        while (!Q.empty()) {
            HeapNode x=Q.top();Q.pop();
            if (x.d!=d[u])  continue;
            int u=x.u,sz=G[u].size();
            for (int j=0;j!=sz;++j) {
                Edge& e=edges[G[u][j]];
                if (d[e.to]>d[u]+e.dist) {
                    d[e.to]=d[u]+e.dist;
                    Q.push(HeapNode (e.to,d[e.to]));
                }
            }
        }
        return;
    }
};
int main() {
    int N,M,S,u,v,w;
    cin>>N>>M>>S;
    Dijkstra D(N);
    for (int i=1;i<=M;++i) {
        cin>>u>>v>>w;
        D.AddEdge(u,v,w);
    }
    D.dijkstra(S);
    for (int i=1;i<=N;++i)
        cout<<D.d[i]<<' ';
    return 0;
}

Bellman-Ford

const int maxn=100,maxm=1000;
void Bellman-Ford(int n,int m,int S) {
    int w[maxn],u[maxn],v[maxn],i,j;
    for (i=1;i<=m;++i)
        cin>>w[i]>>u[i]>>v[i];
    for (k=1;k<n;++k)
        for (i=1;i<=m;++i) {
            int x=u[i],y=v[i];
            if (d[x]<INF)
                d[y]=min(d[y],d[x]+w[i]);
        }
}

Floyd

树

LCA

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=500001,maxm=maxn*2;
int neext[maxm],to[maxm],head[maxn],cnt,
    p[maxn][21],deep[maxn],lg[21];
void add(int x,int y) {
    to[++cnt]=y;
    neext[cnt]=head[x];
    head[x]=cnt;
    return;
}
int LCA(int x,int y) {
    int i;
    if (deep[x]<deep[y])    swap(x,y);
    while (deep[x]>deep[y])
        x=p[x][lg[deep[x]-deep[y]]-1];
    if (x==y)   return x;
    for (i=lg[deep[x]]-1;i>=0;--i)
        if (p[x][i]!=p[y][i]) {
            x=p[x][i];
            y=p[y][i];
        }
    if (p[x][0]==p[y][0])   return p[x][0];
    return -1;
}
void dfs(int n,int d) {
    for (int i=head[n];i;i=neext[i]) {
        int x=to[i];
        if (!deep[x]) {
            deep[x]=d+i; //tiao zheng shun xu,hou dfs.
            p[x][0]=n;
            dfs(x,d+1);
        }
    }
    return;
}
int main() {
    int N,M,S,x,y,i,j;
    scanf("%d%d%d",&N,&M,&S);
    for (i=1;i<=N;++i)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i); //
    for (i=1;i<N;++i) {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    p[S][0]=S;
    deep[S]=1;
    dfs(S,0);
    for (j=1;j<=20;++j)
        for (i=1;i<=N;++i)
            p[i][j]=p[p[i][j-1]][j-1];
    printf("aa%daa",p[5][0]);
    for (i=1;i<=M;++i) {
        scanf("%d%d",&x,&y);
        printf("%d\n",LCA(x,y));
    }
    return 0;
}

树链剖分

//BIT when * yao qu moooooooooooooooooo * 6 months.
#include <cstdio>
#include <cassert>
using namespace std;
const int maxn=(int)1e5+1;
int N,R,P;
int nxt[maxn*2],to[maxn*2],head[maxn],cnt;
int size[maxn],fa[maxn],id[maxn],cntid,deep[maxn],son[maxn],rank[maxn],top[maxn];
int vdi[maxn],vd[maxn];
int Rint(int &x) {
    char ch=getchar();
    x=0;
    while (ch<'0'||ch>'9')
        ch=getchar();
    while (ch>='0'&&ch<='9') {
        x=x*10+(ch^48);
        ch=getchar();
    }
    return x;
}
int lowbit(int x) {
    return x&(-x);
}
void _add(int x,int vl,int *C) {
    while (x<=N + 1) {
        C[x]=(0ll + C[x]+vl)%P;
        x+=lowbit(x);
    }
    return;
}
int _sum(int x,int *C) {
    int ret=0;
    while (x>0) {
        ret=(0ll + ret+C[x])%P;
        x-=lowbit(x);
    }
    return ret;
}
void add(int x,int y,int vl) {
    if (x==0||y==0) {
        return;
    }
    _add(x,vl,vd);
    _add(y+1,P -vl,vd); //-vl
    _add(x,1ll * vl*x % P,vdi);
    _add(y+1,1ll * (P - vl)*(y+1) % P,vdi);
    return;
}
int sum(int x) { //Erred.
    return (P+1ll * _sum(x,vd)*(x+1)-_sum(x,vdi))%P;
}
int ask(int x,int y) {
    return (0ll+P+sum(y)-sum(x-1))%P;
}
void Adde(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
    return;
}
void dfs1(int x) {
    int i,t;
    size[x]=1;//woc
    deep[x]=deep[fa[x]]+1;

    for (i=head[x];i;i=nxt[i]) {
        t=to[i];
        if (t!=fa[x]) {
            fa[t]=x;
            dfs1(t);
            size[x]+=size[t];
            if (size[son[x]]<size[t]) //kuo hao.
                son[x]=t;
        }
    }
    return;
}
void dfs2(int x,int t) {
    int i,tto;
    id[x]=++cntid;
    rank[cntid]=x;
    top[x]=t;
    if (!son[x])
        return;
    dfs2(son[x],t);
    for (i=head[x];i;i=nxt[i]) {
        tto=to[i];
        if (tto!=fa[x]&&tto!=son[x])
            dfs2(tto,tto);
    }
    return;
}
void addpath(int x,int y,int vl) {
    while (top[x]!=top[y])
        if (deep[top[x]]>deep[top[y]]) {
            add(id[top[x]],id[x],vl);
            x=fa[top[x]];
        }
        else {
            add(id[top[y]],id[y],vl);
            y=fa[top[y]];
        }
    if (id[x]<=id[y]) //same Hchain.
        add(id[x],id[y],vl);
    else
        add(id[y],id[x],vl);
    return;
}
int askpath(int x,int y) {
    long long ret=0;
    while (top[x]!=top[y]) {
        if (deep[top[x]]>deep[top[y]]) {
            ret+=ask(id[top[x]],id[x]);
            x=fa[top[x]];
        }
        else {
            ret+=ask(id[top[y]],id[y]);
            y=fa[top[y]];
        }
        ret%=P;
    }
    if (deep[x]>deep[y])
        ret+=ask(id[y],id[x]);
    else
        ret+=ask(id[x],id[y]);
    return (int)(ret%P);
}

signed main() {
    int i,M,u,v,op,x,y,z,v0[maxn];
    //freopen("testdata.in", "r", stdin);
    //freopen("my.out", "w", stdout);
    Rint(N);Rint(M);Rint(R);Rint(P);
    for (i=1;i<=N;++i) {
        Rint(v0[i]);
    }
    for (i=1;i<N;++i) {
        Rint(u);Rint(v);
        Adde(u,v);
        Adde(v,u);
    }
    dfs1(R);
    dfs2(R,R);
    for (i=1;i<=N;++i)
        add(id[i],id[i],v0[i]);
    while (M--) {
        Rint(op);
        switch (op) {
            case 1:
                Rint(x);Rint(y);Rint(z);
                addpath(x,y,(0ll+P + z)%P); //
                break;
            case 2:
                Rint(x);Rint(y);
                printf("%d\n",askpath(x,y));
                break;
            case 3:
                Rint(x);Rint(z);
                add(id[x],id[x]+size[x]-1,(0ll+P + z)%P);//
                break;
            case 4:
                Rint(x);
                printf("%d\n",ask(id[x],id[x]+size[x]-1));
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

树上点分治

#include <iostream>
using namespace std;

const int maxn = 2e4 + 1;
int nxt[maxn << 1], head[maxn], to[maxn << 1], w[maxn << 1], ecnt;
int ans, rt, d[3], mnsz, sz[maxn], vis[maxn], tot;

int vv[maxn];
void AddE(int u, int v, int le) {
    to[++ecnt] = v;
    w[ecnt] = le;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
    return;
}
int getroot(int u, int fa) {
    static int cnt = 0;
    cnt++;
    if (vv[u])
        cout<<"Visited! @"<<u<<", fa = "<<fa<<endl;
    vv[u] = 1;
    int mx = 0;
    sz[u] = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (vis[v] || v == fa)
            continue;
        sz[u] += getroot(v, u);
        mx = max(mx, sz[v]);
    }
    mx = max(mx, tot - sz[u]);
    if (mx < mnsz) {
        rt = u;
        mnsz = mx;
    }
    cnt--;
    vv[u] = 0;
    return sz[u];
}
void getd(int u, int fa, int dis) {
    d[dis % 3]++;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (vis[v] || v == fa)  continue;
        getd(v, u, (dis + w[i]) % 3);
    }
}
int getans(int u, int dis) {
    d[0] = d[1] = d[2] = 0;
    getd(u, -1, dis);
    return d[0] * d[0] + d[1] * d[2] * 2;
}
void solve(int u) {
    vis[u] = 1;
    ans += getans(u, 0);
    for (int x = head[u]; x; x = nxt[x]) {
        int v = to[x];
        if (vis[v])
            continue;
        ans -= getans(v, w[x]);
        mnsz = tot = sz[v]; rt = 0; getroot(v, -1);
        solve(rt);
    }
    return;
}
int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int vid[maxn], id[maxn], cc;
void test(int u, int fa) {
    if (vid[u] == 1) {
        cout<<"Err "<<cc<<endl;
        for (int i = 1; i <= cc; ++i)
            cout<<id[i]<<' ';
        return;
    }
    vid[u] = 1;
    id[++cc] = u;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v != fa)
            test(v, u);
    }
    return;
}
signed main() {
    int n, u, v, i, t, ww;
#ifndef ONLINE_JUDGE
freopen("testdata.in", "r", stdin);
#endif
    cin>>n;
    for (i = 0; i < n - 1; ++i) {
        cin>>u>>v>>ww;
        ww = ww % 3;
        AddE(u, v, ww); AddE(v, u, ww);
    }
    test(1, -1);
    mnsz = tot = n; getroot(1, -1);
    t = gcd(ans, n * n);
    cout<<ans / t<<'/'<<n * n / t<<endl;
    return 0;
}

CV-BCC 无向图的双连通分量

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 2e4 + 1;
int dfs_clock, pre[maxn], iscut[maxn], bccno[maxn], bcc_count;
struct Edge {
    int u, v;
};
vector <int> bcc[maxn], G[maxn];
stack <Edge> S;
void AddE(int u, int v) {
    G[u].push_back(v);
}
int tarjan(int u, int fa) {
    int lowu = pre[u] = ++dfs_clock, child = 0;
    for (auto v: G[u]) {
        if (!pre[v]) {
            child++;
            S.push((Edge) {u, v});
            int lowv = tarjan(v, u);
            lowu = min(lowu, lowv);
            if (lowv >= pre[u]) {
                iscut[u] = 1;
                ++bcc_count;
                bcc[bcc_count].clear();
                //cout<<dfs_clock<<' '<<u<<'>'<<v<<','<<lowv<<'|'<<bcc_count<<endl;
                while (1) {
                    Edge e = S.top();   S.pop();
                    if (bccno[e.u] != bcc_count) {
                        bcc[bcc_count].push_back(e.u);
                        bccno[e.u] = bcc_count;
                    }
                    if (bccno[e.v] != bcc_count) {
                        bcc[bcc_count].push_back(e.v);
                        bccno[e.v] = bcc_count;
                    }
                    if (e.u == u && e.v == v)   break;
                }
            }
        } else if (pre[v] < pre[u] && v != fa) {
            S.push((Edge) {u, v});
            lowu = min(lowu, pre[v]); //Err
        }
    }
    if (fa == -1 && child == 1) iscut[u] = 0; //Err
    return lowu;
}
signed main() {
    int n, m, u, v, i;
    cin>>n>>m;
    while (m--) {
        cin>>u>>v;
        AddE(u, v);
        AddE(v, u);
    }
    for (i = 1; i <= n; ++i)
        if (!pre[i])
            tarjan(i, -1);
    cout<<count(iscut + 1, iscut + n + 1, 1)<<endl;
    for (i = 1; i <= n; ++i)
        if (iscut[i])
            cout<<i<<' ';
    return 0;
}

SCC 有向图的强连通分量

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int maxn = 1e4 + 1;
int n;
int pre[maxn], dfs_clock, sccno[maxn], scc_count;
int c[maxn], topo[maxn];
vector <int> G[maxn], GA[maxn], scc[maxn];
stack <int> S;
void AddE(int u, int v) {
    G[u].push_back(v);
}
void AddED(int u, int v) {
    //cout<<"Add"<<u<<' '<<v<<endl;
    GA[u].push_back(v);
}
int tarjan(int u) {
    int lowlinku = pre[u] = ++dfs_clock;
    S.push(u);
    for (auto x: G[u])
        if (!pre[x]) {
            int lowlinkv = tarjan(x);
            lowlinku = min(lowlinku, lowlinkv);
        } else if (!sccno[x])
            lowlinku = min(lowlinku, pre[x]);
    if (lowlinku == pre[u]) {
        ++scc_count;
        scc[scc_count].clear();
        //cout<<endl<<scc_count<<":";
        while (1) {
            int v = S.top(); S.pop();
            scc[scc_count].push_back(v);
            sccno[v] = scc_count;
            //cout<<v<<' ';
            if (v == u) break;
        }
    }
    return lowlinku;
}
int dfs(int u) {
    static int cnt = scc_count;
    if (c[u] == -1)
        return false;
    c[u] = -1;
    for (auto v: GA[u])
        if (!c[v] && !dfs(v))   return false;
    c[u] = 1;
    topo[cnt--] = u;
    return true;
}
int toposort(int n) {
    for (int i = 1; i <= n; ++i)
        if (!c[i])
            if (!dfs(i))
                return false;
    return true;
}

signed main() {
    int m, i, u, v;
    cin>>n>>m;
    while (m--) {
        cin>>u>>v;
        AddE(u, v);
    }
    for (i = 1; i <= n; ++i) {
        if (!pre[i])
            tarjan(i);
    }
    for (i = 1; i <= n; ++i) //Err Impppp
        for (int v: G[i]) if (sccno[i] != sccno[v]) //Err2.
            AddED(sccno[i], sccno[v]);
    if (!toposort(scc_count))
        cout<<"Shit!"<<endl;
    return 0;
}

网络流

Edmonds-Karp

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
const int infinity=1e9,maxn=1e4+1;
struct EdmondsKarp {
    struct Edge {
        int from,to,cap,flow;
        Edge(int u,int v,int c,int f):
            from(u),to(v),cap(c),flow(f){}
    };

    int n,m,aug[maxn],p[maxn];
    vector <int> G[maxn];
    vector <Edge> edges;

    EdmondsKarp(int n) {
        for (int i=0;i<=n;++i)  G[i].clear();
        edges.clear();
    }

    void AddEdge(int u,int v,int cap) {
        edges.push_back(Edge(u,v,cap,0));
        edges.push_back(Edge(v,u,0,0));
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
        return;
    }

    int MaxFlow(int S,int T) {
        int flow=0;
        while (1) {
            memset(aug,0,sizeof(aug));
            queue <int> Q;
            Q.push(S);
            aug[S]=infinity;
            p[S]=-1;
            while (!Q.empty()) {
                int x=Q.front();
                Q.pop();
                for (int j=0;j<G[x].size();++j) {
                    Edge &e=edges[G[x][j]];
                    if (!aug[e.to]&&e.cap>e.flow) {
                        p[e.to]=G[x][j];
                        aug[e.to]=min(aug[x],e.cap-e.flow);
                        Q.push(e.to);
                    }
                }
                if (aug[T]) break;
            }
            if (!aug[T])    break;
            for (int u=T;u!=S;u=edges[p[u]].from) {
                edges[p[u]].flow+=aug[T];
                edges[p[u]^1].flow-=aug[T];
            }

            flow+=aug[T];
        }
        return flow;
    }
};
int main() {
    int N,M,S,T,u,v,f;
    cin>>N>>M>>S>>T;
    EdmondsKarp E(N);
    for (int i=1;i<=M;++i) {
        cin>>u>>v>>f;
        E.AddEdge(u,v,f);
    }
    cout<<E.MaxFlow(S,T)<<endl;
    return 0;
}

MinCostMaxFlow

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define maxn 5001
#define INF 0x7f7f7f7f
using namespace std;
struct MCMF {
    int flow,cost,m;
    MCMF ():
        flow(0),
        cost(0){
            E.clear();
        }

    struct Edges {
        int to,flow,cost,cap;
    };
    vector <Edges> E;
    vector <int> G[maxn];
    void Adde(int u,int v,int w,int f) {
        E.push_back(Edges {v,0,f,w});
        E.push_back(Edges {u,0,-f,0});
        m=E.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
        return;
    }
    void CALC(int S,int T) {
        while (M(S,T));
        return;
    }
    int M(int S,int T) {
        int i,a[maxn],p[maxn],inq[maxn],d[maxn];
        queue <int> Q;
        memset(a,0,sizeof(a));
        memset(p,0,sizeof(p));
        memset(inq,0,sizeof(inq));
        memset(d,0x7f,sizeof(d));
        inq[S]=1;
        a[S]=INF;
        d[S]=0;
        Q.push(S);
        while (!Q.empty()) {
            int i,x=Q.front();Q.pop();
            inq[x]=0;
            for (i=0;i<(int)G[x].size();++i) {
                Edges &e=E[G[x][i]];
                if (e.cap>e.flow&&d[e.to]>d[x]+e.cost) {
                    d[e.to]=d[x]+e.cost;
                    a[e.to]=min(a[x],e.cap-e.flow);
                    p[e.to]=G[x][i];
                    if (!inq[e.to]) {
                        Q.push(e.to);
                        inq[e.to]=1;
                    }
                }
            }
        }
        if (d[T]==INF)  return false;
        flow+=a[T];
        cost+=a[T]*d[T];
        for (i=T;i!=S;i=E[p[i]^1].to) { //!!!!!!!
            E[p[i]].flow+=a[T];
            E[p[i]^1].flow-=a[T];
        }
        return true;
    }
};
int main() {
    int N,M,S,T;
    int u,v,w,f,i;
    MCMF A;
    scanf("%d%d%d%d",&N,&M,&S,&T);
    for (i=1;i<=M;++i) {
        scanf("%d%d%d%d",&u,&v,&w,&f);
        A.Adde(u,v,w,f);
    }
    A.CALC(S,T);
    printf("%d %d\n",A.flow,A.cost);
    return 0;
}

其他基本操作

手写快排

void qs(int *a,int x,int y) {
    int i=x,j=y,mid=a[x+(y-x)/2];
    while (i<=j) {
        while (a[i]<mid)    i++;
        while (a[j]>mid)    j--;
        if (i<=j)
            swap(a[i++],a[j--]);
    }
    if (i<y)    qs(a,i,y);
    if (x<j)    qs(a,x,j);
    return;
}

CDQ分治

//3D seq
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 1, maxk = 2e5 + 1;
int n, k;
int v[maxn], x[maxn], y[maxn], z[maxn], num[maxn], t[maxn], tot, p[maxn], ans[maxn];
int val[maxk];
int cmp(int i, int j) {
    return x[i] < x[j] || (x[i] == x[j] && ((y[i] < y[j]) || (y[i] == y[j] && z[i] < z[j])));
}
void read() {
    int i, j;
    cin>>n>>k;
    for (i = 0; i < n; ++i) {
        cin>>x[i]>>y[i]>>z[i];
        p[i] = i;
    }
    sort(p, p + n, cmp);
    for (i = 0; i < n; i = j) {
        int t = p[i];
        p[tot++] = t;
        j = i + 1;
        while (j < n && !((x[p[i]] ^ x[p[j]]) || (y[p[i]] ^ y[p[j]]) || (z[p[i]] ^ z[p[j]]))) {
            v[t]++;
            j++;
        }
        v[t]++;
    }
}

int lowbit(int x) {
    return x & (-x);
}
void add(int pos, int vl) {
    while (pos <= k) {
        val[pos] += vl;
        pos += lowbit(pos);
    }
}
int sum(int pos) {
    int ret = 0;
    while (pos) {
        ret += val[pos];
        pos -= lowbit(pos);
    }
    return ret;
}

void CDQ(int L, int R) {
    int mid = L + (R - L) / 2, i = L, j = mid + 1, cnt = L;
    if (L == R) return;
    CDQ(L, mid);CDQ(mid + 1, R);
    while (i <= mid || j <= R) {
        if (j > R || (i <= mid && y[p[i]] <= y[p[j]])) {
            add(z[p[i]], v[p[i]]);
            t[cnt++] = p[i++];
        }
        else {
            ans[p[j]] += sum(z[p[j]]);
            t[cnt++] = p[j++];
        }
    }

    for (i = L; i <= mid; ++i)
        add(z[p[i]], -v[p[i]]);
    for (i = L; i <= R; ++i)
        p[i] = t[i];
    return;
}
void solve() {
    CDQ(0, tot - 1);

}
void print() {
    int i;
    int num[maxn] = { 0 };
    for (i = 0; i < tot; ++i)
        num[ans[p[i]] + v[p[i]] - 1] += v[p[i]];
    for (i = 0; i < n; ++i)
        cout<<num[i]<<endl;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    read();
    solve();
    print();

    return 0;
}

整体二分

void solve(int L, int R, int beg, int end) {
    int mid = L + (R - L) / 2, i, bl = 0, br = 0, pl = 0, pr = 0, M;
    long long num;
    tag++;
    //printf("L = %d, R = %d, mid = %d\n", L, R, mid);
    if (L > R)  return;
    if (L == R) {
        for (i = beg; i < end; ++i)
            if (st[i].opt == 2) //iffffff
                ans[st[i].id] = L;
        return;
    }
    for (i = beg; i < end; ++i) {
        OPT &e = st[i];
        if (e.opt == 1) {
            if (e.k > mid) {
                add(e.a, e.b, 1);
                tr[pr++] = e;
            } else  tl[pl++] = e;
        } else {
            num = sum(e.a, e.b);
            //cout<<num<<endl;
            if (num >= e.k) {
                tr[pr++] = e;
                br = 1;
            } else {
                bl = 1;
                e.k -= num;
                tl[pl++] = e;
            }
        }
    }
    end = beg;
    for (i = 0; i < pl; ++i)    st[end++] = tl[i];
    M = end;
    for (i = 0; i < pr; ++i)    st[end++] = tr[i];
    if (bl) solve(L, mid, beg, M);
    if (br) solve(mid + 1, R, M, end);
    return;
}
signed main() {
    int m, Q = 0;
    long long mn = 0x7f7f7f7f, mx = -0x7f7f7f7f;
    cin>>N>>m;
    for (int i = 0; i < m; ++i) {
        cin>>st[i].opt>>st[i].a>>st[i].b>>st[i].k;
        if (st[i].opt == 2)
            st[i].id = Q++;
        else {
            mn = min(mn, st[i].k);
            mx = max(mx, st[i].k);
        }
    }
    solve(mn, mx, 0, m);
    for (int i = 0; i < Q; ++i)
        cout<<ans[i]<<endl;
    return 0;
}

模拟退火

#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <ctime>
using namespace std;
double x;
time_t t0=clock();
double f(double x) {
    //return pow(x,5)*exp(x)+pow(x,2)*(-100)+pow(x,7)*(-81)-18;
    //return pow((x+1/x),x);
    return log(fabs(x))+log(2);
}
double delta(double d) {
    return fabs(f(d))-fabs(f(x));
}
void simulate_anneal();
int main() {
    srand(time(NULL));
    x=0;
    simulate_anneal();
    cout<<x<<endl;
    return 0;
}
void simulate_anneal() {
    double t=2000,k=0.99,i;
    while (t>1e-14) {
        double d=x+((rand()<<1)-RAND_MAX)*t;
        i=delta(d);
        if (i<0)
            x=d;
        else
            if (exp(-i/t)*RAND_MAX>rand())
                x=d;
        t*=k;
        if ((clock()-t0/(float)CLOCKS_PER_SEC)>0.15) {
            t0=clock();
            printf("d=%lf\tnowx=%lf\tf(x)=%lf\n",d,x,f(x));
        }
    }
    return;
}