T20200929

Posted on Edited on In Word count in article: 1.5k Reading time ≈ 5 mins.
大东辰的测试

T1维护序列

线段树二的板子题，没什么好说的吧。。。

失算了，区间乘法可以乘\(0\)，我直接忽略了

对拍的时候，压根就没有生成\(0\)的数据，拍了好多组都没问题，结果。。。

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
#include <bits/stdc++.h>
#define ls (x << 1)
#define rs (x << 1| 1)


using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int n, p;
int tagt[maxn << 2], tagp[maxn << 2], ans[maxn << 2];

inline void push_up(int x) 
{
    ans[x] = (ans[ls] + ans[rs]) % p;
}

void Build(int l, int r, int x = 1)
{
    tagt[x] = 1;
    if (l == r) {
        ans[x] = __read() % p;
        return ;
    }
    int mid = (l + r) >> 1;
    Build(l, mid, ls);
    Build(mid + 1, r, rs);
    push_up(x);
}

inline void f(int x, int l, int r, int valt, int valp)
{
    ans[x] = 1ll * ans[x] * valt % p;
    ans[x] = (ans[x] + 1ll * valp * (r - l + 1) % p) % p;
    tagp[x] = (1ll * tagp[x] * valt % p + valp) % p;
    tagt[x] = 1ll * tagt[x] * valt % p;
}

inline void push_down(int x, int l, int r)
{
    int mid = (l + r) >> 1;
    f(ls, l, mid, tagt[x], tagp[x]);
    f(rs, mid + 1, r, tagt[x], tagp[x]);
    tagt[x] = 1, tagp[x] = 0;
}

void update(int l, int r, int tl, int tr, int valt, int valp, int x = 1)
{
    if (l >= tl && r <= tr) {
        f(x, l, r, valt, valp);
        return ;
    }
    push_down(x, l, r);
    int mid = (l + r) >> 1;
    if (tl <= mid) update(l, mid, tl, tr, valt, valp, ls);
    if (tr > mid) update(mid + 1, r, tl, tr, valt, valp, rs);
    push_up(x);
}

int Query(int l, int r, int tl, int tr, int x = 1)
{
    if (l >= tl && r <= tr) return ans[x] % p;
    int mid = (l + r) >> 1;
    push_down(x, l, r);
    ll res(0);
    if (tl <= mid) res = Query(l, mid, tl, tr, ls);
    if (tr > mid) res = (res + Query(mid + 1, r, tl, tr, rs)) % p;
    return res % p;
}

signed main()
{
    n = __read(), p = __read();
    Build(1, n);
    int m = __read();
    while (m--) {
        int opt = __read(), l = __read(), r = __read();
        if (opt == 3) printf ("%d\n", Query(1, n, l, r) % p);
        else if (opt == 2) {
            int x = __read();
            update(1, n, l, r, 1, x);
        } else {
            int x = __read();
            update(1, n, l, r, x, 0);
        }
    }
}

T2公路修建

最小生成树，其实我觉得应该排两次序才能保证答案的正确性

但就是过了，就不用管了

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

struct Node {
    int u, v, id;
    int val[2];
    bool operator < (const Node &T) const {
        if (val[0] ^ T.val[0]) return val[0] < T.val[0];
        return val[1] < T.val[1];
    }
}edge[maxn];

struct OPT {
    int id, c;
    bool operator < (const OPT &t) const {
        return id < t.id;
    }
}Ans[maxn], Tmp[maxn];

int f[maxn];

int get_f(int x)
{
    if (f[x] == x) return x;
    return f[x] = get_f(f[x]);
}

int n, m, k;

inline bool Check(int lim)
{
    memset (Tmp, 0, sizeof Tmp);
    for (int i = 1; i <= n; ++i) f[i] = i;
    int cnt(0);
    for (int i = 1; i <= m; ++i) {
        if (edge[i].val[0] > lim) continue;
        int fx = get_f(edge[i].u), fy = get_f(edge[i].v);
        if (fx == fy) continue;
        f[fx] = fy;
        Tmp[++cnt] = {edge[i].id, 1};
    }
    if (cnt < k) return 0;
    for (int i = 1; i <= m; ++i) {
        if (edge[i].val[1] > lim) continue;
        int fx = get_f(edge[i].u), fy = get_f(edge[i].v);
        if (fx == fy) continue;
        f[fx] = fy;
        Tmp[++cnt] = {edge[i].id, 2};
    }
    // printf ("%d\n", cnt);
    return cnt == (n - 1);
}

