牛客笔记7.15

问题描述

给定一个长度为 n 的数组，每天增大其中一个数的值。每次操作后，计算有多少数满足：在与其他所有数的比较中，至少输掉了 ⌈(n-1)/2⌉ 次（即该数小于至少一半的其他数）。

核心思路

  1. 观察：

    • 对于总元素数 n，⌈(n-1)/2⌉ 等价于 n - ⌊n/2⌋。
    • 例如：
      • n=5 时，⌈(5-1)/2⌉ = 2，即需要小于至少 2 个数。
      • n=6 时，⌈(6-1)/2⌉ = 3，即需要小于至少 3 个数。
    • 因此，问题转化为：每次操作后，统计严格小于第 m = n - ⌊n/2⌋ 小元素的数的数量。

  2. 数据结构选择：

    使用 ordered_set维护动态有序集合。

    功能：

    ​ 插入 / 删除元素：O (log n)

    ​ 查询第 k 小元素：find_by_order(k) → O(log n)

    ​ 查询元素排名：order_of_key(key) → O(log n)

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;

// 自定义比较函数：先按值比较，值相同时按唯一标识比较
struct comp {
    bool operator()(const pll& a, const pll& b) const {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    }
};

// 定义支持顺序统计的有序集合
typedef tree<pll, null_type, comp,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> q;
        vector<ll> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        
        // 初始化有序集合，每个元素是{值, 唯一标识}
        ordered_set o;
        vector<pll> pp(n);
        ll id = 0;
        for (int i = 0; i < n; ++i) {
            pll p = {a[i], id++};
            pp[i] = p;
            o.insert(p);
        }
        
        // 计算关键参数m = n - ⌊n/2⌋
        int k = n / 2;
        int m = n - k;
        
        // 处理每次查询
        while (q--) {
            int p;
            ll v1;
            cin >> p >> v1;
            p--; // 转换为0-based索引
            
            // 移除旧值，插入新值
            pll p1 = pp[p];
            o.erase(p1);
            ll v2 = p1.first + v1;
            pll p2 = {v2, id++};
            o.insert(p2);
            pp[p] = p2;
            
            // 查询第m小的元素的值s
            auto it = o.find_by_order(m);
            ll s = it->first;
            
            // 统计严格小于s的元素数量
            ll ans = o.order_of_key(pll(s, 0));
            cout << ans << endl;
        }
    }
    return 0;
}

关键步骤解析

  1. 初始化阶段：
    • 将每个元素存储为 {值, 唯一标识} 的形式，确保元素的唯一性。
    • 唯一标识通过递增的 id 生成，避免值相同的元素冲突。
  2. 查询参数计算：
    • k = n / 2：计算 ⌊n/2⌋。
    • m = n - k：即 n - ⌊n/2⌋，表示需要找到的第 m 小的元素位置。
  3. 动态更新：
    • 每次更新时，先删除旧值，再插入新值（值增加后的结果）。
    • 通过 find_by_order(m) 查询第 m 小的元素的值 s。
  4. 结果统计：
    • 使用 order_of_key(pll(s, 0)) 统计严格小于 s 的元素数量，即为答案。

复杂度分析

  • 初始化：O (n log n)（插入 n 个元素）
  • 单次查询：O (log n)（删除、插入、查询排名各一次）
  • 总体复杂度：O(n log n + q log n)

ordered_set

基于红黑树实现，支持动态维护有序集合。

核心操作：

1
2
3
4
insert(key)           // 插入元素，O(log n)
erase(key)            // 删除元素，O(log n)
find_by_order(k)      // 查询第k小的元素，O(log n)
order_of_key(key)     // 查询小于key的元素数量，O(log n)

ordered_set模板

1
2
typedef tree<Key, Mapped, Compare, Tag, Node_Update> ordered_set;
typedef tree<pll, null_type, comp,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

  1. **Key**：存储的元素类型（如 int, ll, pair<ll, ll> 等）。

    • 示例：tree<int, null_type, ...> 存储整数。

  2. **Mapped**：

    • null_type：表示这是一个集合（Set）。
    • 若为 map，可指定映射类型（如 tree<int, int, ...> 表示键值对）。

  3. **Compare**：比较函数，定义元素的排序规则。

    • 升序排列

      1
      2
      3
      4
      5
      struct comp {
          bool operator()(const int& a, const int& b) const {
              return a < b;  // 升序排列
          }
      };

  4. **Tag**：底层数据结构类型。

    • rb_tree_tag：红黑树（平衡二叉搜索树）。
    • splay_tree_tag：伸展树（自适应树）。

  5. **Node_Update**：节点更新策略。

    • tree_order_statistics_node_update：启用顺序统计功能。
    • 提供两个关键方法：
      • order_of_key(k)：返回小于 k 的元素数量。
      • find_by_order(k)：返回第 k 小的元素的迭代器（从 0 开始）。

ordered_set 的常用操作

以下是 ordered_set 的核心操作及时间复杂度：

操作 代码示例 时间复杂度
插入元素 os.insert(key) O(log n)
删除元素 os.erase(key) O(log n)
查询元素是否存在 os.find(key) != os.end() O(log n)
查询第 k 小的元素 *os.find_by_order(k) O(log n)
查询小于 key 的元素数量 os.order_of_key(key) O(log n)
查询元素的排名 os.order_of_key(key) O(log n)
获取集合大小 os.size() O(1)

基础用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// 定义存储int类型的ordered_set
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;
int main() {
    ordered_set os;
    // 插入元素
    os.insert(3);
    os.insert(1);
    os.insert(2);
    // 查询第 0 小的元素（最小元素）
    cout << *os.find_by_order(0) << endl;  // 输出: 1
    // 查询元素 2 的排名（小于 2 的元素数量）
    cout << os.order_of_key(2) << endl;    // 输出: 1
    // 删除元素
    os.erase(2);
    // 验证元素是否存在
    cout << (os.find(2) != os.end()) << endl;  // 输出: 0 (false)
    return 0;
}

pair 类型

在之前的算法中，我们使用 pair<ll, ll> 存储元素，确保值相同时通过唯一标识区分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct comp {
    bool operator()(const pair<ll, ll>& a, const pair<ll, ll>& b) const {
        if (a.first != b.first) return a.first < b.first;  // 优先按值排序
        return a.second < b.second;      // 值相同时按唯一标识排序
    }
};

typedef tree<pair<ll, ll>, null_type, comp, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;

// 使用示例
ordered_set os;
ll id = 0;
os.insert({3, id++});  // {值, 唯一标识}
os.insert({1, id++});
os.insert({3, id++});  // 两个值为3的元素通过id区分

对比其他数据结构

数据结构 查询排名 查询第 k 小 插入 / 删除 支持重复元素
ordered_set O(log n) O(log n) O(log n) 否
std::set ❌ ❌ O(log n) 否
std::multiset ❌ ❌ O(log n) 是
线段树 O(log n) O(log n) O(log n) 是