一些比较简洁的算法写法

欧拉线性筛

int pri[50000], phi[50000], len;
void calc_phi(int n)
{
    phi[1] = 1;
    for(int i=2;i<=n;i++)
    {
        if(!phi[i])
        {
            pri[len++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<len&&pri[j]*i<=n;j++)
        {
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=pri[j]*phi[i];
                break;
            }
            else phi[i*pri[j]]=(pri[j]-1)*phi[i];
        }
    }
}

优化过的并查集

int pre[200010];
int find(int x)
{
    if(pre[x] > 0)
    {
        pre[x] = find(pre[x]);
        return pre[x];
    }
    return x;
}
void merge(int x, int y)
{
    int rx = find(x);
    int ry = find(y);
    if(rx == ry)
        return;
    if(-pre[rx] > -pre[ry])
        swap(rx, ry);
    pre[ry] += pre[rx] - 1;
    pre[rx] = ry;

}

tarjan 求割点

const int MAXN = 21000, MAXM = 100010;

int g[MAXN], cnt = 0;

struct edge {
    int t, nxt;
} e[MAXM * 2];
void add_edge(int u, int v) {
    e[++cnt].t = v;
    e[cnt].nxt = g[u];
    g[u] = cnt;
}


int dfn[MAXN], low[MAXN], fa[MAXN];
int is_cut[MAXN];

int ans = 0;

void tarjan(int i) {
    static int count = 0;
    int children = 0;
    bool cut = false;
    dfn[i] = low[i] = ++count;
    for (int j_ = g[i], j; j = e[j_].t, j_; j_ = e[j_].nxt) {
        if (!dfn[j]) {
            children += 1;
            fa[j] = i;
            tarjan(j);
            low[i] = min(low[i], low[j]);
            if (fa[i] && low[j] >= dfn[i]) {
                cut = true;
            }
        } else if (j != fa[i]) {
            low[i] = min(low[i], dfn[j]);
        }
    }
    if (cut || (fa[i] == 0 && children >= 2)) {
        is_cut[i] = 1;
        ans += 1;
    }
}

树链剖分和线段树

#include <iostream>
#include <cstring>

using namespace std;
typedef long long treetype;
const int MAXN = static_cast<const int> ( 1e6 + 5 );
int n, a[MAXN];
int MOD;

treetype sgt_query(int lft, int rht, int rt, int l, int r);

void sgt_update(int lft, int rht, int mul, int add, int rt, int l, int r);

treetype sgt_get_val(int rt);

struct edge {
    int t, n;
} es[MAXN];


int g[MAXN * 2];
int len;

void addedge(int a, int b) {
    es[++len].t = b;
    es[len].n = g[a];
    g[a] = len;
}


int wt[MAXN], fat[MAXN], dep[MAXN], siz[MAXN], hvy[MAXN], id[MAXN], top[MAXN], cnt;


#define childs_in(root, j) for(int j##_ = g[root], j; j##_ && (j = es[j##_].t); j##_ = es[j##_].n)

void tcd_dfs1(int x, int f, int depth) {
    dep[x] = depth;
    fat[x] = f;
    siz[x] = 1;
    hvy[x] = 0;
    childs_in (x, s) {
        if (s == fat[x]) continue;
        tcd_dfs1(s, x, depth + 1);
        siz[x] += siz[s];
        if (!hvy[x] || siz[s] > siz[hvy[x]])
            hvy[x] = s;
    }
}


void tcd_dfs2(int x, int top_father) {
    id[x] = ++cnt;
    wt[cnt] = a[x];
    top[x] = top_father;
    if (hvy[x]) {
        tcd_dfs2(hvy[x], top_father);
        childs_in(x, s) {
            if (fat[x] == s || hvy[x] == s) continue;
            tcd_dfs2(s, s);
        }

    }
}


treetype tcd_query_sum(int x, int y) {
    treetype sum = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        (sum += sgt_query(id[top[x]], id[x], 1, 1, n)) %= MOD;
        x = fat[top[x]];
    }
    if (dep[x] > dep[y]) {
        swap(x, y);
    };
    return (sgt_query(id[x], id[y], 1, 1, n) + sum) % MOD;
}

