XCPC模板 | Moonglade

XCPC算法竞赛模板 by MorphLing

图论

单源最短路径（dijkstra）

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+5;
const LL INF=0x3f3f3f3f3f3f3f3f;

struct Dijkstra {
    struct Edge {
        int to;LL val;
    };
    struct Node {
        LL dis;int key;
        friend bool operator < (const Node &x,const Node &y) {
            return x.dis>y.dis;
        }
    };
    bool vis[N];
    int n,m,s;
    LL dis[N];
    vector<Edge>G[N];
    priority_queue<Node>Q;
    void init(int _n,int _s) {
        n=_n,s=_s;
        for (int i=0;i<=n;i++) G[i].clear();
        for (int i=1;i<=n;i++) dis[i]=INF;
    }
    void addEdge(int from,int to,LL val) {
        G[from].push_back({to,val});
    }
    void go() {
        dis[s]=0;
        Q.push({0,s});
        while(!Q.empty()) {
            Node top=Q.top(); Q.pop();
            int now=top.key;
            if (vis[now]) continue;
            vis[now]=1;
            for (int i=0;i<G[now].size();i++) {
                int to=G[now][i].to;
                if (dis[to]>dis[now]+G[now][i].val) {
                    dis[to]=dis[now]+G[now][i].val;
                    if (!vis[to]) Q.push({dis[to],to});
                }
            }
        }
    }
}dijkstra;

int n,m,s;

int main() {
    cin>>n>>m>>s;
    dijkstra.init(n,s);
    for (int i=1;i<=m;i++) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        dijkstra.addEdge(u,v,w);
    }
    dijkstra.go();
    for (int i=1;i<=n;i++) printf("%lld ",dijkstra.dis[i]);
    return 0;
}

树的重心

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
int ans = N,head[N],nxt[N*2],e[N*2],tot,n;//无向图开两倍空间
bool st[N];
void add(int u,int v) {
    e[tot] = v;
    nxt[tot] = head[u];
    head[u] = tot++;
}
int dfs(int u) {
    st[u] = true;
    int cnt = 0,sum = 0;
    for(int i=head[u];i != -1;i = nxt[i]) {
        int j = e[i];
        if(!st[j]) {
            int s = dfs(j);
            cnt = max(cnt,s);//每次统计以u为根的子树中点的个数的最大值
            sum += s;
        }
    }
    cnt = max(cnt,n - sum - 1);//与剩余的点的个数比较
    ans = min(ans,cnt);//比较各个最大值中的最小值
    return sum + 1;//返回以u为根的子树中的点的个数（加上本身）
}
int main() {
    cin >> n;
    int l,r;
    memset(head,-1,sizeof(head));
    for(int i=0;i<n;i++) {
        cin >> l >> r;
        add(l,r);
        add(r,l);
    }
    dfs(1);
    cout << ans;
    return 0;
}

无向图tarjan求割点、割边、点双连通分量

##include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5;

struct Edge {
    int from, to;
    Edge(){}
    Edge(int f, int t) {
        from = f;
        to = t;
    }
};
vector<int> G[N]; // 存图
vector<Edge> bridge; // 存桥
vector<int> cut_vertex; // 存割点
vector<int> compo_vertex[N]; // 存点双连通分量点
vector<Edge> compo_edge[N]; // 存点双连通分量边

vector<Edge> st_edge; // tarjan
vector<int> st_vertex; // tarjan
int dfn[N], low[N], IDX; // tarjan
int cut[N]; // cut[x] > 0 则为割点
int TOT; // 点双连通分量的数量

int n, m;

void init() {
    for (int i = 1; i <= n; i++) {
        G[i].clear();
        compo_vertex[i].clear();
        compo_edge[i].clear();
        dfn[i] = cut[i] = 0;
    }
    IDX = TOT = 0;
    bridge.clear(); cut_vertex.clear();
}

void tarjan(int x, int ff) {
    dfn[x] = low[x] = ++IDX;
    for (auto to : G[x]) {
        if (to == ff) continue;
        if (!dfn[to]) {
            st_edge.push_back(Edge(x, to));
            st_vertex.push_back(to);
            tarjan(to, x);
            low[x] = min(low[x], low[to]);
            if (low[to] >= dfn[x]) {
                cut[x]++;
                TOT++; 
                compo_vertex[TOT].clear(); compo_vertex[TOT].push_back(x);
                compo_edge[TOT].clear();
                while(!st_vertex.empty() && st_vertex.back() != x) { // 存点
                    compo_vertex[TOT].push_back(st_vertex.back());
                    st_vertex.pop_back();
                }
                while(st_edge.back().from != x) { // 存边
                    compo_edge[TOT].push_back(st_edge.back());
                    st_edge.pop_back();
                }
                compo_edge[TOT].push_back(st_edge.back());
                st_edge.pop_back();    
            }
            if (low[to] > dfn[x]) bridge.push_back(Edge(x, to));
        } else {
            if (dfn[to] < dfn[x]) st_edge.push_back(Edge(x, to));
            low[x] = min(low[x], dfn[to]);
        }
    }
}

