「题解」 [COCI 2023/2024 No.2]Zatopljenje

磅豆龙 融会贯通
  2024-07-28 14:19:44 2024-07-28 14:19:44 Created   2024-08-03 09:39:55 2024-08-03 09:39:55 Updated    2.1k Words  9 Mins  

Problem

点击直达题目

Solution

Step1. 分析

如果你对区间修改与维护有了解，那么你一定知道这个题目需要用线段树来维护。

Step2. 思路 & 步骤

  1. 定义和初始化：

    • 定义一些全局变量和结构体来存储数据和线段树节点信息。
    • 三个结构体：
    • 第一个结构体中定义一个数组用于存储线段树节点，每个节点包含区间的左边界、右边界、岛的长度、左端点类别和右端点类别。
      • 第二个结构体中定义一个数组用于存储询问，每个询问包含左边界、右边界、海平面上升高度和询问的。
      • 第三个结构体定义一个数组用于存储每个位置的高度及其。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int n, q, l, r, mid, x, sum, ma, ans[N], o, cnt, cnt1;
    map<int, int> m;

    // 结构体node用于存储线段树的节点信息
    struct node {
        int l, r, len, lc, rc;  // l和r表示区间左右边界, len表示区间内岛屿的数量, lc和rc表示区间左右端点的类别
    } a[N];

    // 结构体deno用于存储高度信息
    struct deno {
        int x, id;  // x表示高度, id表示高度对应的位置索引
    } c[N];

    // 结构体w用于存储查询信息
    struct w {
        int l, r, x, id;  // l和r表示查询区间, x表示海平面上升高度, id表示查询的索引
    } b[N];

  2. 构建线段树：

    • build 函数用于构建线段树，将每个叶子节点初始化为长度为的岛屿。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void build(int p, int l, int r) {
        a[p].l = l;
        a[p].r = r;
        if (l == r) {  // 叶子节点
            a[p].len = a[p].lc = a[p].rc = 1;  // 初始化为长度为1的岛屿
            return;
        }
        int mid = (l + r) / 2;
        build(p * 2, l, mid);  // 递归构建左子树
        build(p * 2 + 1, mid + 1, r);  // 递归构建右子树
        gx(p);  // 更新当前节点信息
    }

  3. 更新操作：

    • change 函数用于更新区间内的节点，将对应的高度位置更新为新的类别。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void change(int p, int l, int r) {
        if (l <= a[p].l && a[p].r <= r) {  // 完全覆盖
            a[p].len = 0;  // 将区间内的长度设置为0
            a[p].lc = a[p].rc = ++cnt1;  // 更新类别
            return;
        }
        int mid = (a[p].l + a[p].r) / 2;
        if (l <= mid) change(p * 2, l, r);  // 递归更新左子树
        if (mid < r) change(p * 2 + 1, l, r);  // 递归更新右子树
        gx(p);  // 更新当前节点信息
    }

  4. 查询操作：

    • ask 函数用于查询指定区间内的岛屿数量。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int ask(int p, int l, int r) {
        if (l <= a[p].l && a[p].r <= r)  // 完全覆盖
            return a[p].len;
        int mid = (a[p].l + a[p].r) / 2;
        int ans1 = 0;
        if (l <= mid && mid < r) {  // 跨区间查询
            ans1 = ask(p * 2, l, r) + ask(p * 2 + 1, l, r);  // 查询左右子树
            if (a[p * 2].rc == a[p * 2 + 1].lc)  // 如果左右子树的连接处高度相同，岛屿数量减少1
                ans1--;
        } else if (l <= mid) {  // 查询左子区间
            ans1 = ask(p * 2, l, r);
        } else if (mid < r) {  // 查询右子区间
            ans1 = ask(p * 2 + 1, l, r);
        }
        return ans1;
    }

  5. 排序和处理：

    • 将高度数组和查询数组分别按高度和海平面上升高度进行排序。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 比较函数，用于排序查询
    bool cmp(w x, w y) {
        return x.x < y.x;
    }

    // 比较函数，用于排序高度
    bool cmp1(deno x, deno y) {
        return x.x < y.x;
    }
    sort(c + 1, c + 1 + n, cmp1);  // 按高度排序
    sort(b + 1, b + 1 + q, cmp);  // 按海平面上升高度排序
    • 遍历每个查询，根据当前海平面上升高度更新线段树，然后进行查询并存储结果。
    1
    2
    3
    4
    while (cnt <= n && c[cnt].x <= b[i].x) {
        change(1, c[cnt].id, c[cnt].id);  // 更新线段树
        cnt++;
    }

  6. 输出结果：

    • 遍历每个查询的结果，按照原始顺序输出。
    1
    2
    3
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << endl;  // 输出结果
    }

时间复杂度计算

