int dfn[maxn], low[maxn];
int dft;

void tarjan(int u) {
    dft++;
    dfn[u] = low[u] = dft;

    for (int v: G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (!co[v]) {
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u]==low[u]) {
    if (fa==-1 || low[u]>dfn[f]){
        ...
    }
}

连通分量的求法也有区别，SCC 直接进栈，BCC 需要先标记桥边 ID 再做 flood fill。

有一些东西可以直接在 dfs 树上统计，不用缩点。强连通分量也一样——有些东西在 Tarjan 时可写，就不用二次搜索增加复杂性。

以及，有向图的 Tarjan 序是缩点图反图的一个拓扑序。

图论建模

对不明二元关系特攻。可以转成连通性问题。

KMP

KMP 稍微记一下。不难。

Code

int n; char s[maxn];
int m; char t[maxn];
int p[maxn];
vector<int> ans;

void pre() {
    int j = 0;
    for (int i=2; i<=m; i++) {
        while (t[j+1] != t[i]) {
            j = p[j];
        }
        if (t[j+1] == t[i]) {
            j++;
        }

        p[i] = j;
    }
}

void kmp() {
    int j = 0;
    for (int i=1; i<=n; i++) {
        while (t[j+1] != s[i]) {
            j = p[j];
        }
        if (t[j+1] == s[i]) {
            j++;
        }

        if (j == m) {
            ans.push_back(i - m + 1);
            j = p[j];
        }
    }
}

区间技巧

忽略重复贡献时，考虑给左端点排序，此时可以忽略贡献部分可以表成一个 $(-\infty, \max r]$ 的区间。取每个区间和 $[\max r+1, \infty)$ ，然后更新 $\max r$ 。

二分

灵活选择 mid 的上/下取整。

整体二分

一个大概是紫的技巧。也是与移动有关，不过是单边移动，然后同时处理多个询问。

Code

int cur;
void shift(int d) {
    if (d > cur) {
        for (int i=cur+1, i<=d; i++) {
            add(cur);
        }
    } else {
        for (int i=d+1; i<=cur; i++) {
            del(cur);
        }
    }
}

void solve(int l, int r, const vector<int> items) {
    int mid = (l + r) / 2;
    shift(mid);

    vector<int> lv, rv;
    for (int i: items) {
        if (checkl(i)) { 
            lv.push_back(i);
        } else {
            rv.push_back(i);
        }
    }

    solve(l, ..., lv);
    solve(..., r, rv);
}

若 add 和 del 是 $T_a$ ，check 是 $T_c$ ，则时间为 $T_a n \log n + T_c \log n$ 。

其他 trick

曼哈顿/切比雪夫距离互转。

序列往左加往右加等价于拆成两个子列，翻转一个之后拼起来。

版权所有

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)