void solve() {
    scanf("%d %d", &n, &m);
    init();
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            cut[i] = -1;
            tarjan(1, -1);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (cut[i]) cut_vertex.push_back(i);
    }
    int mx = 0;
    for (int i = 1; i <= TOT; i++) mx = max(mx, (int) compo_edge[i].size());
    int gcd = __gcd(TOT, mx);
    printf("%d %d %d %d\n", cut_vertex.size(), bridge.size(), TOT / gcd, mx / gcd);
}
int main() {
    int T; cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

有向图tarjan缩点

#include <bits/stdc++.h>

using namespace std;

const int N = 3e4 + 5, INF = 0x3f3f3f3f;

struct Edge {
    int to, v;
    Edge(){}
    Edge(int T, int V) {
        to = T;
        v = V;
    }
};

vector<Edge> G[N];
vector<int> g[N];
vector<int> bcc[N];
queue<int> topo;
vector<int> ord;

int n, x, y, s, deg[N], dis[N];

int dfn[N], low[N], IDX, belong[N], sta[N], top, TAR;

bool vis[N];

void tarjan(int x) {
    dfn[x] = low[x] = ++IDX;
    vis[x] = 1, sta[++top] = x;
    for (auto T : G[x]) {
        int to = T.to;
        if (!dfn[to]) {
            tarjan(to);
            low[x] = min(low[x], low[to]);
        } else if (vis[to]) low[x] = min(low[x], dfn[to]);
    }
    if (low[x] == dfn[x]) {
        int now = sta[top];
        TAR++; bcc[TAR].clear();
        while(sta[top + 1] != x) {
            vis[now] = 0;
            belong[now] = TAR;
            bcc[TAR].push_back(now);
            now = sta[--top];
        }
    }
}

void tarjan_go() {
    for (int i = 1; i <= TAR; i++) g[i].clear();
    for (int i = 1; i <= n; i++) {
        for (auto T : G[i]) {
            int u = i, v = T.to;
            u = belong[u], v = belong[v];
            if (u != v) {
                g[u].push_back(v);
                deg[v]++;
            }
        }
    }
}

struct Node {
    int key, dis;
    bool operator < (const Node &N) const {
        return dis > N.dis;
    }
    Node(){}
    Node(int k, int d) {
        key = k;
        dis = d;
    }
};
priority_queue<Node> p;

void dijkstra(int now) {
    for (auto x : bcc[now]) {
        if (dis[x] != INF) p.push(Node(x, dis[x]));
    }
    while(!p.empty()) {
        int now = p.top().key; p.pop();
        if (vis[now]) continue;
        vis[now] = 1;
        for (auto T : G[now]) {
            int to = T.to, d = T.v;
            if (vis[to]) continue;
            if (dis[to] > dis[now] + d) {
                dis[to] = dis[now] + d;
                if (belong[to] != belong[now]) continue;
                p.push(Node(to, dis[to]));
            }
        }
    }
}

int main() {
    scanf("%d %d %d %d", &n, &x, &y, &s);
    for (int i = 1; i <= x; i++) {
        int u, v, w; scanf("%d %d %d", &u, &v, &w);
        G[u].push_back(Edge(v, w));
        G[v].push_back(Edge(u, w));
    }
    for (int i = 1; i <= y; i++) {
        int u, v, w; scanf("%d %d %d", &u, &v, &w);
        G[u].push_back(Edge(v, w));
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    tarjan_go();
    for (int i = 1; i <= TAR; i++) {
        if (deg[i] == 0) topo.push(i);
    }
    while(!topo.empty()) {
        int now = topo.front(); topo.pop();
        ord.push_back(now);
        for (auto to : g[now]) {
            deg[to]--;
            if (deg[to] == 0) topo.push(to);
        }
    }
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    for (auto i : ord) {
        dijkstra(i);
    }
    for (int i = 1; i <= n; i++) {
        if (dis[i] != INF) printf("%d\n", dis[i]);
        else printf("NO PATH\n");
    }
    return 0;
}

虚树+LCA优化

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

const int N=2e5+5;

int pre[N][25],dfn[N],deep[N],sta[N],TOP,lg[N];

int A[N],n,s,NODE,x,y;

ll ans=0;

vector<int>G[N];
vector<int>E[N];
vector<int>D[N];

void DFS(int x,int fa) {
    int to;
    dfn[x]=++NODE;
    deep[x]=deep[fa]+1;
    D[deep[x]].push_back(x);
    pre[x][0]=fa;
    for (int i=1;(1<<i)<=deep[x];i++) pre[x][i]=pre[pre[x][i-1]][i-1];
    for (int i=0;i<G[x].size();i++) {
        to=G[x][i];
        if (to!=fa)
            DFS(to,x);
    }
}

int LCA(int x,int y) {
    if (deep[x]<deep[y]) swap(x,y);
    while(deep[x]>deep[y]) x=pre[x][lg[deep[x]-deep[y]]-1];
    if (x==y) return x;
    for (int i=lg[deep[x]]-1;i>=0;i--)
        if (pre[x][i]!=pre[y][i])
            x=pre[x][i],y=pre[y][i];
    return pre[x][0];
}

void Insert(int x) {
    if (TOP==1) {
        if (sta[TOP]!=x) sta[++TOP]=x;
        return;
    }
    int lca=LCA(x,sta[TOP]);
    while(TOP>=2 && dfn[sta[TOP-1]]>=dfn[lca]) {
        E[sta[TOP-1]].push_back(sta[TOP]);
        TOP--;
    }
    if (sta[TOP]!=lca) E[lca].push_back(sta[TOP]),sta[TOP]=lca;
    sta[++TOP]=x;
}

ll solve(int x) {
    if (E[x].empty())
        return 1LL*A[x];
    ll ret=0;
    for (int i=0;i<E[x].size();i++) {
        int to=E[x][i];
        ll sol=solve(to);
        if (sol!=0)
            ret+=max(1LL,sol-(deep[to]-deep[x]));
    }
    E[x].clear();
    return ret;
}

int main() {
    cin>>n>>s;
    for (int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<(lg[i-1])==i);
    for (int i=1;i<=n;i++) scanf("%d",&A[i]);
    for (int i=1;i<=n-1;i++) {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DFS(s,0);
    for (int i=1;!D[i].empty();i++) {
        sort(D[i].begin(),D[i].end(),[&](int u,int v){return dfn[u]<dfn[v];});
        TOP=0;
        sta[++TOP]=s;
        for (int j=0;j<D[i].size();j++) {
            Insert(D[i][j]);
        }
        while(TOP>1) {
            E[sta[TOP-1]].push_back(sta[TOP]);
            TOP--;
        }
        ll sol=solve(s);
        if (sol) ans+=max(1LL,sol-1);
    }
    printf("%lld",ans);
    return 0;
}

根据深度建虚树

void build() {
    sum = 1;
    dep[1] = 1;
    ans = 0;
    for (int i = 2; i <= m; i++) {
        int j = i;
        for (; j != mindiv[j]; j /= mindiv[j]) sum++;
        lcadep[i] = bit.query(m) - bit.query(j - 1) + 1;
        sum++;
        dep[i] = sum;
        for (j = i; j > 1; j /= mindiv[j]) bit.modify(mindiv[j]);
        ans += 1ll * (dep[i] - 1) * w[i];
    }
    TOP = 0, TOT = 1;
    st[++TOP] = {1, 1};
    W[1] = w[1];
    for (int i = 2; i <= m; i++) {
        if (lcadep[i] != dep[i - 1]) {
            while(TOP > 1 && st[TOP - 1].dep >= lcadep[i]) {
                G[st[TOP - 1].num].push_back({st[TOP].num, st[TOP].dep - st[TOP - 1].dep});
                TOP--;
            }
            if (lcadep[i] != st[TOP].dep) {
                G[++TOT].push_back({st[TOP].num, st[TOP].dep - lcadep[i]});
                st[TOP] = {TOT, lcadep[i]};
            }
        }
        st[++TOP] = {++TOT, dep[i]};
        W[TOT] = w[i];
    }
    while(TOP > 1) {
        G[st[TOP - 1].num].push_back({st[TOP].num, st[TOP].dep - st[TOP - 1].dep});
        TOP--;
    }
}

点分治

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

const int N = 1e4 + 5, M = 1e7 + 5, P = 1e2 + 5, INF = 0x3f3f3f3f;

struct Edge {
    int to, v;
};

struct BIT {
    int t[N<<1];
    int lowbit(int x) {return x &(-x);}
    void add(int x, int v) {
        while(x < N) {
            t[x] += v;
            x += lowbit(x);
        }
    }
    int ask(int x) {
        int res = 0;
        while(x) {
            res += t[x];
            x -= lowbit(x);
        }
        return res;
    }
}bit;

int n, m, k, q[P], cnt[P], bucket[M];

vector<int> D;

/**variables of tree divide*/
int tot, sz[N], MN, rt;

bool vis[N];

vector<Edge> G[N];

int Getroot(int x, int f) {
    int sum = 0, mx = 0, tmp;
    for (auto T : G[x]) {
        int to = T.to;
        if (vis[to] || to == f) continue;
        tmp = Getroot(to, x);
        sum += tmp;
        mx = max(mx, tmp);
    }
    sum++;
    mx = max(mx, tot - sum);
    if (mx < MN) {
        MN = mx;
        rt = x;
    }
    return sum;
}

void Getsz(int x, int f) {
    sz[x] = 0;
    for (auto T : G[x]) {
        int to = T.to;
        if (vis[to] || to == f) continue;
        Getsz(to, x);
        sz[x] += sz[to];
    }
    sz[x]++;
}

void Getdis(int x, int len, int f) {
    D.push_back(len);
    for (auto T : G[x]) {
        int to = T.to, v = T.v;
        if (vis[to] || to == f) continue;
        Getdis(to, len + v, x);
    }
}

void calc(int x, int len, int type) {
    D.clear();
    Getdis(x, len, -1);
    for (int y : D) {
        if (y > M) continue;
        for (int i = 1; i <= m; i++) {
            if (q[i] - y < 0) continue;
            cnt[i] += type * bucket[q[i] - y];
        }
        bucket[y]++;
    }
    for (int y : D) {
        if (y > M) continue;
        bucket[y]--;
    }
}

void solve(int x) {
    vis[x] = 1;
    calc(x, 0, 1);
    for (auto T : G[x]) {
        int to = T.to, v = T.v;
        if (vis[to]) continue;
        calc(to, v, -1);
        tot = sz[to], MN = INF;
        Getroot(to, -1);
        Getsz(rt, -1);
        solve(rt);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= n - 1; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    for (int i = 1; i <= m; i++) scanf("%d", &q[i]);
    tot = n, MN = INF;
    Getroot(1, -1);
    Getsz(rt, -1);
    solve(rt);
    for (int i = 1; i <= m; i++) {
        printf("%s\n", cnt[i] ? "AYE" : "NAY");
    }
    return 0;
}

树上启发式合并dsu on tree

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ' '

using namespace std;
typedef long long ll;

const int N = 1e5 + 5, M = 2e6 + 5;

int n, sz[N], son[N], a[N], tot[M], num[M][25], ndfn[N], IDX, f[N], g[N];

ll ans;

vector<int> G[N];

vector<int> vc;

void dfs1(int x, int ff) {
    f[x] = ++IDX;
    ndfn[IDX] = x;
    sz[x] = 1;
    for (int to : G[x]) {
        if (to == ff) continue;
        dfs1(to, x);
        sz[x] += sz[to];
        if (sz[to] > sz[son[x]]) son[x] = to;
    }
    g[x] = IDX;
}

void modify(int x, int v) {
    tot[a[x]] += v;
    for (int j = 0; j <= 20; j++) {
        if ((x >> j) & 1) num[a[x]][j] += v;
    }
}

void dfs2(int x, int ff, int keep) {
    for (int to : G[x]) {
        if (to == ff || to == son[x]) continue;
        dfs2(to, x, 0);
    }
    if (son[x]) dfs2(son[x], x, 1);
    for (int to : G[x]) {
        if (to == ff || to == son[x]) continue;
        for (int i = f[to]; i <= g[to]; i++) {
            int now = ndfn[i];
            int k = a[x] ^ a[now];
            for (int j = 0; j <= 20; j++) {
                if ((now >> j) & 1) ans += (1 << j) * (tot[k] - num[k][j]);
                else ans += (1 << j) * num[k][j];
            }
        }
        for (int i = f[to]; i <= g[to]; i++) {
            int j = ndfn[i];
            modify(j, 1);
        }
    }
    modify(x, 1);
    if (!keep) {
        for (int i = f[x]; i <= g[x]; i++) {
            modify(ndfn[i], -1);
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n - 1; i++) {
        int x, y; scanf("%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs1(1, -1);
    dfs2(1, -1, 1);
    cout << ans;
    return 0;
}

树链剖分(轻重链剖分)

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

const int N=1e5+5;

LL q[N];

int n,m,r,p,ord[N];

struct segTree {
    LL t[N<<2];
    LL lztag[N<<2];
    void init() {
        memset(t,0,sizeof(t));
        memset(lztag,0,sizeof(lztag));
    }
    void pushdown(int o,int l,int r) {
        if (lztag[o]) {
            int mid=(l+r)>>1;
            t[o*2]+=lztag[o]*(mid-l+1);
            t[o*2]%=p;
            t[o*2+1]+=lztag[o]*(r-mid);
            t[o*2+1]%=p;
            lztag[o*2]+=lztag[o];
            lztag[o*2]%=p;
            lztag[o*2+1]+=lztag[o];
            lztag[o*2+1]%=p;
            lztag[o]=0;
        }
    }
    void pushup(int o,int l,int r) {
        t[o]=(t[o*2]+t[o*2+1])%p;
    }
    void build(int o,int l,int r) {
        if (l==r) {
            t[o]=ord[l]%p;
            return;
        }
        int mid=(l+r)>>1;
        build(o*2,l,mid);
        build(o*2+1,mid+1,r);
        pushup(o,l,r);
    }
    void modify(int o,int l,int r,int tl,int tr,int v) {
        if (tl<=l && r<=tr) {
            t[o]+=1LL*v*(r-l+1);
            t[o]%=p;
            lztag[o]+=v;
            lztag[o]%=p;
            return;
        }
        int mid=(l+r)>>1;
        pushdown(o,l,r);
        if (tl<=mid) modify(o*2,l,mid,tl,tr,v);
        if (tr>mid) modify(o*2+1,mid+1,r,tl,tr,v);
        pushup(o,l,r);
    }
    LL query(int o,int l,int r,int tl,int tr) {
        if (tl<=l && tr>=r) return t[o];
        int mid=(l+r)>>1;
        pushdown(o,l,r);
        if (tr<=mid) return query(o*2,l,mid,tl,tr)%p;
        if (tl>mid) return query(o*2+1,mid+1,r,tl,tr)%p;
        return (query(o*2,l,mid,tl,tr)+query(o*2+1,mid+1,r,tl,tr))%p;
    }
}ST;

int sz[N],dep[N],son[N],fa[N],top[N],num[N],cnt;

vector<int>G[N];

void init() {
    memset(sz,0,sizeof(sz));
    cnt=0;
    fa[r]=-1;
    dep[r]=1;
    top[r]=r;
}

void dfs1(int x) {
    int mxson=-1;
    son[x]=-1;
    for (auto to:G[x]) {
        if (to==fa[x]) continue;
        dep[to]=dep[x]+1;
        fa[to]=x;
        dfs1(to);
        if (sz[to]>mxson) mxson=sz[to], son[x]=to;
        sz[x]+=sz[to];
    }
    sz[x]++;
}
void dfs2(int x,int tp) {
    num[x]=++cnt;
    ord[cnt]=q[x];
    top[x]=tp;
    if (~son[x]) dfs2(son[x],tp);
    for (auto to:G[x]) {
        if (to==fa[x] || to==son[x]) continue;
        dfs2(to,to);
    }
}
void chainModify(int x,int y,int z) {
    while(top[x]!=top[y]) {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        ST.modify(1,1,n,num[top[x]],num[x],z);
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    ST.modify(1,1,n,num[x],num[y],z);
}
LL chainQuery(int x,int y) {
    LL res=0;
    while(top[x]!=top[y]) {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        res+=ST.query(1,1,n,num[top[x]],num[x]);
        res%=p;
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    res+=ST.query(1,1,n,num[x],num[y]);
    res%=p;
    return res;
}
void subtreeModify(int x,int z) {
    ST.modify(1,1,n,num[x],num[x]+sz[x]-1,z);
}
LL subtreeQuery(int x) {
    return ST.query(1,1,n,num[x],num[x]+sz[x]-1);
}

int main() {
    cin>>n>>m>>r>>p;
    for (int i=1;i<=n;i++) {
        scanf("%lld",&q[i]);
        q[i]%=p;
    }
    for (int i=1;i<=n-1;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    init();
    dfs1(r);
    dfs2(r,r);
    ST.build(1,1,n);
    for (int i=1;i<=m;i++) {
        int opt,x,y;
        LL z;
        scanf("%d",&opt);
        if (opt==1) {
            scanf("%d%d%lld",&x,&y,&z);
            z%=p;
            chainModify(x,y,z);
        }
        if (opt==2) {
            scanf("%d%d",&x,&y);
            printf("%lld\n",chainQuery(x,y));
        }
        if (opt==3) {
            scanf("%d%lld",&x,&z);
            z%=p;
            subtreeModify(x,z);
        }
        if (opt==4) {
            scanf("%d",&x);
            printf("%lld\n",subtreeQuery(x));
        }
    }
    return 0;
}

动态树LCT

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

const int N=1e5+5,INF=0x3f3f3f3f;

struct Link_Cut_Tree{
    int top,root,ch[N][2],ff[N],val[N],xr[N],tag[N],q[N];
    bool isroot(int x) {
        return ch[ff[x]][0]!=x && ch[ff[x]][1]!=x;
    }
    void push_up(int x) {
        xr[x]=xr[ch[x][0]]^xr[ch[x][1]]^val[x];
    }
    void push_down(int x) {
        if (tag[x]) {
            swap(ch[x][0],ch[x][1]);
            tag[ch[x][0]]^=1;
            tag[ch[x][1]]^=1;
            tag[x]=0;
        }
    }
    void Rotate(int x) {
        int y=ff[x],z=ff[y],k=ch[y][1]==x;
        if (!isroot(y)) {
            ch[z][ch[z][1]==y]=x;
        }
        ff[x]=z;
        ch[y][k]=ch[x][k^1],ff[ch[y][k]]=y;
        ch[x][k^1]=y,ff[y]=x;
        push_up(y);push_up(x);
    }
    void Splay(int x) {
        top=1;q[top]=x;
        for (int i=x;!isroot(i);i=ff[i]) q[++top]=ff[i];
        for (int i=top;i;i--) push_down(q[i]);
        while(!isroot(x)) {
            int y=ff[x],z=ff[y];
            if (!isroot(y)) {
                if ((ch[y][0]==x)^(ch[z][0]==y)) Rotate(x);
                else Rotate(y);
            }
            Rotate(x);
        }
    }
    void Access(int x) {
        for (int y=0;x;y=x,x=ff[x]) {
            Splay(x);ch[x][1]=y;push_up(x);
        }
    }
    void Makeroot(int x) {
        Access(x);Splay(x);
        tag[x]^=1;
        push_down(x);
    }
    int Findroot(int x) {
        Access(x); Splay(x);
        push_down(x);
        while(ch[x][0]) {
            push_down(x);x=ch[x][0];
        }
        Splay(x);
        return x;
    }
    void Split(int x,int y) {
        Makeroot(x);
        Access(y); Splay(y);
    }
    void Link(int x,int y) {
        Makeroot(x);
        if (Findroot(y)==x) return;
        ff[x]=y;
    }
    void Cut(int x,int y) {
        Makeroot(x);
        if (Findroot(y)!=x || ff[y]!=x || ch[y][0]) return;
        ff[y]=ch[x][1]=0;
        push_up(x);
    }
    int Query(int x,int y) {
        Split(x,y);
        return xr[y];
    }
    void Modify(int x,int y) {
        val[x]=y; Makeroot(x);
    }
}lct;

int n,m;

int main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) scanf("%d",&lct.val[i]),lct.xr[i]=lct.val[i];
    for (int i=1;i<=m;i++) {
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        switch(opt) {
            case 0:printf("%d\n",lct.Query(x,y));break;
            case 1:lct.Link(x,y);break;
            case 2:lct.Cut(x,y);break;
            case 3:lct.Modify(x,y);break;
        }
    }
    return 0;
}

2-SAT

// 建图
n = read(), m = read();
for (int i = 0; i < m; ++i) {
    // 笔者习惯对 x 点标号为 x，-x 标号为 x+n，当然也可以反过来。
    int a = read(), va = read(), b = read(), vb = read();
    if (va && vb) { // a, b 都真，-a -> b, -b -> a
        g[a + n].push_back(b);
        g[b + n].push_back(a);
    } else if (!va && vb) { // a 假 b 真，a -> b, -b -> -a
        g[a].push_back(b);
        g[b + n].push_back(a + n);
    } else if (va && !vb) { // a 真 b 假，-a -> -b, b -> a
        g[a + n].push_back(b + n);
        g[b].push_back(a);
    } else if (!va && !vb) { // a, b 都假，a -> -b, b -> -a
        g[a].push_back(b + n);
        g[b].push_back(a + n);
    }
}
// 找环
// 注意所有东西都要开两倍空间，因为每个变量存了两次
void tarjan(int u) {
    low[u] = dfn[u] = ++dfsClock;
    stk.push(u); ins[u] = true;
    for (const auto &v : g[u]) {
        if (!dfn[v]) tarjan(v), low[u] = std::min(low[u], low[v]);
        else if (ins[v]) low[u] = std::min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        ++sccCnt;
        do {
            color[u] = sccCnt;
            u = stk.top(); stk.pop(); ins[u] = false;
        } while (low[u] != dfn[u]);
    }
}
// Tarjan 找环，得到的 color[x] 是 x 所在的 scc 的拓扑逆序。
for (int i = 1; i <= (n << 1); ++i) if (!dfn[i]) tarjan(i);
// 输出
for (int i = 1; i <= n; ++i)
    if (color[i] == color[i + n]) { // x 与 -x 在同一强连通分量内，一定无解
        puts("IMPOSSIBLE");
        exit(0);
    }
puts("POSSIBLE");
for (int i = 1; i <= n; ++i)
    print((color[i] < color[i + n])), putchar(' '); // 如果不使用 Tarjan 找环，请改成大于号
puts("");

最大流Dinic

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

const int N=5e3+5;

//理论上界O(N^2*M)
//二分图最大匹配时间复杂度O(sqrt(N)*M)
struct Dinic{
    struct Edge{
        int to;LL v;int rev;
    };
    int n,s,t,dep[N],_cur[N];
    bool used[N];
    vector<Edge>G[N];
    queue<int>L;
    void init(int n_,int s_,int t_) {
        n=n_,s=s_,t=t_;
        for (int i=0;i<=n;i++) G[i].clear();
    }
    void addEdge(int x,int y,LL v) {
        G[x].push_back({y,v,G[y].size()});
        G[y].push_back({x,0,G[x].size()-1});
    }
    bool bfs() {
        memset(used,0,sizeof(used));
        dep[s]=1,used[s]=1;
        L.push(s);
        while(!L.empty()) {
            int cur=L.front();
            L.pop();
            for (int i=0;i<G[cur].size();i++) {
                Edge &e=G[cur][i];
                if (!used[e.to] && e.v>0) {
                    dep[e.to]=dep[cur]+1;
                    used[e.to]=1;
                    L.push(e.to);
                }
            }
        }
        return used[t];
    }
    LL dfs(int c,LL flow) {
        if (c==t ||flow==0) return flow;
        LL ret=0,f;
        for (int &i=_cur[c];i<G[c].size();i++) {
            Edge &e=G[c][i];
            if (dep[e.to]==dep[c]+1 && (f=dfs(e.to,min(flow,e.v)))>0) {
                ret+=f,flow-=f,e.v-=f;
                G[e.to][e.rev].v+=f;
                if (!flow) break;
            }
        }
        return ret;
    }
    LL go() {
        LL ans=0;
        while(bfs()) {
            memset(_cur,0,sizeof(_cur));
            ans+=dfs(s,1LL*100*INT_MAX);
        }
        return ans;
    }
}dinic;

int n,m,e,s,t;
int main() {
    cin>>n>>m>>s>>t;
    dinic.init(n,s,t);
    for (int i=1;i<=m;i++) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        dinic.addEdge(u,v,w);
    }
    printf("%lld\n",dinic.go());
    return 0;
}

集合划分建图(最大流最小割)

void solve()
{
    cin>>n;
    s=0,t=n+n*n*2+1;
    for (int i=s;i<=t;i++) G[i].clear();
    sum=0;
    for (int i=1;i<=n;i++)
    {
        scanf("%lf",&a);
        ac=round(a*100);
        addEdge(s,i,ac);
        sum+=ac;
    }
    for (int i=1;i<=n;i++)
    {
        scanf("%lf",&a);
        ac=round(a*100);
        addEdge(i,t,ac);
        sum+=ac;
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            scanf("%lf",&b[i][j]);
            ac=round((b[i][j])*100);
            sum+=ac*2;
            addEdge(s,n+((i-1)*n+j)*2-1,ac);
            addEdge(n+((i-1)*n+j)*2,t,ac);
            addEdge(n+((i-1)*n+j)*2-1,i,INF);
            addEdge(n+((i-1)*n+j)*2-1,j,INF);
            addEdge(i,n+((i-1)*n+j)*2,INF);
            addEdge(j,n+((i-1)*n+j)*2,INF);
        }
    ll mincut=Dinic();
    double ans=(sum-mincut)/100.0;
    printf("%.2lf\n",ans);
}

int main()
{
    cin>>T;
    while(T--) solve();
    return 0;
}

最小费用最大流（MCMF）

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
const int INF=0x3f3f3f3f3f3f3f3f;

struct MCMF {
    struct E{
        int from,to;
        LL flow,dis;
    };
    queue<int>Q;
    vector<E>edge;
    vector<int>G[N];
    bool vis[N];
    int n,m,s,t,pre[N],last[N];
    LL dis[N],flow[N],maxflow,mincost;
    void init(int _n,int _s,int _t) {
        n=_n,s=_s,t=_t;
        for (int i=0;i<=n;i++) G[i].clear();
        edge.clear();m=0;
        maxflow=mincost=0;
    }
    void addEdge(int from,int to,int flow,int cost) {
        edge.push_back({from,to,flow,cost});
        edge.push_back({to,from,0,-cost});
        G[from].push_back(m++);
        G[to].push_back(m++);
    }
    bool spfa(int s,int t) {
        for (int i=0;i<=n;i++) {
            dis[i]=INF;flow[i]=INF;vis[i]=0;
        }
        Q.push(s);dis[s]=0;vis[s]=1;pre[t]=-1;
        while(!Q.empty()) {
            int now=Q.front();
            Q.pop();
            vis[now]=0;
            for (int i:G[now]) {
                if (edge[i].flow && dis[edge[i].to]>dis[now]+edge[i].dis) {
                    dis[edge[i].to]=dis[now]+edge[i].dis;
                    pre[edge[i].to]=now;
                    last[edge[i].to]=i;
                    flow[edge[i].to]=min(flow[now],edge[i].flow);
                    if (!vis[edge[i].to]) {
                        vis[edge[i].to]=1;
                        Q.push(edge[i].to);
                    }
                }
            }
        }
        return pre[t]!=-1;
    }
    LL go() {
        while(spfa(s,t)) {
            int now=t;
            maxflow+=flow[t];
            mincost+=flow[t]*dis[t];
            while(now!=s) {
                edge[last[now]].flow-=flow[t];
                edge[last[now]^1].flow+=flow[t];
                now=pre[now];
            }
        }
        return mincost;
    }
}mcmf;

int n,m,s,t;

int main() {
    cin>>n>>m>>s>>t;
    mcmf.init(n,s,t);
    for (int i=1;i<=m;i++) {
        int u,v;LL w,f;
        scanf("%d%d%lld%lld",&u,&v,&w,&f);
        mcmf.addEdge(u,v,w,f);
    }
    mcmf.go();
    printf("%lld %lld\n",mcmf.maxflow,mcmf.mincost);
    return 0;
}

二分图最大匹配（匈牙利算法）(最小点覆盖=最大匹配)

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

const int MAXN=5e2+5;

vector<int>G[MAXN];

int n,m,e,ans,u,v;

int vistime[MAXN],mch[MAXN];

bool dfs(int u,int tag) {
    if (vistime[u]==tag) return 0;
    vistime[u]=tag;
    for (auto v:G[u])
        if (mch[v]==0 || dfs(mch[v],tag)) {
            mch[v]=u;
            return 1;
        }
    return 0;
}

int main() {
    cin>>n>>m>>e;
    for (int i=1;i<=e;i++) {
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
    }
    for (int i=1;i<=n;i++)
        if (dfs(i,i)) ans++;
    printf("%d\n",ans);
    return 0;
}

一般图最大匹配（Edmonds带花树）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=1000+20;
const int INF=0x3f3f3f3f;

int N,M;
int n,m;
int d[MAX_N];

bool Graph[MAX_N][MAX_N];
int Match[MAX_N];
bool InQueue[MAX_N],InPath[MAX_N],InBlossom[MAX_N];
int Head,Tail;
int Queue[MAX_N];
int Start,Finish;
int NewBase;
int Father[MAX_N],Base[MAX_N];
int Count;

void CreatGraph(){//O(n^3)
    int u,v;
    vector<int>V[MAX_N];
    memset(Graph,false,sizeof(Graph));
    int tot=1;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&d[i]);
        for (int j=1;j<=d[i];j++) V[i].push_back(tot++);
    }
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        int x=tot++,y=tot++;
        for (int j=0;j<d[u];j++) Graph[V[u][j]][x]=Graph[x][V[u][j]]=1;
        for (int j=0;j<d[v];j++) Graph[V[v][j]][y]=Graph[y][V[v][j]]=1;
        Graph[x][y]=Graph[y][x]=1;
    }
    N=tot-1;
}
void Push(int u){
    Queue[Tail]=u;
    Tail++;
    InQueue[u]=true;
}
int Pop(){
    int res=Queue[Head];
    Head++;
    return res;
}
int FindCommonAncestor(int u,int v){
    memset(InPath,false,sizeof(InPath));
    while(1){
        u=Base[u];
        InPath[u]=1;
        if(u==Start)break;
        u=Father[Match[u]];
    }
    while(1){
        v=Base[v];
        if(InPath[v])break;
        v=Father[Match[v]];
    }
    return v;
}
void ResetTrace(int u){
    int v;
    while(Base[u]!=NewBase){
        v=Match[u];
        InBlossom[Base[u]]=InBlossom[Base[v]]=1;
        u=Father[v];
        if(Base[u]!=NewBase)Father[u]=v;
    }
}
void BloosomContract(int u,int v){
    NewBase=FindCommonAncestor(u,v);
    memset(InBlossom,false,sizeof(InBlossom));
    ResetTrace(u);
    ResetTrace(v);
    if(Base[u]!=NewBase)Father[u]=v;
    if(Base[v]!=NewBase)Father[v]=u;
    for(int tu=1;tu<=N;tu++){
        if(InBlossom[Base[tu]]){
            Base[tu]=NewBase;
            if(!InQueue[tu])Push(tu);
        }
    }
}
void FindAugmentingPath(){
    memset(InQueue,false,sizeof(InQueue));
    memset(Father,0,sizeof(Father));
    for(int i=1;i<=N;i++){
        Base[i]=i;
    }
    Head=Tail=1;
    Push(Start);
    Finish=0;
    while(Head<Tail){
        int u=Pop();
        for(int v=1;v<=N;v++){
            if(Graph[u][v]&&(Base[u]!=Base[v])&&(Match[u]!=v)){
                if((v==Start)||((Match[v]>0)&&Father[Match[v]]>0))BloosomContract(u,v);
                else if(Father[v]==0){
                    Father[v]=u;
                    if(Match[v]>0)Push(Match[v]);
                    else{
                        Finish=v;
                        return;
                    }
                }
            }
        }
    }
}
void AugmentPath(){
    int u,v,w;
    u=Finish;
    while(u>0){
        v=Father[u];
        w=Match[v];
        Match[v]=u;
        Match[u]=v;
        u=w;
    }
}
void Edmonds(){
    memset(Match,0,sizeof(Match));
    for(int u=1;u<=N;u++){
        if(Match[u]==0){
            Start=u;
            FindAugmentingPath();
            if(Finish>0)AugmentPath();
        }
    }
}
void PrintMatch(){
    Count=0;
    for(int u=1;u<=N;u++){
        if(Match[u]>0)Count++;
    }
    if(Count==N)printf("Yes\n");
    else printf("No\n");
}
int main(){
    while(scanf("%d%d",&n,&m)==2){
        CreatGraph();
        Edmonds();
        PrintMatch();
    }
}

数据结构

树状数组

//第一个位置从1开始(0不可用)
struct BIT{
    LL tr[N];
    int lowbit(int x){ return x&(-x); }
    void clr(int x){
        while(x<SZ)
        {
            tr[x]=0;
            x+=lowbit(x);
        }
    }
    void add(int v,int x){
        while(x<N)
        {
            tr[x]+=v;
            x+=lowbit(x);
        }
    }
    LL sum(int x){
        LL sum=0;
        while(x>0)
        {
            sum+=tr[x];
            x-=lowbit(x);
        }
        return sum;
    }
}bit;
//BIT求MEX
struct BIT {
    int bucket[N],tr[N];
    int lowbit(int x){
        return x&(-x);
    }
    void add(int x,int v) {
        if (x<SZ) {
            bucket[x]+=v;
            if (bucket[x]==1 && v==1|| bucket[x]==0 && v==-1)
                while(x<SZ)    {
                    tr[x]+=v;
                    x+=lowbit(x);
                }
        }
    }
    int sum(int x) {
        int sum=0;
        while(x>0) {
            sum+=tr[x];
            x-=lowbit(x);
        }
        return sum;
    }
    int MEX() {
        int l=1,r=SZ-1;
        while(l<r) {
            int mid=(l+r)>>1;
            if (sum(mid)<mid)
                r=mid;
            else l=mid+1;
        }
        return l;
    }
}bit;

二维树状数组

struct BIT{
    int C[N][N];
    int lowbit(int x) {return x&(-x);}
    void Modify(int i,int j,int delta){
        for(int x=i;x<=a;x+=lowbit(x))
            for(int y=j;y<=b;y+=lowbit(y)) {
                C[x][y]+=delta;
            }
    }
    int Sum(int i,int j)
    {
        int result=0;
        for(int x=i;x>0;x-=lowbit(x)) {
            for(int y=j;y>0;y-=lowbit(y)) {
                result+=C[x][y];
            }
        }
        return result;
    }
}bit;

线段树

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

const int N=1e5+5;

struct Segtree {
    LL t[N<<2],lz[N<<2];
    void push_down(int o,int l,int r) {
        if (lz[o]) {
            int mid=(l+r)>>1;
            t[o*2]+=lz[o]*(mid-l+1);
            t[o*2+1]+=lz[o]*(r-mid);
            lz[o*2]+=lz[o];
            lz[o*2+1]+=lz[o];
            lz[o]=0;
        }
    }
    void push_up(int o,int l,int r) {
        t[o]=t[o*2]+t[o*2+1];
    }
    void update(int o,int l,int r,LL v) {
        t[o]+=v*(r-l+1);
        lz[o]+=v;
    }
    void build(int o,int l,int r) {
        lz[o]=0;
        if (l==r) {
            scanf("%lld",&t[o]);
            return;
        }
        int mid=(l+r)>>1;
        build(o*2,l,mid);
        build(o*2+1,mid+1,r);
        push_up(o,l,r);
    }
    void modify(int o,int l,int r,int tl,int tr,LL v) {
        if (tl<=l && tr>=r) {
            update(o,l,r,v);
            return;
        }
        push_down(o,l,r);
        int mid=(l+r)>>1;
        if (tl<=mid) modify(o*2,l,mid,tl,tr,v);
        if (tr>mid) modify(o*2+1,mid+1,r,tl,tr,v);
        push_up(o,l,r);
    }
    LL query(int o,int l,int r,int tl,int tr) {
        if (tl<=l && r<=tr) return t[o];
        push_down(o,l,r);
        int mid=(l+r)>>1;
        if (tr<=mid) return query(o*2,l,mid,tl,tr);
        if (tl>mid) return query(o*2+1,mid+1,r,tl,tr);
        return query(o*2,l,mid,tl,tr)+query(o*2+1,mid+1,r,tl,tr);
    }
}segtree;

int n,m,x,y,k,op;

int main() {
    cin>>n>>m;
    segtree.build(1,1,n);
    for (int i=1;i<=m;i++) {
        scanf("%d",&op);
        switch (op){
            case 1:
                scanf("%d%d%d",&x,&y,&k);
                segtree.modify(1,1,n,x,y,k);
                break;
            case 2:
                scanf("%d%d",&x,&y);
                printf("%lld\n",segtree.query(1,1,n,x,y));
        }
    }
    return 0;
}

ST表

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int a[N][21], n, m;

int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(a[l][k], a[r-(1<<k)+1][k]);
}

int main() {
    cin >> n >> m;
    for (int i=1; i<=n; i++) scanf("%d", &a[i][0]);
    for (int i=1; i<=21; i++) {
        for (int j=1; j+(1<<i)-1<=n; j++) {
            a[j][i] = max(a[j][i-1], a[j+(1<<(i-1))][i-1]);
        }
    }
    for (int i=1, l, r; i<=m; i++) {
        scanf("%d %d", &l, &r);
        printf("%d\n", query(l, r));
    }
    return 0;
}

Splay

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

const int N=1e5+5,INF=0x3f3f3f3f;

struct Splay_tree{
    int root=0,ch[N][2],ff[N],sz[N],cnt[N],val[N],points;
    void push_up(int x) {
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
    }
    void Rotate(int x) {
        int y=ff[x],z=ff[y],k=ch[y][1]==x;
        ch[z][ch[z][1]==y]=x,ff[x]=z;
        ch[y][k]=ch[x][k^1],ff[ch[y][k]]=y;
        ch[x][k^1]=y,ff[y]=x;
        push_up(y);push_up(x);
    }
    void Splay(int x,int goal) {
        while(ff[x]!=goal) {
            int y=ff[x],z=ff[y];
            if (z!=goal) {
                if ((ch[z][1]==y) ^ (ch[y][1]==x)) Rotate(x);
                else Rotate(y);
            }
            Rotate(x);
        }
        if (goal==0) root=x;
    }
    void Insert(int x) {
        int u=root,f=0;
        while(u && val[u]!=x) {
            f=u;
            u=ch[u][val[u]<x];
        }
        if (u) cnt[u]++;
        else {
            u=++points;
            if (f) ch[f][x>val[f]]=u;
            ch[u][0]=ch[u][1]=0;
            ff[u]=f; val[u]=x;
            sz[u]=1; cnt[u]=1;
        }
        Splay(u,0);
    }
    void Find(int x) {
        int u=root;
        if (!u) return;
        while(ch[u][x>val[u]] && x!=val[u]) u=ch[u][x>val[u]];
        Splay(u,0);
    }
    int Next(int x,int f) {
        Find(x);
        int u=root;
        if ((val[u]>x && f) || (val[u]<x && !f)) return u;
        u=ch[u][f];
        while(ch[u][f^1]) u=ch[u][f^1];
        return u;
    }
    void Delete(int x) {
        int pre=Next(x,0),nxt=Next(x,1);
        Splay(pre,0);Splay(nxt,pre);
        int del=ch[nxt][0];
        if (cnt[del]>1) {
            cnt[del]--;
            Splay(del,0);
        }
        else {
            ch[nxt][0]=0;
            //Splay(nxt,0);
        }
    }
    int Rank(int x) {
        Find(x);
        return sz[ch[root][0]];
    }
    int K_th(int x) {
        int u=root;
        if (sz[u]<x) return -1;
        while(true) {
            if (sz[ch[u][0]]+cnt[u]<x) {
                x-=sz[ch[u][0]]+cnt[u];
                u=ch[u][1];
            }
            else if (sz[ch[u][0]]>=x) {
                u=ch[u][0];
            }
            else return u;
        }
    }
}splay;

int n,opt,x;

int main() {
    cin>>n;
    splay.Insert(-INF);splay.Insert(INF);
    while(n--) {
        scanf("%d%d",&opt,&x);
        switch(opt) {
            case 1:splay.Insert(x);break;
            case 2:splay.Delete(x);break;
            case 3:printf("%d\n",splay.Rank(x));break;
            case 4:printf("%d\n",splay.val[splay.K_th(x+1)]);break;
            case 5:printf("%d\n",splay.val[splay.Next(x,0)]);break;
            case 6:printf("%d\n",splay.val[splay.Next(x,1)]);break;
        }
    }
    return 0;
}

DP

四边形不等式优化

若$dp[l][r]=min_{l<k<=r}\{dp[l][k]+dp[k+1][r]+w[l][r]\}$（min也可以改为max）

且$w[l][r]$满足四边形不等式，即：$w[l][r]+w[l+1][r+1]<=w[l+1][r]+w[l][r+1]$

且满足区间单调性，即：$w[l+1][r]<=w[l][r+1]$

则有两个定理（当成结论就好）：

定理一：函数$dp$也满足四边形不等式，即：

$$dp[i][j]+dp[i+1][j+1]<=dp[i+1][j]+dp[i][j+1]$$

定理二：若$dp$满足四边形不等式，定义$s[i][j]$为$dp[i][j]$对应的决策变量的最大值，即：

$$s[i][j]=max_{i<k<=j}\{dp[i][j]=w[i][j]+dp[i][k-1]+dp[k][j]\}$$

则$s[i][j]$单调，即：

$$s[i][j]<=s[i][j+1]<=s[i+1][j+1]$$

发现状态转移方程中$k$的范围存在限制，于是愉快缩小了变量$k$的枚举范围：

$$dp[i][j]=min_{s[i][j-1]<=k<=s[i+1][j]}\{dp[l][k]+dp[k+1][r]+w[l][r]\}$$

#include <bits/stdc++.h>

using namespace std;

const int N = 3e3 + 5, M = 3e2 + 5, INF = 0x3f3f3f3f;

int dp[N][M], d[N][M], x[N], w[N][N];

int n, m;

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (i == j) w[i][j] = 0;
            else w[i][j] = w[i][j - 1] + x[j] - x[(i + j) >> 1];
        }
    }
    memset(dp, INF, sizeof(dp));
    for (int i = 1; i <= m; i++) d[n + 1][i] = n;
    for (int i = 0; i <= m; i++) dp[0][i] = 0;
    for (int j = 1; j <= m; j++) {
        for (int i = n; i >= 1; i--) {
            int id;
            for (int k = d[i][j - 1]; k <= d[i + 1][j]; k++) {
                if (dp[k][j - 1] + w[k + 1][i] < dp[i][j]) {
                    dp[i][j] = dp[k][j - 1] + w[k + 1][i];
                    id = k;
                }
            }
            d[i][j] = id;
        }
    }
    printf("%d\n", dp[n][m]);
    return 0;
}

