这部分介绍了数据结构的综合
包括前置知识，树的dfs序，树的重心
倍增法求LCA等等
然后介绍树上莫队和莫队综合

树有关的算法

树遍历有关的算法

treeAlgo01
treeAlgo02
treeAlgo03

倍增求LCA

LCA

LCA模版题

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
90
91
const int maxn = 50000 + 10;
const int maxt = 20;
int n, m, t;
int T;

// == lca init() ==
int f[maxn][maxt], dist[maxn], dep[maxn];
// == lca finished ==

// == graph ==
int head[maxn], ver[maxn * 2], nxt[maxn * 2], w[maxn * 2];
int tot = 0;

void init() {
    Set(head, 0);
    Set(ver, 0);
    Set(nxt, 0);
    Set(w, 0);
    Set(f, 0);
    Set(dist, 0);
    Set(dep, 0);
    tot = 0;
}
void add(int x, int y, int z) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
    w[tot] = z;
}
// == graph finished ==

// == init lca and bfs() ==
queue<int> que;
void bfs() {
    t = (int)(log(n) / log(2)) + 1;

    que.push(1), dep[1] = 1;
    while (!que.empty()) {
        int x = que.front(); que.pop();
        for(int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if(dep[y]) continue;

            dep[y] = dep[x] + 1;
            f[y][0] = x;
            dist[y] = dist[x] + w[i];
            _rep(k, 1, t) f[y][k] = f[f[y][k - 1]][k - 1];

            que.push(y);
        }
    }
}
// == bfs finished

// == lca ==
int lca(int x, int y) {
    if(dep[x] > dep[y]) swap(x, y);
    _forDown(k, t, 0) if(dep[f[y][k]] >= dep[x]) y = f[y][k];

    if(x == y) return x;

    _forDown(k, t, 0) if(f[x][k] != f[y][k]) {
        x = f[x][k], y = f[y][k];
    }

    return f[x][0];
}
// == lca finished ==


int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    while (T--) {
        init();
        scanf("%d%d", &n, &m);
        _for(i, 1, n) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z);
            add(y, x, z);
        }
        // == input finished ==

        // bfs and lca
        bfs();
        _rep(i, 1, m) {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", dist[x] + dist[y] - 2 * dist[lca(x, y)]);
        }
    }
}

树上莫队

SPOJCount on a tree II
MoAlgoInTree

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
const int maxn = 200200;
int n, m, N;
int a[maxn], buf[maxn];

// == Graph structure ==
int head[maxn], nxt[maxn], ver[maxn];
int tot = 0;
void init() {
    Set(head, 0);
    Set(nxt, 0);
    Set(ver, 0);
    tot = 0;
}

void add(int x, int y) {
    ver[++tot] = y; nxt[tot] = head[x]; head[x] = tot;
}
// == Graph structure finished ==

// == discrete ==
void discrete() {
    sort(buf + 1, buf + 1 + n);
    N = unique(buf + 1, buf + 1 + n) - buf - 1;
    _rep(i, 1, n) a[i] = lower_bound(buf + 1, buf + 1 + N, a[i]) - buf;
}
// == dicrete finsihed ==


// == dfs order and lca ==
int f[maxn][30], dep[maxn];
int h = 0;

int fst[maxn], lst[maxn];
int ord[maxn], dfsn;
void initdfs() {
    Set(dep, 0);
    Set(fst, 0);
    Set(lst, 0);
    Set(ord, 0);
    dfsn = 0;

    dep[1] = 1;
    h = 20 + 5;
}

void dfs(int x) {
    assert(dep[1] == 1);
    ord[++dfsn] = x;
    fst[x] = dfsn;
    for(int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if(dep[y]) continue;

        dep[y] = dep[x] + 1;
        f[y][0] = x;
        _rep(k, 1, h) f[y][k] = f[f[y][k - 1]][k - 1];
        dfs(y);
    }
    ord[++dfsn] = x;
    lst[x] = dfsn;
}

int LCA(int x, int y) {
    if(dep[x] > dep[y]) swap(x, y);
    _forDown(i, h, 0) if(dep[f[y][i]] >= dep[x]) y = f[y][i];

    if(x == y) return x;

    _forDown(i, h, 0) if(f[y][i] != f[x][i]) {
            x = f[x][i], y = f[y][i];
        }
    return f[x][0];
}
// == dfs order and lca finshed ==

