Mini Template

lowbit · 2023-11-15 15:22:12 · 个人记录

RMQ

for(int j=1; j <= __lg(n); ++j) {
    for(int i=1; i+(1<<j)-1 <= n; ++i) {
        f[i][j] = max(f[i][j-1], f[i+(1<<j-1)][j-1]);
    }
}

LCA

void dfs(int u, int fa) {
    f[u][0]=fa, dep[u] = dep[fa]+1;
    for(int i=1; 1<<i <= dep[u]; ++i) f[u][i] = f[f[u][i-1]][i-1];
    for(int i=h[u]; i; i=e[i].n) {
        int v=e[i].v;
        if(v == fa) continue;
        dfs(v, u);
    }
}
int lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    per(i, __lg(n), 0) if(dep[x]-(1<<i) >= dep[y]) x = f[x][i];
    if(x == y) return x;
    per(i, __lg(n), 0) {
        if(f[x][i] != f[y][i]) x=f[x][i], y=f[y][i];
    }
    return f[x][0];
}

Dij

void dijkstra() {
    priority_queue <pair<int, int>> q;
    for(int i=1; i <= n; ++i) dis[i] = INF;
    dis[s] = 0;
    q.push(make_pair(0, s));
    while(!q.empty()) {
        int u = q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i=h[u]; i; i=e[i].n) {
            int v=e[i].v, w=e[i].w;
            if(dis[u]+w < dis[v]) dis[v] = dis[u]+w, q.push(make_pair(-dis[v], v));
        }
    }
}

SPFA

void SPFA() {
    queue <int> q;
    for(int i=1; i <= n; ++i) dis[i] = INF;
    dis[s] = 0, vis[s] = 1;
    q.push(s);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i=h[u]; i; i=e[i].n) {
            int v=e[i].v, w=e[i].w;
            if(dis[u]+w < dis[v]) {
                dis[v] = dis[u]+w;
                if(!vis[v]) q.push(v), vis[v] = 1;
            }
        }
    }
}

Segtree 1

void pushup(int p) {
    sum[p] = sum[p<<1]+sum[p<<1|1];
}
void build(int p, int l, int r) {
    len[p] = r-l+1;
    if(l == r) {
        return ;
    }
    int mid=l+r>>1;
    build(p<<1, l, mid), build(p<<1|1, mid+1, r);
    pushup(p);
}
void pushdown(int p) {
    if(!add[p]) return ;
    sum[p<<1] += add[p] * len[p<<1];
    sum[p<<1|1] += add[p] * len[p<<1|1];
    add[p<<1] += add[p], add[p<<1|1] += add[p];
    add[p] = 0;
}
void modify(int p, int l, int r, int x, int y, ll k) {
    if(l >= x && r <= y) {
        sum[p] += k * len[p];
        add[p] += k;
        return ;
    }
    pushdown(p);
    int mid=l+r>>1;
    if(x <= mid) modify(p<<1, l, mid, x, y, k);
    if(y > mid) modify(p<<1|1, mid+1, r, x, y, k);
    pushup(p);
}
ll ask(int p, int l, int r, int x, int y) {
    if(l >= x && r <= y) return sum[p];
    ll s=0;
    pushdown(p);
    int mid=l+r>>1;
    if(x <= mid) s += ask(p<<1, l, mid, x, y);
    if(y > mid) s += ask(p<<1|1, mid+1, r, x, y);
    return s;
}

LIS

f[0] = INF;
rep(i, 1, n) {
    int k = lower_bound(f+1, f+ans+1, a[i]) - f;
    f[k] = a[i];
    ans= max(ans, k);
}