斜率优化

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e6 + 5;

/** 若找最大值则维护上凸壳 要求K单减
*   若找最小值则维护下凸壳 要求K单增
*   若K无单调性 可以维护凸壳后二分查找
*/

int n, a, b, c;

ll dp[N], sum[N], Q[N], head, tail;

ll Y(int j){return dp[j] + sum[j] * sum[j] * a - sum[j] * b;}
ll X(int j){return sum[j];}
ll K(int i){return 2 * a * sum[i];}
ll B(int i, int j){return Y(j) - K(i) * X(j);}
double slope(int i, int j){return 1.0 * (Y(i) - Y(j)) / (X(i) - X(j));}

int main() {
    cin >> n >> a >> b >> c;
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        sum[i] = sum[i - 1] + x;
    }
    Q[++tail] = 0; head = 1;
    for (int i = 1; i <= n; i++) {
        while(head < tail && slope(Q[head], Q[head + 1]) > K(i)) ++head;
        dp[i] = B(i, Q[head]) + sum[i] * sum[i] * a + sum[i] * b + c;
        while(head < tail && slope(Q[tail - 1], Q[tail]) < slope(Q[tail], i)) --tail;
        Q[++tail] = i;
    }
    printf("%lld\n", dp[n]);
    return 0;
}

数位dp

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;