// == query and block ==
class Qry {
public:
    int l, r, lca, id;
};
Qry qry[maxn];

int belong[maxn];
int sz, t;

bool cmp(const Qry& a, const Qry& b) {
    if(belong[a.l] ^ belong[b.l]) return belong[a.l] < belong[b.l];
    if(belong[a.l] & 1) return a.r < b.r;
    return a.r > b.r;
}

// [1, dfsn]
void block() {
    sz = sqrt(dfsn);
    t = dfsn / sz;
    _rep(i, 1, t) _rep(k, (i - 1) * sz + 1, i * sz) belong[k] = i;
    if(t * sz < n) {
        t++;
        _rep(k, (t - 1) * sz + 1, n) belong[k] = t;
    }
}

// == query and block finsihed ==

// == Mo algorithm ==
int CNT[maxn];
int visMo[maxn];

void initMo() {
    Set(CNT, 0);
    Set(visMo, 0);
}

inline void work(int pos, int& ans) {
    if(visMo[pos] == 0) if(++CNT[a[pos]] == 1) ans++;
    if(visMo[pos]) if(--CNT[a[pos]] == 0) ans--;
    visMo[pos] ^= 1;
}

int ANS[maxn];
int l = 1, r = 0, res = 0;
void solve() {
    sort(qry + 1, qry + 1 + m, cmp);

    _rep(i, 1, m) {
        int ql = qry[i].l, qr = qry[i].r, qlca = qry[i].lca;
        // printf("%d %d\n", ql, qr);
        while (l < ql) work(ord[l++], res);
        while (l > ql) work(ord[--l], res);
        while (r < qr) work(ord[++r], res);
        while (r > qr) work(ord[r--], res);

        if(qlca) work(qlca, res);
        ANS[qry[i].id] = res;
        if(qlca) work(qlca, res);
    }
}
// == Mo;s algo finished ==

int main() {
    freopen("input.txt", "r", stdin);
    init();

    // == input data ==
    scanf("%d%d", &n, &m);
    _rep(i, 1, n) {
        scanf("%d", &a[i]);
        buf[i] = a[i];
    }
    _for(i, 1, n) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    // == input finished ==

    // == discrete ==
    discrete();
    // == discrete finished ==


    // == get dfs order and lca ==
    initdfs();
    dfs(1);
    // == dfs order finished

    // == block query ==

    // == block query finished ==
    // == check the arr ord[]
    block();

    _rep(i, 1, m) {
        int l, r;
        scanf("%d%d", &l, &r);
        int lca = LCA(l, r);
        //debug(lca);

        if(fst[l] > fst[r]) swap(l, r);
        qry[i].id = i;

        if(l == lca) {
            qry[i].l = fst[l];
            qry[i].r = fst[r];
        }
        else {
            qry[i].l = lst[l];
            qry[i].r = fst[r];
            qry[i].lca = lca;
        }
    }
    // == Mo algorithm ==

    initMo();
    solve();

    _rep(i, 1, m) printf("%d\n", ANS[i]);
}

回滚莫队

BZOJ4241

BZOJ4241-01
BZOJ4241-02

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

const int maxn = 100000 + 10;
const int maxb = 5000;
int n, m, N;

int a[maxn], typ[maxn], inp[maxn];

class Qry {
public:
    int l, r, id;
};
Qry qry[maxn];

// == discrete ==
void discrete() {
    sort(inp + 1, inp + 1 + n);
    N = unique(inp + 1, inp + 1 + n) - inp - 1;
    _rep(i, 1, n) typ[i] = lower_bound(inp + 1, inp + 1 + N, a[i]) - inp;
}
// == discrete finished ==

// == block ==
int bl[maxn], br[maxn];
int belong[maxn];
int sz, t;

void block() {
    sz = sqrt(n);
    t = n / sz;
    _rep(i, 1, t) {
        bl[i] = (i - 1) * sz + 1;
        br[i] = i * sz;

        _rep(k, bl[i], br[i]) belong[k] = i;
    }

    if(t * sz < n) {
        t++;
        bl[t] = (t - 1) * sz + 1;
        br[t] = n;

        _rep(k, bl[t], br[t]) belong[k] = t;
    }
}

