NekoNowcoder

Appearance

HappyTriangle - 题解 ​

标签与难度 ​

标签: 数据结构, 线段树, 动态开点线段树, 懒标记, 几何, 三角形不等式 难度: 2200

题目大意喵~ ​

主人你好喵~ 这道题是关于一个一开始空空如也的多重集合（就是允许有重复元素的集合啦）MS 的故事。我们需要处理 q 次操作，操作有三种类型：

  1. 插入 x: 往 MS 里放一个数字 x。
  2. 删除 x: 从 MS 里拿走一个数字 x（如果有很多个 x，只拿走一个哦）。
  3. 查询 x: 给定一个数字 x，判断我们能不能从 MS 中选出两个数 a 和 b，使得长度为 a、b、x 的三条边能组成一个不退化的三角形（也就是面积不为零的三角形）。

如果可以组成三角形，就输出 "Yes"，不然就输出 "No"，很简单吧，喵~

解题思路分析 ​

这道题的核心，就在于那个“组成三角形”的条件呢，喵~ 让我来给你分析一下！

1. 三角形的核心秘密！ ​

三条边 a, b, c 能组成一个不退化的三角形，当且仅当它们满足三角形不等式：

  • 两边之和大于第三边：a + b > c, a + c > b, b + c > a。

在我们的问题里，第三条边是给定的 x，所以我们需要从集合 MS 中找到一对 (a, b) 满足：

  1. a + b > x
  2. a + x > b
  3. b + x > a

后两个不等式可以合并一下下，a + x > b 就是 x > b - a，b + x > a 就是 x > a - b。合起来就是 x > |a - b|。

所以，我们的任务就变成了：对于给定的 x，判断是否存在一对 (a, b) 选自 MS，使得 |a - b| < x < a + b。

2. 从暴力到优雅的喵变！ ​

一个最直接的想法是，对于每次查询 x，我们遍历 MS 中所有的数对 (a, b)，然后检查它们是否满足 |a - b| < x < a + b。但是 MS 中最多可能有 q 个元素，每次查询都遍历所有数对，复杂度是 O(q2)O(q^2)，这可太慢啦，肯定会超时的说！

我们需要一个更聪明的办法。让我们换个角度思考：对于一个数对 (a, b)，它能和哪些 x 组成三角形呢？答案是所有满足 |a - b| < x < a + b 的 x。这其实是一个开区间 (|a - b|, a + b) 呢！

所以，整个问题可以转化为：

查询 x 是否被 MS 中所有数对 (a,b) 产生的区间的并集所覆盖。

这听起来就像是，我们有很多很多条线段，然后问某个点 x 是否被至少一条线段覆盖。这是一个经典的线段覆盖问题！我们可以用一个数组 cover，cover[k] 表示点 k 被多少个区间覆盖。对于每个区间 (L, R)，我们把 cover[L+1] 到 cover[R-1] 的值都加一。查询时，只要看 cover[x] 是否大于 0 就好了。

但是！MS 中的数对还是太多了，我们不能为所有 O(q2)O(q^2) 个数对都去更新区间。这里就需要一个非常关键的观察了，喵~（竖起耳朵）

3. “邻居”的力量！ ​

假设我们把 MS 中所有的元素（包括重复的）从小到大排好序。 s_1 <= s_2 <= ... <= s_N

关键结论：如果存在某个非相邻的数对 (s_i, s_j) (其中 i+1 < j) 产生的区间 (|s_j - s_i|, s_i + s_j) 覆盖了 x，那么一定也存在一个由相邻数对产生的区间能够覆盖 x。

证明时间喵~ 假设我们有一组非相邻的数 s_i 和 s_j，它们之间至少还有一个数 s_k（s_i \le s_k \le s_j）。 我们来比较一下非相邻对 (s_i, s_j) 产生的区间 I1=(∣sj−si∣,si+sj)I_1 = (|s_j - s_i|, s_i + s_j) 和一个更“紧凑”的对 (s_k, s_j) 产生的区间 I2=(∣sj−sk∣,sk+sj)I_2 = (|s_j - s_k|, s_k + s_j)。

  • 因为 s_i \le s_k，所以 s_j - s_k \le s_j - s_i。区间的左端点 |s_j - s_k| 不会比 |s_j - s_i| 更大。
  • 因为 s_i \le s_k，所以 s_i + s_j \le s_k + s_j。区间的右端点 s_k + s_j 不会比 s_i + s_j 更小。