const int N=200,M=5000;

int digit[20];
int dp[N][M][2][2];
char n[200];

int dfs(int pos,int del,int eqb,int eqa) {
    if (pos==-1) {
        if (del>2500)
            return 1;
        else return 0;
    }
    if (dp[pos][del][eqb][eqa]!=-1) return dp[pos][del][eqb][eqa];
    int upb=eqb?n[pos]:9;
    int sum=0;
    for (int b=0;b<=upb;b++) {
        for (int a=0;a<=(eqa?b:9);a++) {
            sum=(sum+dfs(pos-1,del+a-b,eqb&&(b==n[pos]),eqa&&(a==b)))%MOD;
        }
    }
    dp[pos][del][eqb][eqa]=sum;
    return sum;
}

int main() {
    scanf("%s",n);
    int len=strlen(n);
    reverse(n,n+len);
    for (int i=0;i<len;i++) n[i]-='0';
    memset(dp,-1,sizeof(dp));
    printf("%d",dfs(len-1,2500,1,1));
    return 0;
}

数学

快速幂

int bin(int x,int p) {
    int res=1;
    for (;p;p>>=1,x=(1ll*x*x)%MOD)
        if (p&1) res=(1ll*res*x)%MOD;
    return res;
}

exgcd扩展欧几里得（求ax+by=0整数解）

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