void tcd_update(int x, int y, int mul, int add) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])
            swap(x, y);
        sgt_update(id[top[x]], id[x], mul, add, 1, 1, n);
        x = fat[top[x]];
    }
    if (dep[x] > dep[y])
        swap(x, y);

    sgt_update(id[x], id[y], mul, add, 1, 1, n);
}


treetype tcd_query_son(int x) {
    return sgt_query(id[x], id[x] + siz[x] - 1, 1, 1, n);
}

void tcd_update_son(int x, int mul, int add) {
    return sgt_update(id[x], id[x] + siz[x] - 1, mul, add, 1, 1, n);
}


// segment tree part
treetype sum[MAXN * 4], lz_add[MAXN * 4], lz_mul[MAXN * 4];
#define ls rt<1
#define rs rt<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define md int mid = (l + r) >> 1;

inline void sgt_init_lazy(int rt) {
    lz_mul[rt] = 1;
}

inline void sgt_set_val(int rt, int x) {
    sum[rt] = wt[x];
}

inline treetype sgt_get_val(int rt) {
    return sum[rt];
}

inline void sgt_pushup(int rt) {
    sum[rt] = (sum[ls] + sum[rs]) % MOD;
}
inline void init_val(treetype &v)
{
    v = 0;
}
inline void change_val(treetype &v, treetype x)
{
    (v += x) %= MOD;
}


inline void sgt_change_node(int rt, int l, int r, treetype add, treetype mul) {
    if (mul != 1) {
        sum[rt] = sum[rt] * mul % MOD;
        lz_mul[rt] = lz_mul[rt] * mul % MOD;
        lz_add[rt] = lz_add[rt] * mul % MOD;
    }
    if (add) {
        sum[rt] = (sum[rt] + add * (r - l + 1)) % MOD;
        lz_add[rt] = (lz_add[rt] + add) % MOD;
    }
}

inline void sgt_pushdown(int rt, int l, int r) {
    if (lz_add[rt] || lz_mul[rt] != 1) {
        md;
        sgt_change_node(lson, lz_add[rt], lz_mul[rt]);
        sgt_change_node(rson, lz_add[rt], lz_mul[rt]);
        lz_add[rt] = 0;
        lz_mul[rt] = 1;
    }
}

void sgt_build(int rt, int l, int r) {
    sgt_init_lazy(rt);
    if (l == r) {
        sgt_set_val(rt, l);
        return;
    }
    md;
    if (l <= mid)
        sgt_build(lson);
    if (r > mid)
        sgt_build(rson);
    sgt_pushup(rt);
}

treetype sgt_query(int lft, int rht, int rt, int l, int r) {
    if (lft <= l && r <= rht) {
        return sgt_get_val(rt);
    }
    sgt_pushdown(rt, l, r);
    treetype val;
    init_val(val);
    md;
    if (lft <= mid)
        change_val(val, sgt_query(lft, rht, lson));
    if (rht > mid)
        change_val(val, sgt_query(lft, rht, rson));
    return val;
}


// first mul second add
void sgt_update(int lft, int rht, int mul, int add, int rt, int l, int r) {
    if (lft <= l && r <= rht) {
        sgt_change_node(rt, l, r, add, mul);
        return;
    }
    sgt_pushdown(rt, l, r);
    md;
    if (lft <= mid) sgt_update(lft, rht, mul, add, lson);
    if (rht > mid) sgt_update(lft, rht, mul, add, rson);
    sgt_pushup(rt);
}

