省选考前模板

线性筛的通用情况

//low[x]:x的最小质因子的次幂 
vis[1] = low[1] = 1; H[1] = 初始化; 
for(int i = 2; i <= N; i++) 
{
    if(!vis[i]) prime[++tot] = i, mu[i] = -1, H[i] = 质数的情况, low[i] = i;
    for(int j = 1; j <= tot && i * prime[j] <= N; j++) 
    {
        vis[i * prime[j]] = 1;
        if(!(i % prime[j])) 
        {
            low[i * prime[j]] = (low[i] * prime[j]); 
            if(low[i] == i) H[i * prime[j]] = 特殊判断;
            else H[i * prime[j]] = H[i / low[i]] * H[prime[j] * low[i]];
            break;
        } 
        H[i * prime[j]] = H[i] * H[prime[j]];
        low[i * prime[j]] = prime[j];
    }
}

KMP字符串匹配

int k = 0; nt[1] = 0;
for (int i = 2; i <= lenb; ++i) 
{
    while (k && b[k + 1] != b[i])k = nt[k];
    if (b[k + 1] == b[i])++k;
    nt[i] = k;
}
k = 0;
for (int i = 1; i <= lena; ++i) 
{
    while (k && b[k + 1] != a[i])k = nt[k];
    if (b[k + 1] == a[i])++k;
    if (k == lenb)pos[++ans] = i - lenb + 1;
}

manacher/马拉车回文

scanf("%s", s + 1); n = strlen(s + 1);                                              
for (int i = 1, j = 0; i <= n; ++i)t[++j] = '*', t[++j] = s[i]; t[n + n + 1] = '*'; 
t[0] = '$'; n = n + n + 1;                                                          
for (int i = 1; i <= n; ++i)                                                        
{                                                                                   
    p[i] = r > i ? min(r - i, p[2 * pos - i]) : 0;                                  
    while (t[i - p[i] - 1] == t[i + p[i] + 1])++p[i];                               
    if (i + p[i] > r)r = i + p[i], pos = i;                                         
}

PAM

int cnt = 1, last, em;
int get_fail(int x) 
{
    while (s[em - len[x] - 1] != s[em])x = fail[x];
    return x;
}
int get_nt(int x) 
{
    while (s[em - len[x] - 1] != s[em] || ((len[x] + 2) << 1) > len[cnt])x = fail[x];
    return x;
}
void Insert(int x) 
{
    int f1 = get_fail(last);
    if (!tr[f1][x]) 
    {
        len[++cnt] = len[f1] + 2;
        fail[cnt] = tr[get_fail(fail[f1])][x];
        if (len[cnt] <= 2)nt[cnt] = fail[cnt];
        else nt[cnt] = tr[get_nt(nt[f1])][x];
        tr[f1][x] = cnt;
    }
    last = tr[f1][x];
}
fail[0] = 1; fail[1] = 0; len[0] = 0; len[1] = -1;
for (int i = 1; i <= n; ++i)em = i, Insert(s[i] - 'a');

AC 自动机

void build(string s) 
{
    int l = s.length(), now = 0;
    for (int i = 0; i < l; ++i) 
    {
        if (!AC[now].vis[s[i] - 'a'])AC[now].vis[s[i] - 'a'] = ++cnt;
        now = AC[now].vis[s[i] - 'a'];
    }
    ++AC[now].end;
}
queue<int>q;
void Gfail() 
{
    int u;
    for (int i = 0; i < 26; ++i)
        if (AC[0].vis[i]) AC[AC[0].vis[i]].fail = 0, q.push(AC[0].vis[i]);
    while (!q.empty()) 
    {
        u = q.front(); q.pop();
        for (int i = 0; i < 26; ++i)
            if (AC[u].vis[i]) 
            {
                AC[AC[u].vis[i]].fail = AC[AC[u].fail].vis[i];
                q.push(AC[u].vis[i]);
            } else AC[u].vis[i] = AC[AC[u].fail].vis[i];
    }
}

匈牙利二分图最大匹配