const int MAXN=3e6+5;

void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x = 1, y = 0;
    else Exgcd(b, a % b, y, x), y -= a / b * x;
}
int n,p;

int main()
{
    cin>>n>>p;
    for (int i=1;i<=n;i++)
    {
        ll x, y;
        Exgcd (i, p, x, y);
        x = (x % p + p) % p;
        printf ("%d\n", x); //x是a在mod p下的逆元
    }
}

线性基

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e5 + 5;

int n; ll p[N], tmp[N];

void Insert(ll x) {
    for (int i = 55; i >= 0; i--) {
        if (!(x >> i)) continue;
        if (!p[i]) {
            p[i] = x;
            return;
        }
        x ^= p[i];
    }
}

bool ask(ll x) { //查询x是否能被异或出来
    for (int i = 55; i >= 0; i--)
        if (x >> i) x ^= p[i];
    return x == 0;
}

ll k_th(int k) { //查询第k小异或值
    ll res = 0; int cnt = 0;
    for (int i = 0; i <= 55; i++) {
        for (int j = i - 1; j != -1; j--)
            if (p[i] >> j) p[i] ^= p[j];
        if (p[i]) tmp[cnt++] = p[i];
    }
    if (k >= (1ll <<cnt)) return -1;
    for (int i = 0; i < cnt; i++)
        if (k & (1ll << i)) res ^= tmp[i];
    return res;
}

