Problem

点击直达题目

Solution

Step1. 分析

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

Step2. 思路 & 步骤

1. 定义和初始化：

   • 定义一些全局变量和结构体来存储数据和线段树节点信息。
   • 三个结构体：
   • 第一个结构体中定义一个 $a$ 数组用于存储线段树节点，每个节点包含区间的左边界 $l$、右边界 $r$、岛的长度 $len$、左端点类别 $lc$ 和右端点类别 $rc$。
     • 第二个结构体中定义一个 $b$ 数组用于存储询问，每个询问包含左边界 $l$、右边界 $r$、海平面上升高度 $x$ 和询问的 $ID$。
     • 第三个结构体定义一个 $c$ 数组用于存储每个位置的高度及其 $id$。

   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$ 的岛屿。

   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 函数用于更新区间内的节点，将对应的高度位置更新为新的类别。

   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 函数用于查询指定区间内的岛屿数量。

   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. 排序和处理：

   • 将高度数组和查询数组分别按高度和海平面上升高度进行排序。

   // 比较函数，用于排序查询
   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);  // 按海平面上升高度排序

   • 遍历每个查询，根据当前海平面上升高度更新线段树，然后进行查询并存储结果。

   while (cnt <= n && c[cnt].x <= b[i].x) {
       change(1, c[cnt].id, c[cnt].id);  // 更新线段树
       cnt++;
   }

6. 输出结果：

   • 遍历每个查询的结果，按照原始顺序输出。

   for (int i = 1; i <= q; i++) {
       cout << ans[i] << endl;  // 输出结果
   }

时间复杂度计算

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

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

   • build 函数在初始化时对所有节点进行递归构建，其时间复杂度为 $\mathcal{O}(n)$。

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

   • change 函数在处理每次更新时需要递归更新相关节点，其时间复杂度为 $\mathcal{O}(\log n)$。

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

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

4. 排序的时间复杂度：

   • sort 函数用于对高度数组和查询数组进行排序，其时间复杂度为 $\Theta(n \log n)$ 和 $\Theta(q \log q)$。

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

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

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

（所以是不会炸的）

Code

#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;
}