不过他的理解能力也是惊人,至少不像我读不懂题
它甚至还能自动给题目加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
算法思路:
步骤
- 首先,我们需要对输入的数据进行离散化处理,即把 ai,bi 映射到一个新的连续的区间。然后,我们使用线段树来维护白色区间。
- 对于线段树的每个节点,我们需要记录以下信息:l,r 表示该节点表示的区间范围,len 表示该节点表示的区间中最长的白色连续段长度,lmax 表示该节点表示的区间中最长的以 l 为起点的白色连续段长度,rmax 表示该节点表示的区间中最长的以 �r 为终点的白色连续段长度,sum 表示该节点表示的区间中白色连续段的总长度。
- 对于每次操作,我们使用递归的方式更新线段树。对于当前节点表示的区间和操作区间之间的交集,我们分别递归向左子树和右子树进行更新。对于当前节点表示的区间和操作区间的并集,我们需要重新计算该节点的 len,lmax,rmax,sum。
- 最后,我们只需要输出线段树的根节点的 lmax 和 rmax 的最大值即可。
时间复杂度:
离散化的时间复杂度为 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; }