ll getMx() { //查询最大异或值
    ll res = 0;
    for (int i = 55; i >= 0; i--) {
        res = max(res, res ^ p[i]);
    }
    return res;
}

ll getMn() { //查询最小异或值
    for (int i = 0; i <= 55; i++)
        if (p[i]) return p[i];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        ll x; scanf("%lld", &x);
        Insert(x);
    }
    cout << getMx() << endl;
    return 0;
}

欧拉筛

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

const int N=1e7+5;

int vis[N],prime[N],countPrime;
void getPrime() {
    for (int i=2;i<N;i++) {
        if (!vis[i]) prime[++countPrime]=i;
        for (int j=1;j<=countPrime;j++) {
            if (i*prime[j]>=N) break;
            vis[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
}

int main() {
    getPrime();
    printf("%d",countPrime);
    return 0;
}

Min_25筛

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 2e5 + 5;

int vis[N], pr[N], countPr;

void getPrime() {
    for (int i = 2; i < N; i++) {
        if (!vis[i]) pr[++countPr] = i;
        for (int j = 1; j <= countPr; j++) {
            if (i * pr[j] >= N) break;
            vis[i * pr[j]] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}

LL g[N], ans;

LL sum[N], n, w[N];

int id1[N], id2[N], m;

int sqr, K, T;

int bin(int x, int p) {
    int res = 1;
    for (int b = x; p; p >>= 1, b = 1ll * b * b % K)
        if (p & 1) res = 1ll * res * b % K;
    return res;
}

int main() {
    cin >> T;
    getPrime();
    for (int i = 1; i <= countPr; i++) sum[i] = sum[i - 1] + pr[i];
    while (T--) {
        scanf("%lld %d", &n, &K); 
        n++;
        sqr = sqrt(n);
        m = 0;
        int inv2 = bin(2, K - 2);
        for (LL i = 1, j; i <= n; i = j + 1) {
            j = n / (n / i); w[++m] = n / i;
            if (w[m] <= sqr) id1[w[m]] = m;
            else id2[n / w[m]] = m;
            g[m] =(1ll * (1 + w[m]) % K * w[m] % K * inv2 - 1) % K;
        }

        int tot = 0;
        while (1ll * pr[tot] * pr[tot] <= n) tot++;
        tot--;
        clock_t st = clock();
        int cc = 0;
        LL k;
        for (int j = 1; j <= tot; ++j) {
            for (int i = 1; i <= m && 1ll * pr[j] * pr[j] <= w[i]; ++i) {
                cc++;
                k = w[i] / pr[j];
                if (k <= sqr) k = id1[k];
                else k = id2[n / k];
                g[i] = g[i] - 1ll * pr[j] * (g[k] - sum[j - 1]) ;
            }
        }
        ans = (1ll * g[1] % K + ((n + 2) % K) * ((n - 1) % K) % K * inv2 % K - 4 + K) % K;
        printf("%d\n",ans);
    }
    return 0;
}

线性求逆元

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

const int N=3e6+5;

int inv[N],n,p;

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

int main() {
    cin>>n>>p;
    getInv(n);
    for (int i=1;i<=n;i++)
        printf("%d\n",inv[i]);
}

O(n)预处理O(1)求组合数

int fac[N], ifac[N];

void init() {
    fac[0] = ifac[0] = fac[1] = ifac[1] = 1;
    for (int i = 2; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
    for (int i = 2; i < N; i++) ifac[i] = 1ll * (MOD - MOD / i) * ifac[MOD % i] % MOD;
    for (int i = 2; i < N; i++) ifac[i] = 1ll * ifac[i - 1] * ifac[i] % MOD;
}

int C(int n, int m) {
    if (n < m) return 0;
    return 1ll * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}

CRT中国剩余定理

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

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    // ax + by = gcd(a,b)
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);  // ax1 + by1 = bx2 + (a - b(a/b))y2
    y -= (a / b) * x;              // ax1 + by1 = ay2 + b(x2 - (a/b)y2)
    return d;
}

long long crt(vector<ll> &m, vector<ll> &a)
{
    // x = m mod a
    ll m1 = m[0], a1 = a[0];
    for (int i = 1; i < m.size(); i++)
    {
        // a1y1 - a2y2 = m1 - m2
        ll m2 = m[i], a2 = a[i];
        ll g = gcd(a1, a2);
        if ((m2 - m1) % g)
            return -1;
        ll y1, y2;
        exgcd(a1, a2, y1, y2);
        y1 *= (m1 - m2) / g;
        y1 = ((y1 % (a2 / g)) + a2 / g) % (a2 / g);
        // x = (m1 + a1y10) + tLCM
        m1 -= a1 * y1;
        a1 = (a1 / gcd(a1, a2)) * a2;
    }
    m1 = ((m1 % a1) + a1) % a1;  //最小正整数解
    if(m1 <= 0)
        m1 += a1;
    return m1;
}

Miller-Rabin

long long mult_mod(long long a,long long b,long long c)
{
    a%=c;
    b%=c;
    long long ret=0;
    while(b)
    {
        if(b&1){ret+=a;ret%=c;}
        a<<=1;
        if(a>=c)a%=c;
        b>>=1;
    }
    return ret;
}

//计算  x^n %c
long long pow_mod(long long x,long long n,long long mod)//x^n%c
{
    if(n==1)return x%mod;
    x%=mod;
    long long tmp=x;
    long long ret=1;
    while(n)
    {
        if(n&1) ret=mult_mod(ret,tmp,mod);
        tmp=mult_mod(tmp,tmp,mod);
        n>>=1;
    }
    return ret;
}


//以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
//一定是合数返回true,不一定返回false
bool check(long long a,long long n,long long x,long long t)
{
    long long ret=pow_mod(a,x,n);
    long long last=ret;
    for(int i=1;i<=t;i++)
    {
        ret=mult_mod(ret,ret,n);
        if(ret==1&&last!=1&&last!=n-1) return true;//合数
        last=ret;
    }
    if(ret!=1) return true;
    return false;
}
// Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数，但概率极小)
//合数返回false;
bool Miller_Rabin(long long n)
{
    if(n<2)return false;
    if(n==2)return true;
    if((n&1)==0) return false;//偶数
    long long x=n-1;
    long long t=0;
    while((x&1)==0){x>>=1;t++;}
    for(int i=0;i<S;i++)
    {
        long long a=rand()%(n-1)+1;//rand()需要stdlib.h头文件
        if(check(a,n,x,t))
            return false;//合数
    }
    return true;
}

二次剩余

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll w;
struct num{
    ll x,y;
};

num mul(num a,num b,ll p)
{
    num ans={0,0};
    ans.x=((a.x*b.x%p+a.y*b.y%p*w%p)%p+p)%p;
    ans.y=((a.x*b.y%p+a.y*b.x%p)%p+p)%p;
    return ans;
}

ll powwR(ll a,ll b,ll p){
    ll ans=1;
    while(b){
        if(b&1)ans=1ll*ans%p*a%p;
        a=a%p*a%p;
        b>>=1;
    }
    return ans%p;
}
ll powwi(num a,ll b,ll p){
    num ans={1,0};
    while(b){
        if(b&1)ans=mul(ans,a,p);
        a=mul(a,a,p);
        b>>=1;
    }
    return ans.x%p;
}

ll solve(ll n,ll p)
{
    n%=p;
    if(p==2)return n;
    if(powwR(n,(p-1)/2,p)==p-1)return -1;//不存在
    ll a;
    while(1)
    {
        a=rand()%p;
        w=((a*a%p-n)%p+p)%p;
        if(powwR(w,(p-1)/2,p)==p-1)break;
    }
    num x={a,1};
    return powwi(x,(p+1)/2,p);
}

int main()
{
    srand(time(0));
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n,p;
        scanf("%lld%lld",&n,&p);
        if(!n){
            printf("0\n");continue;
        }
        ll ans1=solve(n,p),ans2;
        if(ans1==-1)printf("Hola!\n");
        else
        {
            ans2=p-ans1;
            if(ans1>ans2)swap(ans1,ans2);
            if(ans1==ans2)printf("%lld\n",ans1);
            else printf("%lld %lld\n",ans1,ans2);
        }
    }
}

行列式计算/生成树计数

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

const int MOD=998244353,N=1e2+5;

LL a[N][N],ans;

int T,n,m,sign;

int M[N][N],M2[N][N];

struct Edge{
    int u,v,w;
}e[10005];

LL detVal(int n){
    sign=0;LL ans=1;
    for(int i=1;i<=n;i++){
        for(int j=i+1; j<=n; j++){//当前之后的每一行第一个数要转化成0
            int x=i,y=j;
            while(a[y][i]){//利用gcd的方法，不停地进行辗转相除
                LL t=a[x][i]/a[y][i];
                for(int k=i; k<n; k++)
                    a[x][k]=(a[x][k]-a[y][k]*t)%MOD;
                swap(x, y);
            }
            if(x!=i){//奇数次交换，则D=-D'整行交换
                for(int k=1;k<n;k++)
                    swap(a[i][k],a[x][k]);
                sign^= 1;//行列式*-1
            }
        }
        if(!a[i][i]){//斜对角中有一个0，则结果为0
            return 0;
        }
        else ans=ans*a[i][i]%MOD;
    }
    if(sign!=0) ans*=-1;
    if(ans<0) ans+=MOD;
    return ans;
}

int main(){
    cin>>T;
    while(T--) {
        scanf("%d%d",&n,&m);
        memset(M,0,sizeof(M));
        for (int i=1;i<=m;i++) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            e[i].u=u;e[i].v=v;e[i].w=w;
        }
        memset(a,0,sizeof(a));
        for (int k=1;k<=m;k++) {
            int i=e[k].u,j=e[k].v;
            a[i][i]++;a[j][j]++;
            a[i][j]--;a[j][i]--;
        }
        LL tot=detVal(n);
        tot=bin(tot,MOD-2);
        ans=0;
        for (int i=0;i<=30;i++)
        {
            memset(M2,0,sizeof(M2));
            memset(a,0,sizeof(a));
            for (int p=1;p<=m;p++) {
                if (e[p].w&(1<<i)) {
                    int j=e[p].u,k=e[p].v;
                    a[j][j]++;a[k][k]++;
                    a[j][k]--;a[k][j]--;
                }
            }
            LL cur=detVal(n-1);
            ans=(ans+(1ll*cur*tot)%M(1<<i))%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

点和向量旋转

//任意点(x,y)，绕一个坐标点(rx0,ry0)逆时针旋转a角度后的新的坐标设为(x0, y0)，有公式：
// x0= (x-rx0)*cos(a)-(y-ry0)*sin(a)+rx0 ;
// y0= (x-rx0)*sin(a)+(y-ry0)*cos(a)+ry0 ;

//任意向量(x,y)，绕一个坐标点(rx0,ry0)逆时针旋转a角度后的新的向量设为(x0, y0)，有公式：
// x0= x*cos(a)-y*sin(a);
// y0= x*sin(a)+y*cos(a);
void Rotate(double &x,double &y,double &vx,double &vy,double x0,double y0,double a)
{
    double x_,vx_,y_,vy_;
    x_=(x-x0)*cos(a)-(y-y0)*sin(a)+x0;
    vx_=vx*cos(a)-vy*sin(a);
    y_=(x-x0)*sin(a)+(y-y0)*cos(a)+y0;
    vy_=vx*sin(a)+vy*cos(a);
    x=x_,y=y_,vx=vx_,vy=vy_;
}

求直线交点、中垂线

#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
using namespace std;

const int MAXN=2e3+5;
const double eps=1e-6;

class Point {
public:
    double x,y;
    Point(double a=0,double b=0):x(a),y(b){}
};
class Line {
public:
    bool ifk;
    double k,b;
    //求过两点的直线
    void mkline (Point A,Point B) {
        ifk=true;k=b=0;
        if (A.x==B.x) {
            ifk=0;
            b=A.x;
        } else {
            if (A.y==B.y) {
                k=0;
                // b=(A.x+B.x)/2;
                b=A.y;
            } else {
                k=(B.y-A.y)/(B.x-A.x);
                b=A.y-k*A.x;
            }
        }
    }
    //求两点中垂线
    void mkbisector (Point A,Point B) {
        ifk=true;k=b=0;
        if (A.x==B.x) {
            k=0;
            b=(A.y+B.y)/2;
        } else if (A.y==B.y) {
                ifk=0;
                b=(A.x+B.x)/2;
            } else {
                k=-1/(B.y-A.y)*(B.x-A.x);
                b=(A.y+B.y)/2-k*(A.x+B.x)/2;
            }
    }
    bool operator == (Line &T) {
        return (ifk==T.ifk) && fabs(k-T.k)<eps && fabs(b-T.b)<eps;
    }
};
//求两直线交点
struct Intersection {
    bool parallel,coincide;
    double x,y;
    bool operator < (const Intersection &T) const {
        if (fabs(x-T.x)>eps) return x<T.x;
        else if (fabs(y-T.y)>eps) return y<T.y;
        else return 0;
    }
};
Intersection getIntersection (Line A,Line B) {
    Intersection ans;
    ans.parallel=ans.coincide=0;
    ans.x=ans.y=0;
    if (A==B) {
        ans.coincide=1;
        return ans;
    }
    if (!A.ifk && !B.ifk || A.ifk && B.ifk && fabs(A.k-B.k)<eps) {
        ans.parallel=1;
        return ans;
    }
    if (!A.ifk && B.ifk) return getIntersection(B,A);
    if (A.ifk && !B.ifk) {
        ans.x=B.b;
        ans.y=A.k*ans.x+A.b;
    } else {
        ans.x=(B.b-A.b)/(A.k-B.k);
        ans.y=A.k*ans.x+A.b;
    }
    return ans;
}

Point p[MAXN];

Line l[MAXN];

int n,m,ans;

map<Intersection,int>CNT;

int main()
{
    cin>>n;
    Point ori(0,0);
    for (int i=1;i<=n;i++)
    {
        cin>>p[i].x>>p[i].y;
        l[i].mkbisector(ori,p[i]);
    }
    ans=1;
    for (int i=1;i<=n-1;i++)
    {
        CNT.clear();
        for (int j=i+1;j<=n;j++)
        {
            Intersection inter=getIntersection(l[i],l[j]);
            if (!inter.coincide && !inter.parallel) CNT[inter]++;
        }
        for (auto it:CNT) ans=max(ans,it.second+1);
    }
    printf("%d\n",ans);
    return 0;
}

算法

CDQ分治

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

const int N=1e5+5;

struct BIT{
    int tr[N];
    int lowbit(int x){ return x&(-x); }
    void clr(int x){
        while(x<N)
        {
            tr[x]=0;
            x+=lowbit(x);
        }
    }
    void add(int v,int x){
        while(x<N)
        {
            tr[x]+=v;
            x+=lowbit(x);
        }
    }
    int sum(int x){
        int sum=0;
        while(x>0)
        {
            sum+=tr[x];
            x-=lowbit(x);
        }
        return sum;
    }
}bit;

struct node{
    int id,x,y,z;
    bool operator==(node &t){
        return x==t.x && y==t.y && z==t.z;
    }
}A[N],tmp[N];

int n,k,ans[N],cnt[N];

void CDQ(int l,int r)
{
    if (l==r) return;
    int mid=(l+r)>>1;
    CDQ(l,mid);
    CDQ(mid+1,r);
    int p1=l,p2=mid+1,pt=l;
    while(p1!=mid+1 || p2!=r+1)
    {
        if (p1==mid+1 || A[p2].y<A[p1].y && p2!=r+1)
        {
            ans[A[p2].id]+=bit.sum(A[p2].z);
            tmp[pt++]=A[p2];
            p2++;
        }
        else
        {
            bit.add(1,A[p1].z);
            tmp[pt++]=A[p1];
            p1++;
        }
    }
    for (int i=l;i<=mid;i++) bit.clr(A[i].z);
    for (int i=l;i<=r;i++) A[i]=tmp[i];
}

bool cmp(node &a,node &b){
    if (a.x==b.x && a.y==b.y)
        return a.z<b.z;
    else if(a.x==b.x) return a.y<b.y;
    else return a.x<b.x;
}

int main()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&A[i].x,&A[i].y,&A[i].z);
        A[i].id=i;
    }
    sort(A+1,A+1+n,cmp);
    int same=0;
    for (int i=n;i>=2;i--)
    {
        if (A[i]==A[i-1]) ans[A[i-1].id]+=++same;
        else same=0;
    }
    CDQ(1,n);
    for (int i=1;i<=n;i++) cnt[ans[i]]++;
    for (int i=0;i<n;i++) printf("%d\n",cnt[i]);
    return 0;
}

最长递增子序列(LIS)

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

const int N=1000+5,INF=0x3f3f3f3f;

int T,n,m,A[N],dp[N],ans;

int check(int l,int r)
{
    for (int i=l;i<r;i++)
    {
        int j=lower_bound(dp,dp+n,A[i])-dp;
        dp[j]=A[i];
    }
    return n-(lower_bound(dp,dp+n,INF)-dp);
}
int main()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
        scanf("%d",&A[i]);
        A[n+i]=A[i];
    }
    ans=INF;
    for (int k=0;k<n;k++)
    {
        memset(dp,INF,sizeof(dp));
        ans=min(ans,check(k,k+n));
    }
    cout<<ans;
    return 0;
}