这意味着 I1⊆I2I_1 \subseteq I_2！也就是说，非相邻对产生的区间，总能被一个更“靠近”的数对（最终是某个相邻数对）产生的区间所包含。

所以，我们只需要考虑所有相邻数对产生的区间就足够了！MS 中最多有 q 个元素，相邻的数对最多只有 q-1 对。这下问题就简单多啦！

4. 动态开点线段树登场！ ​

现在，我们的策略是：

  • 用一个 std::multiset 来维护 MS 中的所有数字，它可以自动排序并处理重复元素。
  • 用一个数据结构来维护所有相邻数对产生的区间的覆盖情况。

每次操作：

  • 插入 x:
    1. 在 multiset 中找到 x 的左邻居 p 和右邻居 n。
    2. 原来的相邻对 (p, n) 被 x 分开了，所以我们要撤销它的贡献：在区间 (n-p, n+p) 上减一。
    3. 形成了两个新的相邻对 (p, x) 和 (x, n)。我们要加上它们的贡献：分别在区间 (x-p, x+p) 和 (n-x, n+x) 上加一。
    4. 最后把 x 插入 multiset。
  • 删除 x: 操作完全相反。
  • 查询 x: 查询我们数据结构中点 x 的覆盖次数是否大于 0。

注意到数字的范围可以到 10910^9，普通的数组肯定开不下。但是操作次数 q 不算太大。这种“值域很广，但操作数有限”的场景，正是动态开点线段树大显身手的时候！我们用它来实现区间增加/减少和单点查询，再配上懒标记来优化区间更新的效率。

最终的算法就是： std::multiset + 动态开点线段树（带懒标记）

这样，每次操作的复杂度就是 multiset 的 O(log⁡q)O(\log q) 加上动态开点线段树的 O(log⁡R)O(\log R)（其中 RR 是值域上限 10910^9），完全可以接受啦，喵~

代码实现 ​

这是我根据上面的思路，精心重构的一份代码哦~ 注释很详细，希望能帮到你！

cpp
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

// 为了方便，我们定义一个很大的数作为哨兵
const long long INF = 2e9 + 7; 

// 动态开点线段树的节点
struct Node {
    Node *left_child = nullptr;
    Node *right_child = nullptr;
    long long count = 0;      // 区间覆盖次数
    long long lazy_tag = 0;   // 懒标记
};

Node* root = new Node(); // 线段树的根节点

// 下推懒标记
void push_down(Node* p, long long range_len) {
    if (!p || p->lazy_tag == 0) {
        return;
    }
    
    // 如果没有子节点，就动态创建它们
    if (!p->left_child) p->left_child = new Node();
    if (!p->right_child) p->right_child = new Node();
    
    long long tag = p->lazy_tag;
    long long left_len = range_len - range_len / 2;
    long long right_len = range_len / 2;

    // 更新左子节点的 count 和 lazy_tag
    p->left_child->count += tag * left_len;
    p->left_child->lazy_tag += tag;

    // 更新右子节点的 count 和 lazy_tag
    p->right_child->count += tag * right_len;
    p->right_child->lazy_tag += tag;
    
    // 清除当前节点的懒标记
    p->lazy_tag = 0;
}

// 区间更新 [update_l, update_r] 范围内的值都加上 val
void update(Node* p, long long current_l, long long current_r, long long update_l, long long update_r, int val) {
    if (update_l > update_r || current_l > update_r || current_r < update_l) {
        return;
    }
    
    if (update_l <= current_l && current_r <= update_r) {
        p->count += val * (current_r - current_l + 1);
        p->lazy_tag += val;
        return;
    }
    
    long long mid = current_l + (current_r - current_l) / 2;
    push_down(p, current_r - current_l + 1);
    
    if (!p->left_child) p->left_child = new Node();
    update(p->left_child, current_l, mid, update_l, update_r, val);
    
    if (!p->right_child) p->right_child = new Node();
    update(p->right_child, mid + 1, current_r, update_l, update_r, val);
    
    // 这里的回溯更新 count 是用于区间求和的，本题只做单点查询，可以省略
    // p->count = p->left_child->count + p->right_child->count;
}

// 单点查询 pos 位置的值
long long query(Node* p, long long current_l, long long current_r, long long pos) {
    if (!p) {
        return 0;
    }
    if (current_l == current_r) {
        return p->count;
    }
    
    long long mid = current_l + (current_r - current_l) / 2;
    push_down(p, current_r - current_l + 1);
    
    if (pos <= mid) {
        return query(p->left_child, current_l, mid, pos);
    } else {
        return query(p->right_child, mid + 1, current_r, pos);
    }
}

