【线段树】找最长“白色”线段

简介: 【线段树】找最长“白色”线段

 不过他的理解能力也是惊人,至少不像我读不懂题

它甚至还能自动给题目加Markdown,太**好看了

下面内容全为chatGPT生成

反正我没看懂

题目描述:

【题目描述】

先是在数轴区间 0 到10^9 (10的9次方)之间画上了白色。然后,这个区间的某一些部分又画上了黑色。然后某一些部分又画上白色,等等。请你找出经历M(1 <= M <= 5000)次着色操作后,最长的白色区间。

【输入格式】

首行位M,以下M行 着色 的信息,每一行格式如下:

ai bi ci 这里 ai ,bi 都是整数, ci 为字符'b' 或'w',用空格隔开。

这三个参数描述:从ai(点)到bi(点),着颜色ci, ('w'表示白,'b'表示黑),可以认为0 < ai <= bi < 10^9

【输出格式】

输出x,y (x < y),之间用空格隔开,表示最长的白色区间。假如有多个答案,输出x最小的那个

【样例输入】

4

1 999999997 b

40 300 w

300 634 w

43 47 b

【样例输出】

47 634

算法思路:

步骤

    1. 首先,我们需要对输入的数据进行离散化处理,即把 aibi 映射到一个新的连续的区间。然后,我们使用线段树来维护白色区间。
      1. 对于线段树的每个节点,我们需要记录以下信息:l,r 表示该节点表示的区间范围,len 表示该节点表示的区间中最长的白色连续段长度,lmax 表示该节点表示的区间中最长的以 l 为起点的白色连续段长度,rmax 表示该节点表示的区间中最长的以 �r 为终点的白色连续段长度,sum 表示该节点表示的区间中白色连续段的总长度。
        1. 对于每次操作,我们使用递归的方式更新线段树。对于当前节点表示的区间和操作区间之间的交集,我们分别递归向左子树和右子树进行更新。对于当前节点表示的区间和操作区间的并集,我们需要重新计算该节点的 lenlmaxrmaxsum
          1. 最后,我们只需要输出线段树的根节点的 lmaxrmax 的最大值即可。

          时间复杂度:

          离散化的时间复杂度为 O(M logM),线段树的时间复杂度为 O(M log2M),总时间复杂度为 O(Mlog2M)。

          代码

          以下是我为你提供的C++代码,实现了线段树+离散化,可以帮助你解决这道题目:

          //c++
          #include <bits/stdc++.h>
          using namespace std;
          const int MAXN = 20010;
          int n, m;
          vector<int> nums;
          map<int, int> idx;
          struct Node {
              int l, r, cnt;
              bool b;
              Node() {}
              Node(int L, int R, int Cnt, bool B) : l(L), r(R), cnt(Cnt), b(B) {}
          } tr[MAXN * 4];
          void pushup(int u) {
              if (tr[u].b) tr[u].cnt = nums[tr[u].r + 1] - nums[tr[u].l]; // 被完全覆盖
              else if (tr[u].l == tr[u].r) tr[u].cnt = 0; // 被完全删去
              else tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt; // 合并子区间
          }
          void build(int u, int l, int r) {
              tr[u] = Node(l, r, 0, false);
              if (l == r) return;
              int mid = l + r >> 1;
              build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
          }
          void modify(int u, int x, int y, bool b) {
              if (tr[u].l >= x && tr[u].r <= y) {
                  tr[u].b = b;
                  pushup(u);
                  return;
              }
              int mid = tr[u].l + tr[u].r >> 1;
              if (x <= mid) modify(u << 1, x, y, b);
              if (y > mid) modify(u << 1 | 1, x, y, b);
              pushup(u);
          }
          int main() {
              cin >> m;
              for (int i = 1, l, r; i <= m; i++) {
                  char c;
                  cin >> l >> r >> c;
                  nums.push_back(l), nums.push_back(r + 1); // 离散化
              }
              sort(nums.begin(), nums.end());
              nums.erase(unique(nums.begin(), nums.end()), nums.end());
              for (int i = 0; i < nums.size(); i++) idx[nums[i]] = i; // 记录下离散化后的下标
              build(1, 0, nums.size() - 2);
              for (int i = 1, l, r; i <= m; i++) {
                  char c;
                  cin >> l >> r >> c;
                  modify(1, idx[l], idx[r + 1] - 1, c == 'w' ? true : false); // 修改
                  cout << nums[tr[1].l] << " " << nums[tr[1].r + 1] << endl; // 输出区间
              }
              return 0;
          }

          image.gif


          相关文章
          |
          6月前
          |
          测试技术
          【深度优先搜索】【组合数学】【动态规划】1467.两个盒子中球的颜色数相同的概率
          【深度优先搜索】【组合数学】【动态规划】1467.两个盒子中球的颜色数相同的概率
          |
          6月前
          |
          算法
          【面试算法——动态规划 20】最长公共子序列&& 不相交的线
          【面试算法——动态规划 20】最长公共子序列&& 不相交的线
          |
          6月前
          假设你正在玩跳格子(所有格子排成一个纵列)游戏。需要 跳完n 个格子你才能抵达终点。 每次你可以跳 1 或 2 个格子。你有多少种不同的方法可以到达终点呢? 注意:给定 n 是一个正整数。
          假设你正在玩跳格子(所有格子排成一个纵列)游戏。需要 跳完n 个格子你才能抵达终点。 每次你可以跳 1 或 2 个格子。你有多少种不同的方法可以到达终点呢? 注意:给定 n 是一个正整数。
          |
          6月前
          leetcode-1725:可以形成最大正方形的矩形数目
          leetcode-1725:可以形成最大正方形的矩形数目
          37 0
          |
          人工智能 算法 BI
          【线段树】找最长“白色”线段
          【线段树】找最长“白色”线段
          92 0
          判断线段是否相交
          判断线段是否相交
          88 0
          【LeetCode】149. 直线上最多的点数
          【LeetCode】149. 直线上最多的点数
          【LeetCode】149. 直线上最多的点数
          给你n个线段,代表线段的左右端点,问最少删几条线段,使得剩下当中存在一个线段与所有剩下的所有线段都有交集
          考虑枚举每一条线段,求以此线段与所有线段都有交集,需要删除的线段数。 那么对于此线段[L,R],右端点小于L的,与它无交集,需要全删掉。同理左端点大于R的线段,也需要都删掉。 那么剩下的问题,就是需要删几个了。
          110 0
          暴力枚举:三角形的组成
          题目: 给定一个n个数的数字序列,每个数不超过1e9,有Q此询问,每次询问一个区间是否存在三个数可以组成一 个三角形,输入YES或NO(1<=n,Q<=1e5);
          108 0
          20天刷题计划-120. 三角形最小路径和
          给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。