带修莫队

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 2e5 + 5, M = 1e6 + 5;

int n, m;

int a[N], cnt[M], cntq, cntp, pos[N], ans[N], now;

char op;

struct Query{
    int l, r, t, id;
    bool operator < (Query &Q) {
        if (pos[l] != pos[Q.l]) return l < Q.l;
        if (pos[r] != pos[Q.r]) return r < Q.r;
        return t < Q.t;
    }
}q[N];

struct Modify{
    int pos, bef, aft;
}p[N];

void inc(int x) {
    if (++cnt[x] == 1) now++;
}

void del(int x) {
    if (!(--cnt[x])) now--;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1, u, v; i <= m; i++) {
        op = getchar();
        while(op != 'Q' && op != 'R') op = getchar();
        scanf("%d%d", &u, &v);
        if (op == 'Q') {
            cntq++;
            q[cntq].l = u;
            q[cntq].r = v;
            q[cntq].t = cntp;
            q[cntq].id = cntq;
        } else {
            cntp++;
            p[cntp].pos = u;
            p[cntp].bef = a[u];
            p[cntp].aft = v;
            a[u] = v;
        }
    }
    LL block = pow(1ll * n, 2.0 / 3.0);
    for (int i = 1; i <= n; i++) pos[i] = i / block;
    sort(q + 1, q + 1 + cntq);
    int l = 1, r = 0, t = cntp;
    for (int i = 1; i <= cntq; i++) {
        int nl = q[i].l, nr = q[i].r, nt = q[i].t;
        while(t < nt) {
            t++;
            int pos = p[t].pos, bef = p[t].bef, aft = p[t].aft;
            if (pos >= l && pos <= r) {
                cnt[bef]--;
                if (cnt[bef] == 0) now--;
                cnt[aft]++;
                if (cnt[aft] == 1) now++;
            }
            a[pos] = aft;
        }
        while(t > nt) {
            int pos = p[t].pos, bef = p[t].bef, aft = p[t].aft;
            if (pos >= l && pos <= r) {
                cnt[aft]--;
                if (cnt[aft] == 0) now--;
                cnt[bef]++;
                if (cnt[bef] == 1) now++;
            }
            a[pos] = bef;
            t--;
        }
        while(l < nl) del(a[l++]);
        while(l > nl) inc(a[--l]);
        while(r < nr) inc(a[++r]);
        while(r > nr) del(a[r--]);
        ans[q[i].id] = now;
    }
    for (int i = 1; i <= cntq; i++) printf("%d\n", ans[i]);
    return 0;
}