bool dfs(int x) 
{
    for (int i = head[x]; i; i = e[i].nt) 
    {
        if (vis[e[i].to])continue;
        vis[e[i].to] = 1;
        if (!mch[e[i].to] || dfs(mch[e[i].to])) 
        {
            mch[e[i].to] = x;
            return 1;
        }
    }
    return 0;
}
for (int i = 1; i <= n; ++i) 
{
    memset(vis, 0, sizeof(vis));
    if (dfs(i))++ans;
}

网络最大流

tot = 1;
int bfs() 
{
    int x;
    memset(dis, 0, sizeof(dis));
    while (!q.empty())q.pop();
    for (int i = 1; i <= n; ++i)cur[i] = head[i];
    dis[s] = 1; q.push(s);
    while (!q.empty()) 
    {
        x = q.front(); q.pop();
        for (int i = head[x]; i; i = nt[i])
            if (val[i] && !dis[to[i]]) 
            {
                dis[to[i]] = dis[x] + 1;
                if (to[i] == t)return 1;
                q.push(to[i]);
            }
    }
    return 0;
}
int dinic(int x, int flow) 
{
    if (x == t || !flow)return flow;
    int k, res = flow;
    for (int &i = cur[x]; i; i = nt[i])
        if (val[i] && dis[to[i]] == dis[x] + 1) 
        {
            k = dinic(to[i], min(val[i], res));
            if (!k)dis[to[i]] = 0;
            val[i] -= k; val[i ^ 1] += k;
            if (!(res -= k))break;
        }
    return flow - res;
}
while (bfs())ans += dinic(s, inf);

最小费用最大流

tot = 1;
int SPFA() 
{
    int x;
    memset(dis, 0x3f, sizeof(dis));
    memset(pre, -1, sizeof(pre));
    dis[s] = 0; q.push(s); vis[s] = 1;
    while (!q.empty()) 
    {
        x = q.front(); q.pop(); vis[x] = 0;
        for (int i = head[x]; i; i = nt[i])
            if (val[i] && dis[to[i]] > dis[x] + cost[i]) 
            {
                dis[to[i]] = dis[x] + cost[i]; pre[to[i]] = i; from[to[i]] = x;
                if (!vis[to[i]])q.push(to[i]), vis[to[i]] = 1;
            }
    }
    return pre[t] != -1;
}
void MFMC() 
{
    int k;
    while (SPFA()) 
    {
        k = inf;
        for (int i = t; i != s; i = from[i])k = min(k, val[pre[i]]);
        ans1 += k; ans2 += dis[t] * k;
        for (int i = t; i != s; i = from[i])val[pre[i]] -= k, val[pre[i] ^ 1] += k;
    }
}

无源汇有上下界可行流

