2021-08-27新高二一期暑假集训21

发表于

空间宝石

标签

最短路 + floydfloyd + 线段树

思路

以优先级为下标，建一棵线段树，维护优先级区间最短路, 因为要满足结合律，所以用 floydfloyd 求最短路。

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define int long long
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

using namespace std;

const int N = 3e6 + 10;
int n, S;
int m;
int tot;
int e[2021][10][10];
int l[N], r[N];
int z, t, s;
int f[20200][10][10];
int dis[10010][10][10];
int g[10][10];

void dfs(int u, int l, int r) {
    for (int i = 0; i < 9; ++i) f[u][i][i] = 0;
    if (l > r) return;
    if (l == r) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                f[u][i][j] = min(f[u][i][j], e[l][i][j]);
            }
        }
        for (int k = 0; k < 9; ++k) {
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    f[u][i][j] = min(f[u][i][j], f[u][i][k] + f[u][k][j]);
                }
            }
        }
        return ;
    }
    int mid = (l + r) >> 1;
    dfs(ls(u), l, mid);
    dfs(rs(u), mid + 1, r);
    for (int k = 0; k < 9; ++k) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                f[u][i][j] = min(f[u][i][j], f[ls(u)][i][k] + f[rs(u)][k][j]);
            }
        }
    }
}

void solve(int id, int x, int y, int u = 1, int l = 1, int r = 2000) {
    if (x <= l && r <= y) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                g[i][j] = dis[id][i][j];
            }
        }
        for (int k = 0; k < 9; ++k) {
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    dis[id][i][j] = min(dis[id][i][j], g[i][k] + f[u][k][j]);
                }
            }
        }
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) solve(id, x, y, ls(u), l, mid);
    if (y > mid) solve(id, x, y, rs(u), mid + 1, r);
}

struct sege {
    int l, r;
    bool operator < (const sege A) const {
        return l < A.l;
    }
}a[N];

signed main() {
    scanf("%lld%lld", &n, &S);
    memset(e, 0x3f, sizeof(e));
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        int p, u, v, w;
        scanf("%lld%lld%lld%lld", &p, &u, &v, &w);
        e[p][u][v] = min(e[p][u][v], w);
    }
    dfs(1, 1, 2000);
    scanf("%lld", &m);
    while (m--) {
        int z, t, s;
        scanf("%lld%lld%lld", &z, &t, &s);
        for (int i = 1; i <= s; ++i) {
            scanf("%lld%lld", &a[i].l, &a[i].r);
        }
        sort(a + 1, a + s + 1);
        for (int i = 1; i <= s; ++i) {
            for (int j = 0; j < 9; ++j) {
                for (int k = 0; k < 9; ++k) {
                    dis[i][j][k] = 0x3f3f3f3f3f3f3f3f;
                }
            }
            for (int j = 0; j < 9; ++j) dis[i][j][j] = 0;
            solve(i, a[i].l, a[i].r);
        }
        for (int p = 2; p <= s; ++p) {
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    g[i][j] = dis[p][i][j];
                }
            }
            for (int k = 0; k < 9; ++k) {
                for (int i = 0; i < 9; ++i) {
                    for (int j = 0; j < 9; ++j) {
                        dis[p][i][j] = min(dis[p][i][j], dis[p - 1][i][k] + g[k][j]);
                    }
                }
            }
        }
        int ans = 0x3f3f3f3f3f3f3f3f;
        for (int i = 1; i <= s; ++i) {
            ans = min(ans, dis[i][z][t]);
        }
        if (ans == 0x3f3f3f3f3f3f3f3f) {
            puts("-1");
            continue;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

总结

floydfloyd 好，矩阵有的性质祂都有，还可以用线段维护区间 floydfloyd .

Mex

标签

主席树 + 迭代

思路

考虑 O(n2)O(n^2) 暴力:

对于每一个区间，把区间中的数从小到大排序，设对于左端点为 ll 右端点为 ii 的区间，未求出 mexmex , 且已知 1−R1-R 的数都在子集元素和中出现过. 考虑把右端点拓展到 i+1i + 1, 那么如果 ai+1≤R+1a_{i+1} \leq R + 1 ，那么 RR 变为 R+ai+1R + a_{i+1} ， 否则可以知道 mexmex 为 R+1R + 1

把它优化到 O(nlg⁡2n)O(n\lg^2 n)

对于每一个询问分别求解， 设已知 1−R1-R 的数都在子集元素和中出现过, 上一次已知 1−last1-last 的数都在子集元素和中出现过, 那么找出 [last+2,R+1][last + 2, R + 1] 之间的数，如果找不到，那么就得到了 mexmex 为 R+1R+1 , 否则让 RR 加上 [last+2,R+1][last + 2, R + 1] 之间的数, 那么显然新的 R>2lastR > 2last ， 所以这样的操作最多重复 O(lg⁡n)O(\lg n) 次，区间求和可以用主席树实现.

Code

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
#include <iostream>
#include <cstdio>
#define int long long

using namespace std;

const int N = 1e5 + 10;

struct Node {
    int ls, rs;
    int sum;
}lt[N * 100];
int n;
int a[N];
int m;
int rt[N], tot;
int sum[N];

void insert(int pre, int &u, int x, int l = 1, int r = 1000000000) {
    u = ++tot;
    lt[u] = lt[pre];
    lt[u].sum += x;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (x <= mid) insert(lt[pre].ls, lt[u].ls, x, l, mid);
    else insert(lt[pre].rs, lt[u].rs, x, mid + 1, r);
}

int query(int u, int x, int y, int l = 1, int r = 1000000000) {
    if (x <= l && r <= y) return lt[u].sum;
    int mid = (l + r) >> 1;
    int res = 0;
    if (x <= mid) res += query(lt[u].ls, x, y, l, mid);
    if (y > mid) res += query(lt[u].rs, x, y, mid + 1, r);
    return res;
}

int quemax(int pre, int u, int l = 1, int r = 1000000000) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (lt[lt[u].rs].sum == lt[lt[pre].rs].sum) return quemax(lt[pre].ls, lt[u].ls, l, mid);
    else return quemax(lt[pre].rs, lt[u].rs, mid + 1, r);
}

signed main() {
    scanf("%lld", &n);
    rt[0] = ++tot;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        insert(rt[i - 1], rt[i], a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    scanf("%lld\n", &m);
    while (m--) {
        int l, r;
        scanf("%lld%lld", &l, &r);
        int cnt = 0;
        int last = -1;
        while (cnt + 1 < quemax(rt[l - 1], rt[r])) {
            int tmp = cnt; 
            cnt += query(rt[r], last + 2, cnt + 1) - query(rt[l - 1], last + 2, cnt + 1);
            last = tmp;
            if (cnt == tmp) {
                break;
            }
        } 
        if (cnt + 1 >= quemax(rt[l - 1], rt[r])) {
            printf("%lld\n", sum[r] - sum[l - 1] + 1);
        }
        else 
        printf("%lld\n", cnt + 1);
    }
    return 0;
}