威佐夫博弈

ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，...,n 方括号表示取整函数)

树上莫队（带修）

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << " "
#define debugl(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long ll;

const int N = 1e5 + 5;

int n, M, Q, v[N], w[N], c[N];

int f[N], g[N], id[N << 1], pos[N << 1], IDX, TIME, CNT;

int dep[N], pre[N][25], pow_2[25], cnt[N];

bool vis[N];

ll ans, aans[N];

struct Modify{
    int pre, aft, pos;
}m[N];

struct Query{
    int x, y, t, id;
}q[N];

bool cmp(Query Q_, Query Q) {
    if (pos[Q_.x] != pos[Q.x]) return pos[Q_.x] < pos[Q.x];
    if (pos[Q_.y] != pos[Q.y]) return pos[Q_.y] < pos[Q.y];
    return Q_.t < Q.t;
}

vector<int> G[N];

void dfs(int x, int ff) {
    f[x] = ++IDX;
    id[IDX] = x;
    for (int to : G[x]) {
        if (to == ff) continue;
        dep[to] = dep[x] + 1;
        pre[to][0] = x;
        dfs(to, x);
    }
    g[x] = ++IDX;
    id[IDX] = x;
}

int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int gap = dep[x] - dep[y];
    for (int i = 20; i >= 0; i--) {
        if (gap >= pow_2[i]) {
            gap -= pow_2[i];
            x = pre[x][i];
        }
    }
    if (x == y) return x;
    for (int i = 20; i >= 0; i--) {
        if (pre[x][i] != pre[y][i]) {
            x = pre[x][i];
            y = pre[y][i];
        }
    }
    return pre[x][0];
}

void add(int pos) {
    vis[pos] ^= 1;
    if (vis[pos]) {
        cnt[c[pos]]++;
        ans = ans + 1ll * w[cnt[c[pos]]] * v[c[pos]];
    }
    else {
        ans = ans - 1ll * w[cnt[c[pos]]] * v[c[pos]];
        cnt[c[pos]]--;
    }
}

int main() {
    cin >> n >> M >> Q;
    for (int i = 1; i <= M; i++) scanf("%d", &v[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    pow_2[0] = 1;
    for (int i = 1; i <= 20; i++) pow_2[i] = pow_2[i - 1] * 2;
    dep[1] = 1;
    dfs(1, -1);
    int block = pow(IDX, 2.0 / 3);
    for (int i = 1; i <= IDX; i++) {
        pos[i] = (i - 1) / block + 1;
    }
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= n; j++) pre[j][i] = pre[pre[j][i - 1]][i - 1];
    }
    for (int i = 1; i <= Q; i++) {
        int t, x, y;
        scanf("%d %d %d", &t, &x, &y);
        if (t == 0) {
            m[++TIME] = {c[x], y, x};
            c[x] = y;
        } else {
            if (f[x] > f[y]) swap(x, y);
            q[++CNT] = {LCA(x, y) == x ? f[x] : g[x], f[y], TIME, CNT};
        }
    }
    sort(q + 1, q + 1 + CNT, cmp);
    int l = 0, r = 0, t = TIME;
    for (int i = 1; i <= CNT; i++) {
        while(t < q[i].t) {
            t++;
            if (vis[m[t].pos]) {
                int pc = m[t].pre;
                int ac = m[t].aft;
                ans -= 1ll * v[pc] * w[cnt[pc]];
                cnt[pc]--;
                cnt[ac]++;
                ans += 1ll * v[ac] * w[cnt[ac]];
            }
            c[m[t].pos] = m[t].aft;
        }
        while(t > q[i].t) {
            if (vis[m[t].pos]) {
                int pc = m[t].pre;
                int ac = m[t].aft;
                ans -= 1ll * v[ac] * w[cnt[ac]];
                cnt[ac]--;
                cnt[pc]++;
                ans += 1ll * v[pc] * w[cnt[pc]];
            }
            c[m[t].pos] = m[t].pre;
            t--;
        }
        while(r < q[i].y) r++, add(id[r]);
        while(l > q[i].x) l--, add(id[l]);
        while(r > q[i].y) add(id[r]), r--;
        while(l < q[i].x) add(id[l]), l++;
        int lca = LCA(id[l], id[r]);
        if (lca != id[l] && lca != id[r]) {
            add(lca);
            aans[q[i].id] = ans;
            add(lca);
        } else aans[q[i].id] = ans;
    }
    for (int i = 1; i <= CNT; i++) printf("%lld\n", aans[i]);
    return 0;
}

异或最小生成树

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int INF=0x3f3f3f3f;

int l[N<<5],r[N<<5];

struct Edge{
    int t,w;
};

int root,num;

vector<Edge>G[N];

vector<int>P;

int u,v,w,n;

ll tot;

void dfs(int x,int fa,int now) {
    P.push_back(now);
    for (auto to:G[x]) {
        if (to.t!=fa)
            dfs(to.t,x,now^to.w);
    }
}
void MakeTrie(int subroot,int check,int x) {
    if (check==0) return;
    if ((x&check)==0) {
        if (l[subroot]==0) l[subroot]=++num;
        MakeTrie(l[subroot],check>>1,x);
    }
    else {
        if (r[subroot]==0) r[subroot]=++num;
        MakeTrie(r[subroot],check>>1,x);
    }
}
ll dfs3(int a,int b,int check) {
    if (!a || !b) return INF;
    if (check==0) return 0;
    ll t1,t2;
    t1=min(dfs3(l[a],l[b],check>>1),dfs3(r[a],r[b],check>>1));
    if (t1==INF)
        t2=check+min(dfs3(l[a],r[b],check>>1),dfs3(r[a],l[b],check>>1));
    else t2=INF;
    return min(t1,t2);
}
ll dfs2(int subroot,int check) {
    ll ret=0;
    if (l[subroot]) ret+=dfs2(l[subroot],check>>1);
    if (r[subroot]) ret+=dfs2(r[subroot],check>>1);
    if (l[subroot] && r[subroot]) {
        int t1=l[subroot],t2=r[subroot];
        ret+=check+dfs3(t1,t2,check>>1);
    }
    return ret;
}

int main() {
    cin>>n;
    for (int i=1;i<=n-1;i++) {
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    dfs(0,-1,0);
    sort(P.begin(),P.end());
    P.erase(unique(P.begin(),P.end()),P.end());
    for (auto x:P) {
        MakeTrie(0,1<<30,x);
    }
    printf("%lld\n",dfs2(0,1<<30));
    return 0;
}

字符串

KMP

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

const int N=1e5+5;

struct KMP{
    int nxt[N];
    void getNext(string &t) {
        nxt[0]=-1;
        for (int i=1,j=-1;i<=t.length();i++) {
            while(j!=-1 && t[i-1]!=t[j]) j=nxt[j];
            nxt[i]=++j;
        }
    }
    void getAns(string &s,string &t) {
        int len=t.length();
        for (int i=0,j=0;i<s.length();) {
            if (j==-1 || s[i]==t[j]) i++,j++;
            else j=nxt[j];
            if (j==len) printf("%d\n",i-j+1),j=nxt[j];
        }
    }
}kmp;

string s,t;

int main() {
    cin>>s;
    cin>>t;
    kmp.getNext(t);
    kmp.getAns(s,t);
    for (int i=1;i<=t.length();i++) printf("%d ",kmp.nxt[i]);
}

后缀数组SA

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int n;
char S[MAXN];
int s[MAXN];
int last[2];
//char s[MAXN];
struct SA {
    int sa[MAXN], ra[MAXN], height[MAXN];
    int t1[MAXN], t2[MAXN], c[MAXN];
    void build(int *str, int n, int m) {
        str[n] = 0;
        n++;
        int i, j, p, *x = t1, *y = t2;
        for (i = 0; i < m; i++) c[i] = 0;
        for (i = 0; i < n; i++) c[x[i] = str[i]]++;
        for (i = 1; i < m; i++) c[i] += c[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
        for (j = 1; j <= n; j <<= 1) {
            p = 0;
            for (i = n - j; i < n; i++) y[p++] = i;
            for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
            for (i = 0; i < m; i++) c[i] = 0;
            for (i = 0; i < n; i++) c[x[y[i]]]++;
            for (i = 1; i < m; i++) c[i] += c[i - 1];
            for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1;
            x[sa[0]] = 0;
            for (i = 1; i < n; i++)
                x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? p - 1 : p++;
            if (p >= n) break;
            m = p;
        }
        n--;
        for (int i = 0; i <= n; i++) ra[sa[i]] = i;
        for (int i = 0, j = 0, k = 0; i <= n; i++) {
            if (k) k--;
            j = sa[ra[i] - 1];
            while (str[i + k] == str[j + k]) k++;
            height[ra[i]] = k;
        }
        st_init(height, n);
    }
    int lg[MAXN], table[23][MAXN];
    void st_init(int *arr, int n) {
        if (!lg[0]) {
            lg[0] = -1;
            for (int i = 1; i < MAXN; i++)
                lg[i] = lg[i / 2] + 1;
        }
        for (int i = 1; i <= n; ++i)
            table[0][i] = arr[i];
        for (int i = 1; i <= lg[n]; ++i)
            for (int j = 1; j <= n; ++j)
                if (j + (1 << i) - 1 <= n)
                    table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
    }
    int lcp(int l, int r) {
        l = ra[l], r = ra[r];
        if (l > r) swap(l, r);
        ++l;
        int t = lg[r - l + 1];
        return min(table[t][l], table[t][r - (1 << t) + 1]);
    }
} sa;

/*bool cmp(int i, int j) {
    if (dis[i] != dis[j]) return dis[i] < dis[j];
    if (i + dis[i] > n) return true;
    if (j + dis[j] > n) return false;
    int lcp = sa.lcp(i + dis[i], j + dis[j]);
    return a[i + lcp + dis[i]] < a[j + lcp + dis[j]];
}*/

int main(){
    while(scanf("%d",&n)!=-1)
    {
        scanf("%s",S);
        last[0]=last[1]=0;
        s[n]=n+1;
        for (int i=n-1;i>=0;i--)
        {
            int now= S[i]=='a' ? 0 : 1;
            if (last[now]==0) s[i]=n;
            else s[i]=(last[now]-i);
            last[now]=i;
        }
        n++;
        sa.build(s,n,n+2);
        for(int i = n-1;i >=1 ;i--)
            printf("%d ",sa.sa[i]+1);
        printf("\n");
    }
    return 0;
}