int main()
{
	cin >> n >> m;
	S = 0; T = n + 1;
	for (int i = 1; i <= m; ++i)
	{
		x = read(); y = read(); L[i] = read(); r = read();
		ADD(x, y, r - L[i]);
		A[x] -= L[i]; A[y] += L[i];
		c[i] = tot;
	}
	for (int i = 1; i <= n; ++i)
		if (A[i] > 0)ADD(S, i, A[i]), sum += A[i];
		else if (A[i])ADD(i, T, -A[i]);
	while (bfs(S, T))
		while (flow = dinic(S, inf))ans += flow;
	if (ans != sum)return puts("NO") == 23333;
	puts("YES");
	for (int i = 1; i <= m; ++i)Write(L[i] + e[c[i]].cap, 1), putchar('
');
	return 0;
}

有源汇有上下界最大流

int main()
{
	cin >> n >> m >> S >> T;
	SS = 0; TT = n + 1;
	for (int i = 1; i <= m; ++i)
	{
		x = read(); y = read(); l = read(); r = read();
		ADD(x, y, r - l);
		A[x] -= l; A[y] += l;
	}
	for (int i = 1; i <= n; ++i)
		if (A[i] > 0) {ADD(SS, i, A[i]); sum += A[i];}
		else if (A[i])ADD(i, TT, -A[i]);
	ADD(T, S, inf);
	while (bfs(SS, TT))while (flow = dinic(SS, inf, TT))ans += flow;
	if (ans != sum)return puts("please go home to sleep") == 23333;
	ans = 0;
	while (bfs(S, T))while (flow = dinic(S, inf, T))ans += flow;
	cout << ans;
	return 0;
}

有源汇有上下界最小流

int main()
{
	cin >> n >> m >> S >> T;
	SS = 0; TT = n + 1;
	for (int i = 1; i <= m; ++i)
	{
		x = read(); y = read(); l = read(); r = read();
		ADD(x, y, r - l);
		A[x] -= l; A[y] += l;
	}
	for (int i = 1; i <= n; ++i)
		if (A[i] > 0) {ADD(SS, i, A[i]); sum += A[i];}
		else if (A[i])ADD(i, TT, -A[i]);
	while (bfs(SS, TT))while (flow = dinic(SS, inf, TT))ans += flow;
	ADD(T, S, inf);
	while (bfs(SS, TT))while (flow = dinic(SS, inf, TT))ans += flow;
	if (ans != sum)return puts("please go home to sleep") == 23333;
	cout << e[tot].cap;
	return 0;
}

左偏树(可并堆)

struct dui {int val, fa, dis, ch[2];} tr[N << 1];
int find(int x) {return x == tr[x].fa ? tr[x].fa : tr[x].fa = find(tr[x].fa);}
int Merge(int x, int y) 
{
    if (!x || !y)return x + y;
    if (tr[x].val > tr[y].val || (tr[x].val == tr[y].val && x > y))swap(x, y);
    tr[x].ch[1] = Merge(tr[x].ch[1], y); tr[tr[x].ch[1]].fa = x;
    if (tr[tr[x].ch[0]].dis < tr[tr[x].ch[1]].dis)swap(tr[x].ch[0], tr[x].ch[1]);
    tr[x].dis = tr[tr[x].ch[1]].dis + 1;
    return x;
}
void Delete(int x) 
{
    tr[x].val = -1;
    tr[tr[x].ch[0]].fa = tr[x].ch[0]; tr[tr[x].ch[1]].fa = tr[x].ch[1];
    tr[x].fa = Merge(tr[x].ch[0], tr[x].ch[1]);
}

圆方树

void Tarjan(int x)
{
    dfn[x] = low[x] = ++cnt; zhan[++Top] = x;
    for (int i = Head[x]; i; i = Nt[i])
        if (!dfn[To[i]])
        {
            Tarjan(To[i]); low[x] = min(low[x], low[To[i]]);
            if (low[To[i]] >= dfn[x])
            {
                add(++num, x); add(x, num);
                int t;
                do
                {
                    t = zhan[Top--]; add(num, t); add(t, num);
                } while (t != To[i]);
            }
        }
        else low[x] = min(low[x], dfn[To[i]]);
}

虚树

int my(int a, int b) {return dfn[a] < dfn[b];}
void build() 
{
    int x, lca;
    sort(a + 1, a + 1 + k, my);
    if (a[1] != 1)zhan[top = 1] = 1;
    for (int i = 1; i <= k; ++i) 
    {
        x = a[i];
        if (top <= 1) {zhan[++top] = x; continue;}
        lca = LCA(zhan[top], x);
        if (lca == zhan[top]) {zhan[++top] = x; continue;}
        while (top > 1 && dep[lca] <= dep[zhan[top - 1]]) {add(zhan[top - 1], zhan[top], 0); --top;}
        if (lca != zhan[top])add(lca, zhan[top], 0), zhan[top] = lca;
        zhan[++top] = x;
    }
    while (top) {add(zhan[top - 1], zhan[top], 0); top--;}
}

dsu on tree

void ADD(int x, int fa, int val) 
{
    cnt[col[x]] += val;
    if (cnt[col[x]] > mx)mx = cnt[col[x]], nowans = col[x];
    else if (cnt[col[x]] == mx)nowans += col[x];
    for (int i = head[x]; i; i = nt[i])
        if (to[i] != fa && to[i] != Son)ADD(to[i], x, val);
}
void dfs2(int x, int fa, int opt) 
{
    for (int i = head[x]; i; i = nt[i])
        if (to[i] != fa && to[i] != son[x])dfs2(to[i], x, 0);
    if (son[x])dfs2(son[x], x, 1), Son = son[x];
    ADD(x, fa, 1); Son = 0; ans[x] = nowans;
    if (!opt)ADD(x, fa, -1), nowans = 0, mx = 0;
}

Tarjan求割边

void Tarjan(int x, int f) 
{
    dfn[x] = low[x] = ++dfn_id;
    for (int i = head[x]; i; i = nt[i])
        if (i != f) 
        {
            if (!dfn[to[i]]) 
            {
                Tarjan(to[i], i ^ 1), low[x] = min(low[x], low[to[i]]);
                if (low[to[i]] > dfn[x])vis[i] = vis[i ^ 1] = 1;
            } else low[x] = min(low[x], dfn[to[i]]);
        }
}

Tarjan求割点

void Tarjan(int x, int rt) 
{
    int er = 0;
    dfn[x] = low[x] = ++cnt;
    for (int i = head[x]; i; i = e[i].nt) 
    {
        int v = e[i].to;
        if (!dfn[e[i].to]) 
        {
            Tarjan(v, rt);
            low[x] = min(low[x], low[v]);
            if (low[v] >= dfn[x] && x != rt)cut[x] = 1;
            if (x == rt)er++;
        }
        else low[x] = min(low[x], dfn[v]);
    }
    if (x == rt && er > 1)cut[x] = 1;
}

NTT

void NTT(LL *A, int lim, int opt) 
{
    for (int i = 0; i < lim; ++i)r[i] = (r[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
    for (int i = 0; i < lim; ++i)if (i < r[i])swap(A[i], A[r[i]]);
    LL w, wn, x, y;
    for (int mid = 1, len = 2; len <= lim; mid <<= 1, len <<= 1) 
    {
        wn = ksm(opt == 1 ? G : Ginv, (mod - 1) / len, mod);
        for (int j = 0; j < lim; j += len) 
        {
            w = 1;
            for (int k = j; k < j + mid; ++k, w = w * wn % mod) 
            {
                x = A[k]; y = A[k + mid] * w % mod;
                A[k] = (x + y) % mod; A[k + mid] = (x - y + mod) % mod;
            }
        }
    }
    if (opt == 1)return;
    int ni = ksm(lim, mod - 2, mod);
    for (int i = 0; i < lim; ++i)A[i] = A[i] * ni % mod;
}

FFT

void FFT(xu *A, int lim, int opt) 
{
    for (int i = 0; i < lim; ++i)r[i] = (r[i >> 1] >> 1) | (i & 1 ? (lim >> 1) : 0);
    for (int i = 0; i < lim; ++i)if (i < r[i])swap(A[i], A[r[i]]);
    for (int mid = 1; mid < lim; mid <<= 1) 
    {
        xu wn(cos(PI / mid), opt * sin(PI / mid));
        for (int len = mid << 1, j = 0; j < lim; j += len) 
        {
            xu w((DB)1, (DB)0);
            for (int k = j; k < mid + j; ++k, w = w * wn) 
            {
                xu a = A[k], b = w * A[k + mid];
                A[k] = a + b;
                A[k + mid] = a - b;
            }
        }
    }
    if (opt == 1)return;
    for (int i = 0; i < lim; ++i)A[i] = xu(A[i].x / lim , 0);
}

分治NTT

void solve(int l, int r) 
{
    if (l == r)return;
    int mid = (l + r) >> 1, len = r - l + 1;
    solve(l, mid);
    for (int i = 0; i < len; ++i)a[i] = b[i] = 0;
    for (int i = l; i <= mid; ++i)a[i - l] = f[i]; for (int i = 1; l + i <= r; ++i)b[i] = g[i];
    NTT(a, len, 1); NTT(b, len, 1);
    for (int i = 0; i < len; ++i)a[i] = (LL)a[i] * b[i] % mod;
    NTT(a, len, -1);
    for (int i = mid + 1; i <= r; ++i)(f[i] += a[i - l]) %= mod;
    solve(mid + 1, r);
}

多项式 INV LN EXP

求逆：(B equiv 2B_0 -AB_0^2)

求ln：(displaystyle int frac{A'}{A})

求exp:(B equiv B_0(1-lnB_0+A))

void INV(int siz, LL *A, LL *B) 
{
    if (siz == 1) 
    {
        B[0] = ksm(A[0], mod - 2, mod);
        return;
    }
    INV((siz + 1) >> 1, A, B);
    int lim = 1;
    while (lim < (siz << 1))lim <<= 1;
    for (int i = 0; i < siz; ++i)c[i] = A[i];
    for (int i = siz; i < lim; ++i)c[i] = 0;
    NTT(c, lim, 1); NTT(B, lim, 1);
    for (int i = 0; i < lim; ++i)B[i] = B[i] * (2 - c[i] * B[i] % mod + mod) % mod;
    NTT(B, lim, -1);
    for (int i = siz; i < lim; ++i)B[i] = 0;
}
void MUL(LL *A, int n, LL *B, int m) 
{
    int lim = 1;
    while (lim <= (n + m))lim <<= 1;
    NTT(A, lim, 1); NTT(B, lim, 1);
    for (int i = 0; i < lim; ++i)A[i] = A[i] * B[i] % mod;
    NTT(A, lim, -1);
}
LL LN_inv[N];
void LN(int n, LL *A, LL *B) 
{
    int lim = 1;
    while (lim <= (n << 1))lim <<= 1;
    for (int i = 1; i < n; ++i)B[i - 1] = A[i] * i % mod;
    for (int i = n - 1; i < lim; ++i)B[i] = 0;
    for (int i = 0; i < lim; ++i)LN_inv[i] = 0;
    INV(n, A, LN_inv);
    MUL(B, n, LN_inv, n);
    for (int i = lim - 1; i >= 1; --i)B[i] = B[i - 1] * ksm(i, mod - 2, mod);
    B[0] = 0;
}
LL ln[N];
void EXP(int siz, LL *A, LL *B) 
{
    if (siz == 1) 
    {
        B[0] = 1;
        return;
    }
    EXP((siz + 1) >> 1, A, B);
    LN(siz, B, ln);
    int lim = 1;
    while (lim < (siz << 1))lim <<= 1;
    for (int i = 0; i < siz; ++i)ln[i] = A[i] - ln[i];
    ln[0]++;
    for (int i = siz; i < lim; ++i)ln[i] = B[i] = 0;
    MUL(B, siz, ln, siz);
}

FWT

void GET()
{
    for(int i=0;i<n;++i)a[i]=(LL)a[i]*b[i]%mod;
}
void OR(LL *A, int opt) 
{
    for (int mid = 1, len = 2; len <= n; mid <<= 1, len <<= 1)
        for (int i = 0; i < n; i += len)
            for (int j = i; j < i + mid; ++j)
                (A[j + mid] += A[j] * opt) %= mod;
}
void AND(LL *A, int opt) 
{
    for (int mid = 1, len = 2; len <= n; mid <<= 1, len <<= 1)
        for (int i = 0; i < n; i += len)
            for (int j = i; j < i + mid; ++j)
                (A[j] += A[j + mid] * opt) %= mod;
}
void XOR(LL *A, int opt) 
{
    int a, b;
    for (int mid = 1, len = 2; len <= n; mid <<= 1, len <<= 1)
        for (int i = 0; i < n; i += len)
            for (int j = i; j < i + mid; ++j)
                a = A[j], b = A[j + mid], A[j] = (LL)(a + b) * opt % mod, A[j + mid] = (LL)(a - b) * opt % mod;
}
OR(a, 1); OR(b, 1); GET(); OR(a, mod - 1);
AND(a, 1); AND(b, 1); GET(); AND(a, mod - 1);
XOR(a, 1); XOR(b, 1); GET(); XOR(a, (mod + 1) / 2);

子集卷积

inline int yi(int x) {int res = 0; while (x)res += x & 1, x >>= 1; return res;}
void OR(int *A, int lim, int opt) 
{
    for (int mid = 1, len = 2; len <= lim; mid <<= 1, len <<= 1)
        for (int j = 0; j < lim; j += len)
            for (int k = j; k < j + mid; ++k)
                (A[k + mid] += A[k] * opt) %= mod;
}
int main() 
{
    cin >> m; n = 1 << m;
    for (int i = 0; i < n; ++i)scanf("%d", &a[yi(i)][i]);
    for (int i = 0; i < n; ++i)scanf("%d", &b[yi(i)][i]);
    for (int i = 0; i <= m; ++i)OR(a[i], n, 1), OR(b[i], n, 1);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= j; ++k)c[j][i] = ((LL)c[j][i] + (LL)a[k][i] * b[j - k][i]) % mod;
    for (int i = 0; i <= m; ++i)OR(c[i], n, -1);
    for (int i = 0; i < n; ++i)printf("%d ", (c[yi(i)][i] + mod) % mod);
    return 0;
}

自适应辛普森

辛普森公式:(displaystyle int_{a}^{b}f(x)dx approx frac{(b-a)(f(a)+f(b)+4f(frac{a+b}{2}))}{6})

inline DB simpson(DB l , DB r) {return (f(l) + 4 * f((l + r) / 2) + f(r)) * (r - l) / 6;}
inline DB jue(DB x) {return x > 0 ? x : -x;}
DB asr(DB l, DB r, DB eps, DB ans) 
{
    DB mid = (l + r) / 2, L = simpson(l, mid), R = simpson(mid, r);
    if (jue(L + R - ans) <= eps * 15)return L + R + (L + R - ans) / 15;
    return asr(l, mid, eps / 2, L) + asr(mid, r, eps / 2, R);
}

Matrix-Tree 定理(矩阵树定理)

详见博客

for (int i = 2, inv, tmp; i <= n; ++i)
{
    for (int j = i + 1; j <= n; ++j)
        if (!a[i][i] && a[j][i]) {ans = -ans; swap(a[i], a[j]); break;}
    inv = ksm(a[i][i], mod - 2, mod);
    for (int j = i + 1; j <= n; ++j)
    {
        tmp = (LL)a[j][i] * inv % mod;
        for (int k = i; k <= n; ++k)a[j][k] = (a[j][k] - (LL)a[i][k] * tmp % mod) % mod;
    }
}

二维凸包

inline int my1(dian a, dian b) {return a.x == b.x ? a.y < b.y : a.x < b.x;}
inline int my2(dian a, dian b) 
{
    int tmp = dump(cross(a - e[1], b - e[1]));
    if (tmp > 0)return 1;
    else if (tmp == 0 && dump(dis(a, e[1]) - dis(b, e[1])) < 0)return 1;
    return 0;
}
inline void TU_BAO() 
{
    sort(e + 1, e + 1 + n, my1);
    sort(e + 2, e + 1 + n, my2);
    zhan[top = 1] = e[1];
    for (int i = 2; i <= n; ++i) 
    {
        while (top > 1 && dump(cross(e[i] - zhan[top - 1], zhan[top] - zhan[top - 1])) >= 0)--top;
        zhan[++top] = e[i];
    }
}

半平面交

friend bool operator <(const xian &a, const xian &b) {return a.ang < b.ang;}
DB cross(dian a, dian b) {return a.x * b.y - a.y * b.x;}
int onleft(xian s, dian a) {return cross(s.v, a - s.p) > 0;}
dian linemeet(xian a, xian b) {return a.p + a.v * (cross(b.v, a.p - b.p) / cross(a.v, b.v));}
int hpi(xian *L, int n) 
{
    sort(L + 1, L + 1 + n);
    int head, tail;
    sta[head = tail = 1] = L[1];
    for (int i = 2; i <= n; ++i) 
    {
        while (head < tail && !onleft(L[i], p[tail - 1]))tail--;
        while (head < tail && !onleft(L[i], p[head]))head++;
        sta[++tail] = L[i];
        if (!dump(cross(sta[tail].v, sta[tail - 1].v))) 
        {
            tail--;
            if (onleft(sta[tail], L[i].p))sta[tail] = L[i];
        }
        if (head < tail)p[tail - 1] = linemeet(sta[tail], sta[tail - 1]);
    }
    while (head < tail && !onleft(sta[head], p[tail - 1]))tail--;
    if (tail <= head + 1)return 0;
    p[tail] = linemeet(sta[tail], sta[head]);
    for (int i = head; i <= tail; ++i)Ans[i - head + 1] = p[i];
    return tail - head + 1;
}

平衡树splay

int isr(int x) {return x == tr[tr[x].fa].ch[1];}
int js(int x) {return tr[tr[x].ch[0]].siz + 1;}
void updata(int x) {tr[x].siz = tr[tr[x].ch[0]].siz + tr[tr[x].ch[1]].siz + 1;}
void New(int x, int val) 
{
    tr[x].ch[0] = tr[x].ch[1] = tr[x].fa = 0;
    tr[x].val = val; tr[x].siz = 1;
}
void rotate(int x) 
{
    int y = tr[x].fa, z = tr[y].fa, k = isr(x);
    if (y != root)tr[z].ch[isr(y)] = x;
    else root = x;
    tr[y].ch[k] = tr[x].ch[!k]; tr[tr[y].ch[k]].fa = y;
    tr[x].ch[!k] = y; tr[y].fa = x; tr[x].fa = z;
    updata(y); updata(x);
}
void Splay(int x) 
{
    while (x != root) 
    {
        if (tr[x].fa != root)rotate(isr(x) == isr(tr[x].fa) ? tr[x].fa : x);
        rotate(x);
    }
}
void Insert(int val) 
{
    if (!root) 
    {
        root = (top ? zhan[top--] : ++cnt);
        New(root, val);
        return;
    }
    int now = root, fa = 0;
    while (now) {fa = now; now = tr[now].ch[val > tr[now].val];}
    now = (top ? zhan[top--] : ++cnt); New(now, val);
    tr[fa].ch[tr[now].val > tr[fa].val] = now; tr[now].fa = fa;
    Splay(now);
}
void Merge(int &x, int y, int fa) 
{
    if (x)tr[x].fa = fa;
    if (y)tr[y].fa = fa;
    if (!x || !y) {x = x + y; return;}
    Merge(tr[x].ch[1], y, x);
    updata(x);
}
void Delete(int val) 
{
    int now = root;
    while (now && tr[now].val != val)now = tr[now].ch[val > tr[now].val];
    if (!now)return;
    zhan[++top] = now; Splay(now);
    Merge(tr[now].ch[0], tr[now].ch[1], 0);
    root = tr[now].ch[0];
}
int Rank(int val) 
{
    int now = root, fa = 0, res = 0;
    while (now) 
    {
        fa = now;
        if (val <= tr[now].val)now = tr[now].ch[0];
        else {res += js(now); now = tr[now].ch[1];}
    }
    Splay(fa);
    return res + 1;
}
int Kth(int k) 
{
    int now = root;
    while (now && js(now) != k) 
    {
        if (k < js(now))now = tr[now].ch[0];
        else {k -= js(now); now = tr[now].ch[1];}
    }
    Splay(now);
    return tr[now].val;
}
int Pre(int val) 
{
    int now = root, last = 0;
    while (now) 
    {
        if (val > tr[now].val) {last = now; now = tr[now].ch[1];}
        else now = tr[now].ch[0];
    }
    if (last) {Splay(last); return tr[last].val;}
    return -1;
}
int Next(int val) 
{
    int now = root, last = 0;
    while (now) 
    {
        if (val < tr[now].val) {last = now; now = tr[now].ch[0];}
        else now = tr[now].ch[1];
    }
    if (last) {Splay(last); return tr[last].val;}
    return -1;
}

splay维护序列

void pushup(int x) 
{
    siz[x] = siz[lson] + siz[rson] + 1;
    mx[x] = val[x];
    if (lson)mx[x] = max(mx[x], mx[lson]);
    if (rson)mx[x] = max(mx[x], mx[rson]);
}
void pushdown(int x) 
{
    if (rev[x]) 
    {
        swap(ch[lson][0], ch[lson][1]); swap(ch[rson][0], ch[rson][1]);
        rev[lson] ^= 1; rev[rson] ^= 1; rev[x] = 0;
    }
    if (tag[x]) 
    {
        val[lson] += tag[x]; mx[lson] += tag[x]; val[rson] += tag[x]; mx[rson] += tag[x];
        tag[lson] += tag[x]; tag[rson] += tag[x]; tag[x] = 0;
    }
}
int isr(int x) {return ch[fa[x]][1] == x;}
void rotate(int x, int &to) 
{
    int y = fa[x], z = fa[y], k = isr(x);
    if (y == to)to = x;
    else ch[z][isr(y)] = x;
    ch[y][k] = ch[x][!k]; fa[ch[y][k]] = y;
    ch[x][!k] = y; fa[y] = x; fa[x] = z;
    pushup(y); pushup(x);
}
void splay(int x, int &to) 
{
    while (x != to) 
    {
        if (fa[x] != to)rotate(isr(x) == isr(fa[x]) ? fa[x] : x, to);
        rotate(x, to);
    }
}
int build(int l, int r) 
{
    if (l > r)return 0;
    int mid = (l + r) >> 1, x = ++cnt; siz[x] = 1;
    lson = build(l, mid - 1); fa[lson] = x;
    rson = build(mid + 1, r); fa[rson] = x;
    pushup(x);
    return x;
}
int find(int x, int k) 
{
    while (1) 
    {
        pushdown(x);
        if (k <= siz[lson])x = lson;
        else 
        {
            k -= siz[lson] + 1;
            if (!k)return x;
            x = rson;
        }
    }
}
int split(int x, int y) 
{
    x = find(root, x); y = find(root, y);
    splay(x, root); splay(y, ch[root][1]);
    return ch[y][0];
}

LCT

inline int isr(int x) {return ch[fa[x]][1] == x;}
inline int isroot(int x) {return ch[fa[x]][0] != x && ch[fa[x]][1] != x;}
void pushup(int x) {sum[x] = val[x] ^ sum[lson] ^ sum[rson];}
void pushdown(int x) 
{
    if (rev[x]) 
    {
        swap(ch[lson][0], ch[lson][1]); swap(ch[rson][0], ch[rson][1]);
        rev[lson] ^= 1; rev[rson] ^= 1; rev[x] = 0;
    }
}
void upd(int x) 
{
    if (!isroot(x))upd(fa[x]); pushdown(x);
}
void rot(int x) 
{
    int y = fa[x], z = fa[y], k = isr(x);
    if (!isroot(y))ch[z][isr(y)] = x;
    ch[y][k] = ch[x][!k]; fa[ch[y][k]] = y;
    ch[x][!k] = y; fa[y] = x; fa[x] = z;
    pushup(y); pushup(x);
}
void Splay(int x) 
{
    upd(x);
    while (!isroot(x)) 
    {
        if (!isroot(fa[x]))rot(isr(x) == isr(fa[x]) ? fa[x] : x);
        rot(x);
    }
}
void access(int x) 
{
    int t = 0;
    while (x) {Splay(x); rson = t; pushup(x); t = x; x = fa[x];}
}
void make_root(int x) 
{
    access(x); Splay(x);
    swap(lson, rson); rev[x] ^= 1;
}
void link(int x, int y) {make_root(x); fa[x] = y;}
void cut(int x, int y) {make_root(y); access(x); Splay(x); lson = fa[y] = 0;}
int find(int x) 
{
    access(x); Splay(x);
    while (lson)pushdown(x), x = lson;
    return x;
}
void change(int x, int v) {Splay(x); sum[x] ^= val[x]; val[x] = v; sum[x] ^= val[x];}
int main() 
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)scanf("%d", &val[i]);
    while (m--) 
    {
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0) 
        {
            make_root(x); access(y); Splay(y);
            printf("%d
", sum[y]);
        } else if (opt == 1) {if (find(x) != find(y))link(x, y);}
        else if (opt == 2) {if (find(x) == find(y) && (fa[x] == y || fa[y] == x))cut(x, y);}
        else change(x, y);
    }
    return 0;
}

省选 考前模板

线性筛的通用情况

KMP字符串匹配

manacher/马拉车 回文

PAM

AC 自动机

匈牙利二分图最大匹配

网络最大流

最小费用最大流

无源汇有上下界可行流

有源汇有上下界最大流

有源汇有上下界最小流

左偏树(可并堆)

圆方树

虚树

dsu on tree

Tarjan求割边

Tarjan求割点

NTT

FFT

分治NTT

多项式 INV LN EXP

FWT

子集卷积

自适应辛普森

Matrix-Tree 定理(矩阵树定理)

二维凸包

半平面交

平衡树splay

splay维护序列

LCT

省选考前模板

manacher/马拉车回文