inline void tcd_init(int r, int n)
{
    tcd_dfs1(r, 0, 1);
    tcd_dfs2(r, r);
    sgt_build(1, 1, n);

}
int main() {
    int m, r;
    cin >> n >> m >> r >> MOD;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        addedge(a, b);
        addedge(b, a);
    }

    tcd_init(r, n);

    for (int i = 0; i < m; ++i) {
        int t, a, b, c;
        cin >> t;
        switch (t) {
            case 1:
                cin >> a >> b >> c;
                tcd_update(a, b, 1, c);
                break;
            case 2:
                cin >> a >> b;
                cout < "<:" < tcd_query_sum(a, b) < endl;
                break;
            case 3:
                cin >> a >> b;
                tcd_update_son(a, 1, b);
                break;
            case 4:
                cin >> a;
                cout < "<:" < tcd_query_son(a) < endl;
                break;
            default:
                exit(-1);
        }
    }
    return 0;
}

用于维护序列的splay tree

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

#define rep(i) for (int i=0; i<n; i++)
using namespace std;
typedef long long ll;
const int N = 100005, inf = 0x3f3f3f3f;


typedef struct splaynode *pNode;
struct splaynode {
    pNode pre, ch[2];
    ll value, lazy, max, sum;
    int size, rev;

    void init(ll v) {
        pre = ch[0] = ch[1] = NULL;
        max = value = sum = v;
        lazy = rev = 0;
        size = 1;
    }
} mem[N];

int memtop;

stack<pNode> S;
pNode root;

inline int get_size(pNode &x) {
    return x ? x->size : 0;
}

void pushdown(pNode &x) {
    if (!x) return;
    if (x->lazy) {
        ll w = x->lazy;
        x->value += w;
        if (x->ch[0]) {
            x->ch[0]->lazy += w;
            x->ch[0]->max += w;
            x->ch[0]->sum += w * get_size(x->ch[0]);
        }
        if (x->ch[1]) {
            x->ch[1]->lazy += w;
            x->ch[1]->max += w;
            x->ch[1]->sum += w * get_size(x->ch[1]);
        }
        x->lazy = 0;
    }
    if (x->rev) {
        pNode t = x->ch[0];
        x->ch[0] = x->ch[1];
        x->ch[1] = t;
        x->rev = 0;
        if (x->ch[0]) x->ch[0]->rev ^= 1;
        if (x->ch[1]) x->ch[1]->rev ^= 1;
    }
}

void update(pNode &x) {
    if (!x) return;
    x->size = 1;
    x->max = x->value;
    x->sum = x->value;
    if (x->ch[0]) {
        x->sum += x->ch[0]->sum;
        x->max = max(x->max, x->ch[0]->max);
        x->size += x->ch[0]->size;
    }
    if (x->ch[1]) {
        x->sum += x->ch[1]->sum;
        x->max = max(x->max, x->ch[1]->max);
        x->size += x->ch[1]->size;
    }
}

void rotate(pNode &x, int d) {
    pNode y = x->pre;
    pushdown(y);
    pushdown(x);
    pushdown(x->ch[d]);
    y->ch[!d] = x->ch[d];
    if (x->ch[d] != NULL) x->ch[d]->pre = y;
    x->pre = y->pre;
    if (y->pre != NULL) { if (y->pre->ch[0] == y) y->pre->ch[0] = x; else y->pre->ch[1] = x; }
    x->ch[d] = y;
    y->pre = x;
    update(y);
    if (y == root) root = x;
}

void splay(pNode &src, pNode &dst) {
    pushdown(src);
    while (src != dst) {
        if (src->pre == dst) {
            if (dst->ch[0] == src) rotate(src, 1); else rotate(src, 0);
            break;
        } else {
            pNode y = src->pre, z = y->pre;
            if (z->ch[0] == y) {
                if (y->ch[0] == src) {
                    rotate(y, 1);
                    rotate(src, 1);
                } else {
                    rotate(src, 0);
                    rotate(src, 1);
                }
            } else {
                if (y->ch[1] == src) {
                    rotate(y, 0);
                    rotate(src, 0);
                } else {
                    rotate(src, 1);
                    rotate(src, 0);
                }
            }
            if (z == dst) break;
        }
        update(src);
    }
    update(src);
}

void select(int k, pNode &f) {
    int tmp;
    pNode t = root;
    while (true) {
        pushdown(t);
        tmp = get_size(t->ch[0]);
        if (k == tmp + 1) break;
        if (k <= tmp) t = t->ch[0];
        else {
            k -= tmp + 1;
            t = t->ch[1];
        }
    }
    pushdown(t);
    splay(t, f);
}