bool cmp(const Qry& a, const Qry& b) {
    if(belong[a.l] ^ belong[b.l]) return belong[a.l] < belong[b.l];
    return a.r < b.r;
}
// == block finsihed ==
int cnt[maxn];
llong ANS[maxn];

void initMo() {
    Set(ANS, 0);
    Set(cnt, 0);
}

llong force(int ql, int qr) {
    llong res = 0;
    int tcnt[maxn];

    _rep(i, ql, qr) tcnt[typ[i]] = 0;
    _rep(i, ql, qr) {
        tcnt[typ[i]]++;
        res = max(res, (llong)1 * tcnt[typ[i]] * a[i]);
        //debug(res);
    }
    return res;
}

void solve() {
    sort(qry + 1, qry + 1 + m, cmp);

    int i = 1;
    _rep(k, 1, t) {
        int l = br[k] + 1, r = br[k];
        Set(cnt, 0);
        llong res = 0;

        // brute force for seg in block
        for( ; belong[qry[i].l] == k; i++) {
            int ql = qry[i].l, qr = qry[i].r;

            if(belong[ql] == belong[qr]) {
                llong ans = force(ql, qr);
                ANS[qry[i].id] = ans;
                continue;
            }

            llong fix = 0;
            while (r < qr) {
                r++;
                ++cnt[typ[r]];
                res = max(res, (llong)1 * cnt[typ[r]] * a[r]);
                //debug(res);
            }
            fix = res;

            while (l > ql) {
                l--;
                ++cnt[typ[l]];
                res = max(res, (llong)1 * cnt[typ[l]] * a[l]);
                //debug(res);
            }

            ANS[qry[i].id] = res;
            //debug(res);

            while (l < br[k] + 1) {
                --cnt[typ[l]];
                ++l;
            }

            res = fix;
        }
    }
}


int main() {
    freopen("input.txt", "r", stdin);
    // == input ==
    scanf("%d%d", &n, &m);
    _rep(i, 1, n) {
        scanf("%d", &a[i]);
        inp[i] = a[i];
    }
    _rep(i, 1, m) {
        int _l, _r;
        scanf("%d%d", &_l, &_r);
        qry[i].l = _l;
        qry[i].r = _r;
        qry[i].id = i;
    }
    // == input finished ==

    // == discrete ==
    discrete();
    // == discrete finished ==

    // == block ==
    block();
    // == block finished ==

    // == Mo Algorithm ==
    initMo();
    solve();
    // == Mo Algo finished ==

    _rep(i, 1, m) printf("%lld\n", ANS[i]);
}

莫队算法和树状数组

值得注意的是，树状数组有以下几个特点
1) 树状数组维护的一般是增量d()d()
2) 或者是一个valval出现的次数in[]in[]

提供的信息有：前缀和，以及单点修改
其中，树状数组本身就表示局部和
Ci=Ai−lowbit(i)+1+⋯+AiC_{i} = A_{i - lowbit(i) + 1} + \cdots + A_{i}
所以单点修改A[i]A[i]的时候，其实也是单点修改C[i]C[i]
因为A[i]A[i]的变化会给[i,i+lowbit(i),⋯ ,n][i, i + lowbit(i), \cdots, n] 带来变化，所以

1
2
3
void add(int x, int d) {
    while (x <= n) C[x] += d, x += lowbit(x);
}

莫队算法和树状数组(二)

LUOGU1972

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

const int maxn = 1000000 + 5;

class Fwick {
public:
    vector<int> C;
    int n;
    
    void resize(int n) {
        this->n = n;
        C.resize(n + 1);
    }
    
    void clear() {
        fill(C.begin(), C.end(), 0);
    }
    
    int sum(int x) {
        int ret = 0;
        while (x) {
            ret += C[x];
            x -= lowbit(x);
        }
        return ret;
    }
    
    void add(int x, int d) {
        while (x <= n) {
            C[x] += d;
            x += lowbit(x);
        }
    }
    
