优雅的分组贪心|线段树二分

许多优化 都是边遍历 边更新维护

可以借助各种数据结构(轮子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 树状数组

感觉线段树和树状数组本质上很相似，这俩的区别和应用场景是不一样么？

• 可差分数据和不可差分数据的区别吧，比如最大值，树状数组只能够维护前缀的最大值
• 树状数组适用于计算【差】信息的场景（比如子数组和等于两个前缀和的差）
• 但对于求最大最小的问题不好处理，比如修改元素 + 计算区间最大值的情况，用线段树更合适