inline void selectsegment(int l, int r) {
    select(l, root);
    select(r + 2, root->ch[1]);
}

void insert(int pos, ll value) {  //在pos位置后面插入一个新值value
    selectsegment(pos + 1, pos);
    pNode t;
    pNode x = root->ch[1];
    pushdown(root);
    pushdown(x);
    if (!S.empty()) {
        t = S.top();
        S.pop();
    } else {
        t = &mem[memtop++];
    }
    t->init(value);
    t->ch[1] = x;
    x->pre = t;
    root->ch[1] = t;
    t->pre = root;
    splay(x, root);
}

void add(int a, int b, int value) {  //区间[a,b]中的数都加上value
    selectsegment(a, b);
    pNode x = root->ch[1]->ch[0];
    pushdown(x);
    update(x);
    x->max += value;
    x->lazy += value;
    splay(x, root);
}

void reverse(int a, int b) {   //区间[a,b]中的数翻转
    selectsegment(a, b);
    root->ch[1]->ch[0]->rev ^= 1;
    pNode x = root->ch[1]->ch[0];
    splay(x, root);
}

void revolve(int a, int b, int t) { //区间[a,b]中的数向后循环移t位
    pNode p1, p2;
    selectsegment(a, b);
    select(b + 1 - t, root->ch[1]->ch[0]);
    p1 = root->ch[1]->ch[0];
    pushdown(p1);
    p2 = p1->ch[1];
    p1->ch[1] = NULL;

    select(a + 1, root->ch[1]->ch[0]);
    p1 = root->ch[1]->ch[0];
    pushdown(p1);
    p1->ch[0] = p2;
    p2->pre = p1;

    splay(p2, root);
}

ll getmax(int a, int b) {   //取[a,b]中最小的值
    selectsegment(a, b);
    pNode x = root->ch[1];
    pushdown(x);
    x = x->ch[0];
    pushdown(x);
    update(x);
    return x->max;
}

ll getsum(int a, int b) {
    selectsegment(a, b);
    pNode x = root->ch[1];
    pushdown(x);
    x = x->ch[0];
    pushdown(x);
    update(x);
    return x->sum;
}

void erase(int pos) {               //抹去第pos个元素
    selectsegment(pos, pos);
    pushdown(root->ch[1]);
    S.push(root->ch[1]->ch[0]);        //回收内存
    root->ch[1]->ch[0] = NULL;
    pNode x = root->ch[1];
    splay(x, root);
}


void cutandmove(int a, int b, int c) {
    selectsegment(a, b);
    pNode CutRoot = root->ch[1]->ch[0];
    CutRoot->pre = NULL;
    root->ch[1]->size -= CutRoot->size;
    root->ch[1]->ch[0] = NULL;

    selectsegment(c + 1, c);

    CutRoot->pre = root->ch[1];
    root->ch[1]->ch[0] = CutRoot;
    root->ch[1]->size += CutRoot->size;
}

void cut(int a, int b) {
    selectsegment(a, b);
    pNode CutRoot = root->ch[1]->ch[0];
    CutRoot->pre = NULL;
    root->size -= CutRoot->size;
    root->ch[1]->size -= CutRoot->size;
    root->ch[1]->ch[0] = NULL;
}

vector<ll> ans;

void inorder(pNode x) {
    if (!x) return;
    pushdown(x);
    inorder(x->ch[0]);
    if (x->value != inf) ans.push_back(x->value);
    inorder(x->ch[1]);
}

void init_splaytree(ll *a, int n) {
    memtop = 0;
    root = &mem[memtop++];
    root->init(inf);
    root->ch[1] = &mem[memtop++];
    root->ch[1]->init(inf);
    while (!S.empty()) S.pop();
    rep(i) insert(i, a[i]);
}

splay常见操作

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1000000;
int ch[MAXN][2], f[MAXN], size[MAXN], cnt[MAXN], key[MAXN];
int sz, root;


