小鸟游六花

vanishment this world

发表于 更新于

一、模板

0、关于代码的一些说明

对于第二个计算low值的地方 low[u] = min(low[u], dfn[v]), 对于新手可能会不小心写成low[u] = min(low[u], low[v]), 这样是不对的，考虑如下边构成的(无/有)向图:

1
2
3
4
5
1 3
2 3
3 4
3 5
4 5

如果写成low[u] = min(low[u], low[v])，判断割点的时候就会出错。

第二个说明点是，我们在求桥(割边)时，在有平行边的时候使用父节点号来判断反向边会出错，这里建议使用反向边判断：if (i == (fa ^ 1)) continue;。

1、Tarjan 求无向图的桥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int maxn = 200100;
int dfn[maxn], low[maxn], tdf = 0;
struct Edge {
    int next, to;
} edges[maxn * 2];
int heads[maxn], pos = 1;

void addEdge(int a, int b) {
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    heads[a] = pos;
}

// Tarjan 求无向图的桥
vector<vector<int>> ans;
void tarjan(int u, int fa) {
    low[u] = dfn[u] = ++tdf;
    for (int i = heads[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (i == (fa ^ 1)) continue;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                // bridge u - v
                ans.push_back({u, v});
            }
        } else low[u] = min(low[u], dfn[v]);
    }
}

2、Tarjan无向图求割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int maxn = 100100;
int dfn[maxn], low[maxn], tdf = 0;
int heads[maxn], pos = 0;
struct Edge {
    int next, to;
} edges[maxn * 2];

