许多优化 都是边遍历 边更新维护
可以借助各种数据结构(轮子bush
来减少循环次数 即时间复杂度 更快的拿到ret
lc3480
维护每个数字对应的最小、次小冲突值，计算无冲突子数组的最大数量，最终结合额外可扩展的子数组数量得到结果。
class Solution {
public:
long long maxSubarrays(int n, vector<vector<int>>& conflictingPairs) {
vector<vector<int>> groups(n + 1);
for (auto& p : conflictingPairs) {
int a = p[0], b = p[1];
if (a > b) {
swap(a, b);
}
groups[a].push_back(b);
}
long long ans = 0;
vector<long long> extra(n + 2);
vector<int> b = {n + 1, n + 1};
for (int i = n; i > 0; i--) {
// 维护最小 b 和次小 b
b.insert(b.end(), groups[i].begin(), groups[i].end());
ranges::sort(b);
b.resize(2);
ans += b[0] - i;
extra[b[0]] += b[1] - b[0];
}
return ans + ranges::max(extra);
}
};
lc3479
线段树二分 vs 树状数组
感觉线段树和树状数组本质上很相似，这俩的区别和应用场景是不一样么？
- 可差分数据和不可差分数据的区别吧，比如最大值，树状数组只能够维护前缀的最大值
- 树状数组适用于计算【差】信息的场景（比如子数组和等于两个前缀和的差）
- 但对于求最大最小的问题不好处理，比如修改元素 + 计算区间最大值的情况，用线段树更合适