这段代码的时间复杂度主要由以下几个部分构成：

  1. 构建线段树的时间复杂度：

    • build 函数在初始化时对所有节点进行递归构建，其时间复杂度为。

  2. 更新线段树的时间复杂度：

    • change 函数在处理每次更新时需要递归更新相关节点，其时间复杂度为。

  3. 查询线段树的时间复杂度：

    • ask 函数在处理每次查询时需要递归查询相关节点，其时间复杂度为。

  4. 排序的时间复杂度：

    • sort 函数用于对高度数组和查询数组进行排序，其时间复杂度为和。

  5. 主循环的时间复杂度：

    • 主循环遍历每个查询，并在处理查询前对高度进行更新。由于每个高度更新和查询操作的复杂度为，并且每个高度只更新一次，因此这部分的总时间复杂度为。

综合来看，整个算法的时间复杂度为：

（所以是不会炸的）

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
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;

const int N = 10001005;

int n, q, l, r, mid, x, sum, ma, ans[N], o, cnt, cnt1;
map<int, int> m;

// 结构体node用于存储线段树的节点信息
struct node {
    int l, r, len, lc, rc;  // l和r表示区间左右边界, len表示区间内岛屿的数量, lc和rc表示区间左右端点的类别
} a[N];

// 结构体deno用于存储高度信息
struct deno {
    int x, id;  // x表示高度, id表示高度对应的位置索引
} c[N];

// 结构体w用于存储查询信息
struct w {
    int l, r, x, id;  // l和r表示查询区间, x表示海平面上升高度, id表示查询的索引
} b[N];

// 更新节点信息函数
void gx(int p) {
    a[p].len = a[p * 2].len + a[p * 2 + 1].len;  // 合并左右子区间的岛屿数量
    if (a[p * 2].rc == a[p * 2 + 1].lc)  // 如果左右子区间的连接处高度相同，岛屿数量减少1
        a[p].len--;
    a[p].lc = a[p * 2].lc;  // 更新左端点类别
    a[p].rc = a[p * 2 + 1].rc;  // 更新右端点类别
}

// 构建线段树函数
void build(int p, int l, int r) {
    a[p].l = l;
    a[p].r = r;
    if (l == r) {  // 叶子节点
        a[p].len = a[p].lc = a[p].rc = 1;  // 初始化为长度为1的岛屿
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);  // 递归构建左子树
    build(p * 2 + 1, mid + 1, r);  // 递归构建右子树
    gx(p);  // 更新当前节点信息
}

// 更新线段树函数
void change(int p, int l, int r) {
    if (l <= a[p].l && a[p].r <= r) {  // 完全覆盖
        a[p].len = 0;  // 将区间内的长度设置为0
        a[p].lc = a[p].rc = ++cnt1;  // 更新类别
        return;
    }
    int mid = (a[p].l + a[p].r) / 2;
    if (l <= mid) change(p * 2, l, r);  // 递归更新左子树
    if (mid < r) change(p * 2 + 1, l, r);  // 递归更新右子树
    gx(p);  // 更新当前节点信息
}

// 查询线段树函数
int ask(int p, int l, int r) {
    if (l <= a[p].l && a[p].r <= r)  // 完全覆盖
        return a[p].len;
    int mid = (a[p].l + a[p].r) / 2;
    int ans1 = 0;
    if (l <= mid && mid < r) {  // 跨区间查询
        ans1 = ask(p * 2, l, r) + ask(p * 2 + 1, l, r);  // 查询左右子树
        if (a[p * 2].rc == a[p * 2 + 1].lc)  // 如果左右子树的连接处高度相同，岛屿数量减少1
            ans1--;
    } else if (l <= mid) {  // 查询左子区间
        ans1 = ask(p * 2, l, r);
    } else if (mid < r) {  // 查询右子区间
        ans1 = ask(p * 2 + 1, l, r);
    }
    return ans1;
}

// 比较函数，用于排序查询
bool cmp(w x, w y) {
    return x.x < y.x;
}

// 比较函数，用于排序高度
bool cmp1(deno x, deno y) {
    return x.x < y.x;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    cnt1 = n + 1;
    for (int i = 1; i <= n; i++) {
        cin >> c[i].x;
        c[i].id = i;
    }
    sort(c + 1, c + 1 + n, cmp1);  // 按高度排序
    for (int i = 1; i <= q; i++) {
        cin >> b[i].l >> b[i].r >> b[i].x;
        b[i].id = i;
    }
    sort(b + 1, b + 1 + q, cmp);  // 按海平面上升高度排序
    cnt = 1;
    build(1, 1, n);  // 构建线段树
    for (int i = 1; i <= q; i++) {
        while (cnt <= n && c[cnt].x <= b[i].x) {
            change(1, c[cnt].id, c[cnt].id);  // 更新线段树
            cnt++;
        }
        ans[b[i].id] = ask(1, b[i].l, b[i].r);  // 查询岛屿数量
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << endl;  // 输出结果
    }
    return 0;
}
  • Title: 「题解」 [COCI 2023/2024 No.2]Zatopljenje
  • Author: 磅豆龙
  • Created at : 2024-07-28 14:19:44
  • Updated at : 2024-08-03 09:39:55
  • Link: https://blog.setbun.com/p/20240728.html
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
「题解」 [COCI 2023/2024 No.2]Zatopljenje
  1. Problem
  2. Solution
    1. Step1. 分析
    2. Step2. 思路 & 步骤
    3. 时间复杂度计算
  3. Code