// 辅助函数，处理相邻对 (a, b) 区间变化的工具
void modify_pair_contribution(long long a, long long b, int val) {
    if (a == -INF || b == INF) return; // 不处理和哨兵组成的对
    // 区间是 (|b-a|, a+b)，即 [b-a+1, a+b-1]
    update(root, 1, INF, b - a + 1, a + b - 1, val);
}


int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int q;
    std::cin >> q;

    std::multiset<long long> ms;
    // 放入两个哨兵，这样每个元素都一定有左右邻居了
    ms.insert(-INF);
    ms.insert(INF);

    for (int i = 0; i < q; ++i) {
        int op;
        long long x;
        std::cin >> op >> x;

        if (op == 1) { // 插入
            auto it = ms.lower_bound(x);
            long long right_neighbor = *it;
            long long left_neighbor = *(--it);
            
            // 1. 移除旧邻居对 (left_neighbor, right_neighbor) 的贡献
            modify_pair_contribution(left_neighbor, right_neighbor, -1);
            // 2. 添加新邻居对 (left_neighbor, x) 的贡献
            modify_pair_contribution(left_neighbor, x, 1);
            // 3. 添加新邻居对 (x, right_neighbor) 的贡献
            modify_pair_contribution(x, right_neighbor, 1);
            
            ms.insert(x);
        } else if (op == 2) { // 删除
            auto it = ms.find(x);
            long long right_neighbor = *(++it);
            --it;
            long long left_neighbor = *(--it);
            
            // 1. 移除旧邻居对 (left_neighbor, x) 的贡献
            modify_pair_contribution(left_neighbor, x, -1);
            // 2. 移除旧邻居对 (x, right_neighbor) 的贡献
            modify_pair_contribution(x, right_neighbor, -1);
            // 3. 恢复旧邻居对 (left_neighbor, right_neighbor) 的贡献
            modify_pair_contribution(left_neighbor, right_neighbor, 1);
            
            ms.erase(ms.find(x));
        } else { // 查询
            if (query(root, 1, INF, x) > 0) {
                std::cout << "Yes\n";
            } else {
                std::cout << "No\n";
            }
        }
    }

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(qlog⁡R)O(q \log R) 对于 q 次操作中的每一次，我们都需要：

    1. 在 std::multiset 中查找邻居，复杂度为 O(log⁡q)O(\log q)。
    2. 在线段树中进行常数次（3次）的区间更新或1次单点查询。动态开点线段树操作一次的深度是 O(log⁡R)O(\log R)，其中 RR 是值域（这里是 10910^9 级别）。 所以总的时间复杂度是 O(q⋅(log⁡q+log⁡R))O(q \cdot (\log q + \log R))。因为 RR 比 qq 大得多，所以可以简化为 O(qlog⁡R)O(q \log R)。

  • 空间复杂度: O(qlog⁡R)O(q \log R)

    1. std::multiset 最多存储 q 个元素，空间为 O(q)O(q)。
    2. 动态开点线段树每次更新最多会创建 O(log⁡R)O(\log R) 个新节点。q 次操作总共会创建 O(qlog⁡R)O(q \log R) 个节点。这是空间占用的主要部分。

知识点总结 ​

这道题真是一次愉快的冒险呢，喵~ 我们用到的知识点有：

  1. 三角形不等式: 这是解决问题的数学基础。能灵活地将几何问题 a+b>c, |a-b|<c 转化为区间问题 x \in (|a-b|, a+b) 是解题的第一步！
  2. 关键性质的洞察: 能够发现并证明“我们只需要考虑相邻数对”，是避免 O(q2)O(q^2) 复杂度的关键。这大大减少了我们需要维护的信息量。
  3. 动态开点线段树: 面对巨大的值域和相对稀疏的操作点，动态开点线段树是我们的不二之选。它按需分配内存，有效地解决了空间问题。
  4. 懒标记 (Lazy Propagation): 配合线段树处理区间更新的利器。它能将多次更新的代价分摊，保证了操作的对数复杂度。
  5. 哨兵思想: 在 multiset 中预先插入极大和极小的哨兵值，可以简化代码逻辑，避免处理边界情况，让每个元素都拥有左右邻居。

希望这篇题解能帮到你，如果还有问题，随时可以再来找我玩哦，喵~