Asusetic
0%

2021.06.20模拟赛

发表于 分类于 Valine：
本文字数： 363 阅读时长 ≈ 1 分钟

咕咕咕

2021.06.20 模拟赛

T1 城市建设

城市建设

非常裸的并查集

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
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m, q;
ll w[N];
struct Edge {
    int u, v, t;
} e[N];
struct Query {
    int t, id;
} qy[N];
ll ans[N];
int fa[N], siz[N];
ll val[N];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
        return;
    }
    // if (siz[x] < siz[y]) {
        // swap(x, y);
    // }
    // siz[x] += siz[y];
    val[x] += val[y];
    fa[y] = x;
}
int main() {
    // freopen("build.in", "r", stdin);
    // freopen("build.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &w[i]);
        fa[i]  = i;
        val[i] = w[i];
        siz[i] = 1;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &e[i].t, &e[i].u, &e[i].v);
    }
    sort(e + 1, e + 1 + m, [&](const Edge &A, const Edge &B) -> bool {
        return A.t < B.t;
    });
    for (int i = 1; i <= q; i++) {
        cin >> qy[i].t;
        qy[i].id = i;
    }
    sort(qy + 1, qy + 1 + q, [&](const Query &A, const Query &B) -> bool {
        return A.t < B.t;
    });
    int cur = 1;
    ll res  = 0;
    for (int i = 1; i <= q; i++) {
        while (e[cur].t <= qy[i].t && cur <= m) {
            int u = e[cur].u;
            int v = e[cur].v;
            u     = find(u);
            v     = find(v);
            if (u == v) {
                cur++;
                continue;
            } else {
                res += 1ll * val[u] * val[v];
                merge(u, v);
            }
            cur++;
        }
        ans[qy[i].id] = res;
    }
    for (int i = 1; i <= q; i++) {
        printf("%lld\n", ans[i]);
    }
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}
// Asusetic eru quionours.

T2 矩形

矩形2

扫描线板子，n为啥老找板子

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
#include <algorithm>
#include <array>
#include <cstdio>
#include <iostream>
using namespace std;
int n, m;
typedef long long ll;
const int N = 1e5 + 5;
int a[N], b[N], c[N];
int id[N], h[N];
ll val[N];
struct Data {
    int pos;
    ll h;
    int typ;
} q[N * 2];
ll ans;
namespace SegmentTree {
#define ls(x) x * 2
#define rs(x) x * 2 + 1
struct Node {
    ll sum, tag;
    int l, r;
};
array<Node, N << 2> tr;
void build(int x, int l, int r) {
    tr[x].l = l;
    tr[x].r = r;
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    build(ls(x), l, mid);
    build(rs(x), mid + 1, r);
}
void pushup(int x) {
    tr[x].sum = tr[ls(x)].sum + tr[rs(x)].sum;
}
void pushdown(int x) {
    auto &l  = tr[x].l;
    auto &r  = tr[x].r;
    auto mid = (int)(l + r) / 2;
    if (tr[x].tag) {
        tr[ls(x)].sum += tr[x].tag * 1ll * (mid - l + 1);
        tr[rs(x)].sum += tr[x].tag * 1ll * (r - mid);
        tr[ls(x)].tag += tr[x].tag;
        tr[rs(x)].tag += tr[x].tag;
        tr[x].tag = 0;
    }
}
void update(int rt, int L, int R, int v) {
    auto &l  = tr[rt].l;
    auto &r  = tr[rt].r;
    auto mid = (int)(l + r) / 2;
    if (L <= l && R >= r) {
        tr[rt].sum += 1ll * v * 1ll * (r - l + 1);
        tr[rt].tag += v;
        return;
    }
    pushdown(rt);
    if (L <= mid) {
        update(ls(rt), L, R, v);
    }
    if (mid < R) {
        update(rs(rt), L, R, v);
    }
    pushup(rt);
}
int query(int rt = 1) {
    auto &l  = tr[rt].l;
    auto &r  = tr[rt].r;
    auto mid = (int)(l + r) / 2;
    if (l == r) {
        if (tr[rt].sum)
            return l;
        else
            return l - 1;
    }
    pushdown(rt);
    if (!tr[rs(rt)].sum)
        return query(ls(rt));
    else
        return query(rs(rt));
}
#undef ls
#undef rs
} // namespace SegmentTree
int main() {
    // freopen("horizon.in", "r", stdin);
    // freopen("horizon.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        id[i] = i;
    }
    sort(id + 1, id + 1 + n, [&](const int &A, const int &B) -> bool {
        return c[A] < c[B];
    });
    for (int i = 1; i <= n; i++) {
        h[id[i]] = i;
        val[i]   = c[id[i]];
    }
    SegmentTree::build(1, 1, n);
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        q[++tot] = {a[i], h[i], 1};
        q[++tot] = {b[i], h[i], 2};
    }
    sort(q + 1, q + 1 + tot, [&](const Data &A, const Data &B) -> bool {
        if (A.pos == B.pos) {
            return A.typ < B.typ;
        }
        return A.pos < B.pos;
    });
    int last = 0;
    for (int i = 1; i <= tot; i++) {
        ans += 1ll * val[last] * (q[i].pos - q[i - 1].pos);
        if (q[i].typ == 1) {
            SegmentTree::update(1, 1, q[i].h, 1);
        } else {
            SegmentTree::update(1, 1, q[i].h, -1);
        }
        last = SegmentTree::query();
    }
    cout << ans << endl;
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}
// Asusetic eru quionours.