    int find(int l, int r, int val) {
        while (l < r) {
            int mid = (l + r) >> 1;
            if(sum(mid) < val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

Fwick fwick;
int A[maxn], N, vis[maxn];
int ANS[maxn];
int m;

void init() {
    Set(vis, 0);
    Set(ANS, 0);
}

class Qry {
public:
    int l, r;
    int id;
    
    bool operator< (const Qry& rhs) const {
        return r < rhs.r;
    }
};
Qry qry[maxn];


void solve() {
    _rep(i, 1, m) {
        _rep(k, qry[i - 1].r + 1, qry[i].r) {
            if(vis[A[k]]) fwick.add(vis[A[k]], -1);
            
            vis[A[k]] = k;
            fwick.add(vis[A[k]], 1);
        }
        ANS[qry[i].id] = fwick.sum(qry[i].r) - fwick.sum(qry[i].l - 1);
        
        
    }
    
    _rep(i, 1, m) printf("%d\n", ANS[i]);
}

int main() {
    freopen("./input.txt", "r", stdin);
    init();
    scanf("%d", &N);
    
    int maxv = 0;
    _rep(i, 1, N) {
        scanf("%d", &A[i]);
        maxv = max(maxv, A[i]);
    }
    
    fwick.resize(maxn);
    
    // == then input the query ==
    scanf("%d", &m);
    
    _rep(i, 1, m) {
        scanf("%d%d", &qry[i].l, &qry[i].r);
        qry[i].id = i;
    }
    
    sort(qry + 1, qry + 1 + m);
    
    // == then solve the problem ==
    solve();
}

小z的袜子(代码优化)

小z的袜子

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

const int maxn = 50000 + 10;
int n, m, A[maxn];

// == block ==
int belong[maxn], sz, t;

void block() {
    sz = sqrt(n);
    t = n / sz;

    _rep(i, 1, t) {
        _rep(k, (i - 1) * sz + 1, i * sz) belong[k] = i;
    }

    if(t * sz < n) {
        t++;
        _rep(k, (t - 1) * sz + 1, n) belong[k] = t;
    }
}
// == block finished ==

inline llong gcd(llong a, llong b) {
    return b ? gcd(b, a % b) : a;
}

// == query structure ==
class Qry {
public:
    int l, r;
    int id;
};
Qry qry[maxn];

int cmp(const Qry& a, const Qry& b) {
    if(belong[a.l] ^ belong[b.l]) return belong[a.l] < belong[b.l];
    if(belong[a.l] & 1) return a.r < b.r;
    return a.r > b.r;
}

// == query finished ==

// == Mo algotithm ==
llong num[maxn];

void maintain(int x, int d, llong& ans) {
    ans -= num[x] * (num[x] - 1);
    num[x] += d;
    ans += num[x] * (num[x] - 1);
}

llong ANS[maxn][2];
void solve() {
    int l = 1, r = 0;
    llong res = 0;

    _rep(i, 1, m) {
        int ql = qry[i].l, qr = qry[i].r;

        if(ql == qr) {
            ANS[qry[i].id][0] = 0;
            ANS[qry[i].id][1] = 1;
            continue;
        }

        while (l < ql) maintain(A[l++], -1, res);
        while (l > ql) maintain(A[--l], 1, res);
        while (r < qr) maintain(A[++r], 1, res);
        while (r > qr) maintain(A[r--], -1, res);

        llong D = (llong)(qry[i].r - qry[i].l + 1) * (qry[i].r - qry[i].l);
        llong g = gcd(D, res);

        ANS[qry[i].id][0] = res;
        ANS[qry[i].id][1] = D;

        if(!g) ANS[qry[i].id][1] = 1;
        else {
            ANS[qry[i].id][0] /= g;
            ANS[qry[i].id][1] /= g;
        }
    }
}
// == Mo finished ==

void init() {
    Set(num, 0);
    Set(ANS, 0);
}

int main() {
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    init();

    // == get input ==
    scanf("%d%d", &n, &m);
    _rep(i, 1, n) scanf("%d", &A[i]);

    _rep(i, 1, m) {
        scanf("%d%d", &qry[i].l, &qry[i].r);
        qry[i].id = i;
    }
    // == input finished ==

    // == block ==
    block();
    // == block finsihed ==

    // == solve the problem ==
    sort(qry + 1, qry + 1 + m, cmp);
    solve();

    _rep(i, 1, m) printf("%lld/%lld\n", ANS[i][0], ANS[i][1]);
}

区间众数的莫队算法(二)

有时候我们不需要求出众数是多少
而只需要知道，出现次数最多的那个数，出现了多少次

LUOGU3709