AcWing 4412. 构造数组

Posted on Edited on In 
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
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
using PII = pair<int, int>;
const int N = 2e5 + 10, MOD = 998244353;
unordered_map<int, PII> m(N);
int n, a;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a);
        if (m.count(a)) {
            m[a].second = i;
        } else {
            m[a] = {i, i};
        }
    }
    vector<PII> v(m.size());
    int i = 0;
    for (auto &[_, p] : m) v[i++] = p;
    sort(v.begin(), v.end());
    int cnt = v.size(), pr = v[0].second;
    for (int i = 1; i < v.size(); ++i) {
        auto &[l, r] = v[i];
        if (l <= pr) pr = max(pr, r), --cnt;
        else pr = r;
    }
    long long ans = 1;
    for (int i = 1; i < cnt; ++i) ans = ans * 2 % MOD;
    printf("%lld\n", ans);
    return 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
#include <iostream>
#include <unordered_map>
using namespace std;
using PII = pair<int, int>;
const int N = 4e5 + 10, MOD = 998244353;
unordered_map<int, PII> m(N);
int n, a, sub[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a);
        if (m.count(a)) {
            m[a].second = i;
        } else {
            m[a] = {i, i};
        }
    }
    for (auto &[_, p] : m) {
        auto &[l, r] = p;
        ++sub[l << 1], --sub[r << 1 | 1];
    }
    int cnt = 0;
    for (int i = 1; i < N; ++i) {
        sub[i] += sub[i - 1];
        if (!sub[i - 1] && sub[i]) ++cnt;
    }
    long long ans = 1;
    for (int i = 1; i < cnt; ++i) ans = ans * 2 % MOD;
    printf("%lld\n", ans);
    return 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
#include <iostream>
#include <unordered_map>
using namespace std;
using PII = pair<int, int>;
const int N = 2e5 + 10, MOD = 998244353;
unordered_map<int, PII> m(N);
int n, a, f[N];
int find(int x) {
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a);
        if (m.count(a)) {
            m[a].second = i;
        } else {
            m[a] = {i, i};
        }
    }
    for (int i = 0; i < n; ++i) f[i] = i;
    int cnt = n;
    for (auto &[_, p] : m) {
        auto &[l, r] = p;
        int pa = find(l);
        while (pa < r) {
            f[pa] = find(pa + 1);
            pa = find(pa);
            --cnt;
        }
    }
    long long ans = 1;
    for (int i = 1; i < cnt; ++i) ans = ans * 2 % MOD;
    printf("%lld\n", ans);
    return 0;
}