T3 新型计算机

除了数据范围大了十倍以外和 4.20 的方舟系统完全一致，没懂n的找题思路

T4 邮箱

邮箱

当时没看懂题/kk

其实就是两个区间 [a,b] [c,d][a,b] \ [c,d] 从 a→ba \rightarrow b 依次随机向 [c,d][c,d] 中的某个位置放球，球有颜色，每个位置有，求颜色匹配的的期望个数

首先每个球不论先后放下其实放对的概率是一样的，都是 cnt(coli)d−c+1\dfrac{\mathrm{cnt}(\mathrm{col_i})}{d-c+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
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
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;
using ll    = long long;
const int N = 1e6 + 5, Q = 1e6 + 10;
// const int BLOCK_SIZE = 893;
namespace IO {
inline char _getchar() {
    static const int BUFFER_SIZE = 1 << 15;
    static char *fs, *ft, fbuf[BUFFER_SIZE];
    if (fs == ft) {
        ft = (fs = fbuf) + fread(fbuf, 1, BUFFER_SIZE, stdin);
        if (fs == ft)
            return EOF;
    }
    return *fs++;
}
template <typename T> void read(T &x) {
    x     = 0;
    int f = 1;
    static char ch;
    while (!isdigit(ch = _getchar())) {
        if (ch == '-')
            f = -1;
    }
    for (; ch >= '0' && ch <= '9'; ch = _getchar())
        x = x * 10 + ch - '0';
    x *= f;
}
template <typename T, typename... Args> void read(T &x, Args &... args) {
    read(x);
    read(args...);
}
template <typename T> inline void write(T x) {
    if (x < 0)
        x = ~x + 1, putchar('-');
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
template <typename T, typename... Args> void write(T &x, Args &... args) {
    write(x);
    putchar(' ');
    write(args...);
}
} // namespace IO
using namespace IO;
ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}
pair<ll, ll> simply(ll x, ll y) {
    ll g = gcd(x, y);
    return make_pair(x / g, y / g);
}
int n, m, q;
array<int, N> a, b;
struct Data {
    int l, r, opt, id;
};
vector<Data> op;
array<int, N> len, belong, cnta, cntb;
array<ll, Q> ans;
int main() {
    read(n, m);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
    }
    for (int i = 1; i <= m; i++) {
        read(b[i]);
    }
    read(q);
    op.resize(4 * q);
    int tot = 0;
    for (int i = 1; i <= q; i++) {
        int l, r, x, y;
        read(l, r, x, y);
        op[tot++] = (Data{r, y, 1, i});
        op[tot++] = (Data{l - 1, y, -1, i});
        op[tot++] = (Data{r, x - 1, -1, i});
        op[tot++] = (Data{l - 1, x - 1, 1, i});
        len[i]    = y - x + 1;
    }
    int BLOCK_SIZE = (n / sqrt(4 * q) + 1) + 1;
    for (int i = 1; i <= max(n, m); i++) {
        belong[i] = (i - 1) / BLOCK_SIZE + 1;
    }
    sort(op.begin(), op.end(), [&](const Data &A, const Data &B) -> bool {
        if (belong[A.l] == belong[B.l]) {
            if (belong[A.l] & 1) {
                return belong[A.r] > belong[B.r];
            }
            return belong[A.r] < belong[B.r];
        }
        return A.l < B.l;
    });
    ll now(0ll);
    int l = 0, r = 0;
    auto change_a = [&](int x, int v) -> void {
        now += cntb[a[x]] * v;
        cnta[a[x]] += v;
    };
    auto change_b = [&](int x, int v) -> void {
        now += cnta[b[x]] * v;
        cntb[b[x]] += v;
    };
    for_each(op.begin(), op.end(), [&](const Data &x) -> void {
        while (l < x.l) {
            l++;
            change_a(l, 1);
        }
        while (l > x.l) {
            change_a(l, -1);
            l--;
        }
        while (r < x.r) {
            ++r;
            change_b(r, 1);
        }
        while (r > x.r) {
            change_b(r, -1);
            r--;
        }
        ans[x.id] += now * x.opt;
    });
    for (int i = 1; i <= q; i++) {
        auto res = simply(ans[i], len[i]);
        write(res.first, res.second);
        puts("");
    }
}