inline void clear(int x) {
    ch[x][0] = ch[x][1] = f[x] = size[x] = cnt[x] = key[x] = 0;
}
int new_node(int x, int fa = 0) {
    sz += 1;
    ch[sz][0] = ch[sz][1] = 0;
    f[sz] = fa;
    size[sz] = cnt[sz] = 1;
    key[sz] = x;
    return sz;
}

inline bool get(int x) {
    return ch[f[x]][1] == x;
}

inline void update(int x) {
    if (x) {
        size[x] = cnt[x];
        if (ch[x][0]) size[x] += size[ch[x][0]];
        if (ch[x][1]) size[x] += size[ch[x][1]];
    }
}

inline void rotate(int x) {
    int old = f[x], oldf = f[old], whichx = get(x);
    ch[old][whichx] = ch[x][!whichx];
    f[ch[old][whichx]] = old;
    ch[x][!whichx] = old;
    f[old] = x;
    f[x] = oldf;
    if (oldf)
        ch[oldf][ch[oldf][1] == old] = x;
    update(old);
    update(x);
}

inline void splay(int x) {
    for (int fa; (fa = f[x]); rotate(x))
        if (f[fa])
            rotate((get(x) == get(fa)) ? fa : x);
    root = x;
}


inline void insert(int x) {
    if (root == 0) {
        root = new_node(x);
        return;
    }
    int now = root, fa = 0;
    while (true) {
        if (x == key[now]) {
            cnt[now]++;
            update(now);
            update(fa);
            splay(now);
            break;
        }
        fa = now;
        now = ch[now][key[now] < x];
        if (now == 0) {
            int nd = new_node(x, fa);
            ch[fa][key[fa] < x] = nd;
            update(fa);
            splay(nd);
            break;
        }
    }
}


inline int find(int x) {
    int now = root, ans = 0;
    while (true) {
        if (x < key[now]) {
            now = ch[now][0];
        } else {
            ans += (ch[now][0] ? size[ch[now][0]] : 0);
            if (x == key[now]) {
                splay(now);
                return ans + 1;
            }
            ans += cnt[now];
            now = ch[now][1];
        }
    }
}

inline int findx(int x) {
    int now = root;
    while (true) {
        if (ch[now][0] && x <= size[ch[now][0]])
            now = ch[now][0];
        else {
            int temp = (ch[now][0] ? size[ch[now][0]] : 0) + cnt[now];
            if (x <= temp) return key[now];
            x -= temp;
            now = ch[now][1];
        }
    }
}

inline int pre() {
    int now = ch[root][0];
    while (ch[now][1]) now = ch[now][1];
    return now;
}

inline int next() {
    int now = ch[root][1];
    while (ch[now][0]) now = ch[now][0];
    return now;
}

inline void del(int x) {
    find(x);
    if (cnt[root] > 1) {
        cnt[root] -= 1;
        update(root);
    }
    else if (!ch[root][0] && !ch[root][1]) {
        clear(root);
        root = 0;
    }
    else if (!ch[root][0]) {
        int oldroot = root;
        root = ch[root][1];
        f[root] = 0;
        clear(oldroot);
    } else if (!ch[root][1]) {
        int oldroot = root;
        root = ch[root][0];
        f[root] = 0;
        clear(oldroot);
    } else {
        int leftbig = pre(), oldroot = root;
        splay(leftbig);
        ch[root][1] = ch[oldroot][1];
        f[ch[oldroot][1]] = root;
        clear(oldroot);
        update(root);
    }
}

int main() {
    int n, opt, x;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &opt, &x);
        switch (opt) {
            case 1:
                insert(x);
                break;
            case 2:
                del(x);
                break;
            case 3:
                printf("%d\n", find(x));
                break;
            case 4:
                printf("%d\n", findx(x));
                break;
            case 5:
                insert(x);
                printf("%d\n", key[pre()]);
                del(x);
                break;
            case 6:
                insert(x);
                printf("%d\n", key[next()]);
                del(x);
                break;
        }
    }
}