signed main()
{
    n = __read(), k = __read(), m = __read();
    int l(0), r(30000), ans;
    for (int i = 1; i < m; ++i) {
        edge[i].u = __read(), edge[i].v = __read();
        edge[i].val[0] = __read(), edge[i].val[1] = __read();
        edge[i].id = i;
    }

    sort (edge + 1, edge + m + 1);

    while (l <= r) {
        int mid = (l + r) >> 1;
        if (Check(mid)) {
            memcpy(Ans, Tmp, sizeof (Ans));
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    printf ("%d\n", ans);
    sort (Ans + 1, Ans + n);
    for (int i = 1; i < n; ++i)
        printf ("%d %d\n", Ans[i].id, Ans[i].c);

    system("pause");
}

T3三色二叉树

看一眼就可以开始乱写的\(Dp\)

无脑乱搞即可

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int id;
int mx[maxn][3], mn[maxn][3];
char s[maxn];

inline int dfs()
{
    int p = ++id, size = s[p] - '0';
    mx[p][0] = mn[p][0] = 1;
    int son[2] = {0, 0};
    for (int i = 0; i < size; ++i)
        son[i] = dfs();

    if (size == 1) {
        mx[p][0] = max(mx[son[0]][1], mx[son[0]][2]) + 1;
        mx[p][1] = max(mx[son[0]][0], mx[son[0]][2]);
        mx[p][2] = max(mx[son[0]][0], mx[son[0]][1]);

        mn[p][0] = min(mn[son[0]][1], mn[son[0]][2]) + 1;
        mn[p][1] = min(mn[son[0]][0], mn[son[0]][2]);
        mn[p][2] = min(mn[son[0]][0], mn[son[0]][1]);
    } else if (size == 2) {
        mx[p][0] = max(mx[son[0]][1] + mx[son[1]][2], mx[son[0]][2] + mx[son[1]][1]) + 1;
        mx[p][1] = max(mx[son[0]][0] + mx[son[1]][2], mx[son[0]][2] + mx[son[1]][0]);
        mx[p][2] = max(mx[son[0]][1] + mx[son[1]][0], mx[son[0]][0] + mx[son[1]][1]);

        mn[p][0] = min(mn[son[0]][1] + mn[son[1]][2], mn[son[0]][2] + mn[son[1]][1]) + 1;
        mn[p][1] = min(mn[son[0]][0] + mn[son[1]][2], mn[son[0]][2] + mn[son[1]][0]);
        mn[p][2] = min(mn[son[0]][1] + mn[son[1]][0], mn[son[0]][0] + mn[son[1]][1]);
    }
    return p;
}

signed main()
{
    scanf ("%s", s + 1);
    dfs();
    printf ("%d %d\n", max(mx[1][0], max(mx[1][1], mx[1][2])), min(mn[1][0], min(mn[1][1], mn[1][2])));
    system("pause");
}

T4采花

这个稍微难想一点点

画图吧

那么就可以只维护左端点，然后感觉一下就完了

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
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)

using namespace std;

typedef long long ll;
const int maxn = 2e6 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int n, c, m, p(1);
int pre[maxn][2], lst[maxn];
int sum[maxn], clo[maxn];
int ans[maxn];

inline void update(int x, int val)
{
    while (x <= n) {
        sum[x] += val;
        x += lowbit(x);
    }
}

inline int query(int x)
{
    int ans(0);
    while (x) {
        ans += sum[x];
        x -= lowbit(x);
    }
    return ans;
}

struct Node
{
    int l, r, id;
    bool operator < (const Node &t) const {
        return r < t.r;
    }
}que[maxn];

signed main()
{
    n = __read(), c = __read(), m = __read();
    for (int i = 1; i <= n; ++i) {
        clo[i] = __read();
        pre[i][0] = lst[clo[i]];
        pre[i][1] = pre[pre[i][0]][0];
        lst[clo[i]] = i;
    }

    for (int i = 1; i <= m; ++i) {
        que[i].l = __read(), que[i].r = __read();
        que[i].id = i;
    }

    sort (que + 1, que + m + 1);

    for (int i = 1; i <= m; ++i) {
        while (p <= que[i].r) {
            if (pre[p][0]) {
                if (pre[p][1]) update(pre[p][1], -1);
                update(pre[p][0], 1);
            }
            ++p;
        }
        ans[que[i].id] = query(que[i].r) - query(que[i].l - 1);
    }

    for (int i = 1; i <= m; ++i) printf ("%d\n", ans[i]);
}