void addEdge(int a, int b) {
    //printf("edge: %d => %d\n", a, b);
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    heads[a] = pos;
}
// 无向图求割点(割点无需判断反向边)
int cut[maxn];
void tarjan1(int u, bool root) {
    low[u] = dfn[u] = ++tdf;
    int cnt = 0;
    for (int i = heads[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (!dfn[v]) {
            tarjan1(v, false);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u])
                if (!root || ++cnt > 1) cut[u] = 1;
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

3、Tarjan无向图V-DCC缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int maxn = 100100;
struct Edge {
    int next, to;
} edges[maxn * 2];
int heads[maxn], pos = 1;

void addEdge(int a, int b) {
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    heads[a] = pos;
}

// 无向图V-DCC
int dfn[maxn], low[maxn], tdf = 0;
int v_dcc_stk[maxn], v_dcc_sp = -1, cut[maxn];
vector<int> v_dcc_set[maxn];
int v_dcc_cnt = 0;
void tarjan(int u, bool root) {
    low[u] = dfn[u] = ++tdf; v_dcc_stk[++v_dcc_sp] = u;
    int cnt = 0;
    for (int i = heads[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (!dfn[v]) {
            tarjan(v, false);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                if (!root || ++cnt > 1) cut[u] = 1;
                v_dcc_set[v_dcc_cnt].clear();
                while (1) {
                    int z = v_dcc_stk[v_dcc_sp--];
                    v_dcc_set[v_dcc_cnt].push_back(z);
                    if (v == z) break;
                }
                v_dcc_set[v_dcc_cnt++].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

4、Tarjan有向图SCC缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const int maxn = 100010;
int heads[maxn], pos = 1;
struct Edge {
    int next, to;
} edges[maxn * 4];
void addEdge(int a, int b) {
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    heads[a] = pos;
}
// 无向图求SCC
int dfn[maxn], low[maxn], tdf = 0;
int scc_instk[maxn];
int scc_stk[maxn], scc_sp = -1;
int scc[maxn], scc_size[maxn], scc_cnt = 0;
void tarjan(int u) {
    low[u] = dfn[u] = ++tdf;
    scc_stk[++scc_sp] = u, scc_instk[u] = 1;
    for (int i = heads[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (!dfn[v])
            tarjan(v),
            low[u] = min(low[u], low[v]);
        else if(scc_instk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]){
        int v; scc_size[++scc_cnt] = 0;
        do{
            v = scc_stk[scc_sp--];
            scc_instk[v] = 0;
            scc[v] = scc_cnt;
            ++scc_size[scc_cnt];
        }while(u != v);
    }
}

5、Tarjan无向图E-DCC缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

const int maxn = 500100;
int heads[maxn], pos = 1;
struct Edge {
    int next, to;
} edges[1000010 * 4];
void addEdge(int a, int b) {
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    heads[a] = pos;
}
int dfn[maxn], low[maxn], tdf = 0;
int e_dcc[maxn], e_dcc_stk[maxn], e_dcc_cnt = 0, e_dcc_sp = -1;
void tarjan(int u, int fa) {
    low[u] = dfn[u] = ++tdf; e_dcc_stk[++e_dcc_sp] = u;
    for (int i = heads[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (i == (fa ^ 1)) continue;
        if (!dfn[v]) tarjan(v, i), low[u] = min(low[u], low[v]);
        else low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++e_dcc_cnt;
        while (1) {
            int v = e_dcc_stk[e_dcc_sp--];
            e_dcc[v] = e_dcc_cnt;
            if (u == v) break;
        }
    }
}

发表于 更新于

一、算法实现

1、Manacher模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>


using namespace std;
#define N 12001000
// https://www.luogu.com.cn/problem/P3805
char S[N],M[N<<1];
int R[N<<1];
// 返回最长回文串长度, 并在R里存放回文半径
int manacher()
{
    int n = 0;
    for(int i = 0; S[i]; ++i){
        M[n++] = '#';
        M[n++] = S[i];
    }
    if(n == 0) return 0;
    M[n++] = '#';
    M[n] = 0;
    int r=1,c=1,ans = 1;R[0]=1;
    for(int i = 1; i < n; ++i){
        int p = i < r ? min(R[2*c - i], r - i + 1) : 1;
        while(i + p < n && i - p >= 0 && M[i+p] == M[i-p]) ++p;
        R[i] = p;
        ans = max(ans, p);
        if(r < p + i - 1) r = p + i - 1, c = i;
    }
    return ans - 1;
}
int main()
{
    scanf("%s", S);
    printf("%d\n", manacher());
    /*int n = strlen(M);
    for(int i = 0; i < n; ++i) printf("%c ", M[i]);
    puts("");
    for(int i = 0; i < n; ++i) printf("%d ", R[i]);
    puts("");*/
    return 0;
}

发表于 更新于

一、算法实现

1、区间修改求和模板

需要注意的是，懒加载标识再修改的时候需要增加，而不是覆盖： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef long long LLI;
const int maxn = 120015;
const int maxn4 = maxn << 2;

struct SegTree {
    LLI tree[maxn4];
    LLI lazy[maxn4];
    void build() {
        memset(tree, 0, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
    }
    void pushdown(int rt, int s, int t, int mid) {
        tree[rt << 1] += lazy[rt] * (mid - s + 1);
        lazy[rt << 1] += lazy[rt];
        tree[rt << 1 | 1] += lazy[rt] * (t - mid);
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0; // clear lazy-flag
    }
    void range_add(int rt, LLI val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            tree[rt] += (t - s + 1) * val;
            lazy[rt] += val;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) range_add(rt << 1, val, l, r, s, mid);
        if (r > mid) range_add(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
    }
    LLI query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        LLI ans = 0;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans += query(rt << 1, l, r, s, mid);
        if (r > mid) ans += query(rt << 1 | 1, l, r, mid + 1, t);
        return ans;
    }
};

2、区间最值模板(不支持0)

大部分情况，都可以将数据离散化一个不在0的区间内，此时应该减少不必要的判断，避免题目卡时间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const int maxn = 100010;
const int maxn4 = 100010 * 4;

typedef int LLI;
struct SegTree {
    LLI tree[maxn4];
    LLI lazy[maxn4];
    void clear() {
        memset(tree, -1, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
    }
    void pushdown(int rt, int s, int t, int mid) {
        // unsupport zero update!
        if (lazy[rt]) {
            tree[rt << 1] = lazy[rt];
            lazy[rt << 1] = lazy[rt];
            tree[rt << 1 | 1] = lazy[rt];
            lazy[rt << 1 | 1] = lazy[rt];
            lazy[rt] = 0; // clear lazy-flag
        }
    }
    // example: (1,val,l,r,1,N);
    void update(int rt, LLI val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            tree[rt] = val;
            lazy[rt] = val;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) update(rt << 1, val, l, r, s, mid);
        if (r > mid) update(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }
    LLI query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        LLI ans = -1;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans = max(query(rt << 1, l, r, s, mid), ans);
        if (r > mid) ans = max(query(rt << 1 | 1, l, r, mid + 1, t), ans);
        return ans;
    }
};

3、区间最值模板(支持0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const int maxn = 100010;
const int maxn4 = 100010 * 4;

typedef int LLI;
struct SegTree {
    LLI tree[maxn4];
    LLI lazy[maxn4];
    // support zero update!
    bool changed[maxn4];

    void clear() {
        memset(tree, -1, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
        memset(changed, 0, sizeof(changed));
    }
    void pushdown(int rt, int s, int t, int mid) {
        if (changed[rt]) {
            tree[rt << 1] = lazy[rt];
            lazy[rt << 1] = lazy[rt];
            tree[rt << 1 | 1] = lazy[rt];
            lazy[rt << 1 | 1] = lazy[rt];
            lazy[rt] = 0;       // clear lazy-flag
            changed[rt] = 0;    // clear changed-flag
        }
    }
    // example: (1,val,l,r,1,N);
    void update(int rt, LLI val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            tree[rt] = val;
            lazy[rt] = val;
            changed[rt] = 1;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) update(rt << 1, val, l, r, s, mid);
        if (r > mid) update(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }
    LLI query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        LLI ans = -1;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans = max(query(rt << 1, l, r, s, mid), ans);
        if (r > mid) ans = max(query(rt << 1 | 1, l, r, mid + 1, t), ans);
        return ans;
    }
};

4、区间最值模板(同时支持区间修改和区间增加)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// https://www.luogu.com.cn/problem/P1253
// 注意pushdown函数的实现
const int maxn = 1000010;
const int maxn4 = 1000010 * 4;


struct SegTree {
    LLI tree[maxn4];
    LLI lazy[maxn4];
    LLI diff[maxn4];
    // support zero update!
    bool changed[maxn4];

    void clear() {
        memset(tree, 0, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
        memset(diff, 0, sizeof(diff));
        memset(changed, 0, sizeof(changed));
    }
    void pushdown(int rt, int s, int t, int mid) {
        if (changed[rt]) {
            tree[rt << 1] = lazy[rt];
            lazy[rt << 1] = lazy[rt];
            // 不能漏了这里
            diff[rt << 1] = 0;
            changed[rt << 1] = 1;

            tree[rt << 1 | 1] = lazy[rt];
            lazy[rt << 1 | 1] = lazy[rt];
            // 不能漏了这里
            diff[rt << 1 | 1] = 0;
            changed[rt << 1 | 1] = 1;

            lazy[rt] = 0;       // clear lazy-flag
            changed[rt] = 0;    // clear changed-flag
        }
        if (diff[rt]) {
            tree[rt << 1] += diff[rt];
            diff[rt << 1] += diff[rt];
            tree[rt << 1 | 1] += diff[rt];
            diff[rt << 1 | 1] += diff[rt];
            diff[rt] = 0;       // clear diff-flag
        }
    }
    // example: (1,val,l,r,1,N);
    void update(int rt, LLI val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            diff[rt] = 0;
            tree[rt] = val;
            lazy[rt] = val;
            changed[rt] = 1;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) update(rt << 1, val, l, r, s, mid);
        if (r > mid) update(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }
    void range_add(int rt, LLI val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            diff[rt] += val;
            tree[rt] += val;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) range_add(rt << 1, val, l, r, s, mid);
        if (r > mid) range_add(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }
    LLI query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        LLI ans = -9223372036854775807LL;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans = max(query(rt << 1, l, r, s, mid), ans);
        if (r > mid) ans = max(query(rt << 1 | 1, l, r, mid + 1, t), ans);
        return ans;
    }
};

5、区间最值模板(最终版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
template<typename T, int MAX_N>
struct SegTree {
    T tree[MAX_N*4+4];
    T lazy[MAX_N*4+4];
    // support zero update!
    bool changed[MAX_N*4+4];
    void clear() {
        memset(tree, 0, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
        memset(changed, 0, sizeof(changed));
    }
    void pushdown(int rt, int s, int t, int mid) {
        if (changed[rt]) {
            tree[rt << 1] = lazy[rt];
            lazy[rt << 1] = lazy[rt];
            tree[rt << 1 | 1] = lazy[rt];
            lazy[rt << 1 | 1] = lazy[rt];
            lazy[rt] = 0;       // clear lazy-flag
            changed[rt] = 0;    // clear changed-flag
        }
    }
    void update(T val, int l, int r){
        update(1, val, l, r, 1, MAX_N);
    }
    T query(int l, int r){
        return query(1, l, r, 1, MAX_N);
    }
    // example: (1,val,l,r,1,N);
    void update(int rt, T val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            tree[rt] = val;
            lazy[rt] = val;
            changed[rt] = 1;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) update(rt << 1, val, l, r, s, mid);
        if (r > mid) update(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
    }
    T query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        T ans = -1;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans = max(query(rt << 1, l, r, s, mid), ans);
        if (r > mid) ans = max(query(rt << 1 | 1, l, r, mid + 1, t), ans);
        return ans;
    }
};

5、区间修改区间求和(最终版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
template<typename T, int MAX_N>
struct SegTree {
    T tree[MAX_N*4+4];
    T lazy[MAX_N*4+4];
    T diff[MAX_N*4+4];
    // support zero update!
    bool changed[MAX_N*4+4];

    void clear() {
        memset(tree, 0, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
        memset(diff, 0, sizeof(diff));
        memset(changed, 0, sizeof(changed));
    }
    void pushdown(int rt, int s, int t, int mid) {
        if (changed[rt]) {
            tree[rt << 1] = lazy[rt] * (mid - s + 1);
            lazy[rt << 1] = lazy[rt];
            // 不能漏了这里
            diff[rt << 1] = 0;
            changed[rt << 1] = 1;

            tree[rt << 1 | 1] = lazy[rt] * (t - mid);
            lazy[rt << 1 | 1] = lazy[rt];
            // 不能漏了这里
            diff[rt << 1 | 1] = 0;
            changed[rt << 1 | 1] = 1;

            lazy[rt] = 0;       // clear lazy-flag
            changed[rt] = 0;    // clear changed-flag
        }
        if (diff[rt]) {
            tree[rt << 1] += diff[rt] * (mid - s + 1);
            diff[rt << 1] += diff[rt];
            tree[rt << 1 | 1] += diff[rt] * (t - mid);
            diff[rt << 1 | 1] += diff[rt];
            diff[rt] = 0;       // clear diff-flag
        }
    }
    // example: (1,val,l,r,1,N);
    void update(int rt, T val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            diff[rt] = 0;
            tree[rt] = (t - s + 1) * val;;
            lazy[rt] = val;
            changed[rt] = 1;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) update(rt << 1, val, l, r, s, mid);
        if (r > mid) update(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
    }
    void add(int rt, T val, int l, int r, int s, int t) {
        if (l <= s && r >= t) {
            diff[rt] += val;
            tree[rt] += (t - s + 1) * val;;
            return;
        }
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) add(rt << 1, val, l, r, s, mid);
        if (r > mid) add(rt << 1 | 1, val, l, r, mid + 1, t);
        // pushup
        tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
    }
    T query(int rt, int l, int r, int s, int t) {
        if (l <= s && r >= t) return tree[rt];
        T ans = 0;
        int mid = s + ((t - s) >> 1);
        pushdown(rt, s, t, mid);
        if (l <= mid) ans += query(rt << 1, l, r, s, mid);
        if (r > mid) ans += query(rt << 1 | 1, l, r, mid + 1, t);
        return ans;
    }

    void update(T val, int l, int r){
        update(1, val, l, r, 1, MAX_N);
    }
    void add(T val, int l, int r){
        add(1, val, l, r, 1, MAX_N);
    }
    T query(int l, int r){
        return query(1, l, r, 1, MAX_N);
    }
};

0%