算法常见题型之STL set进阶：二分查找与迭代器双向移动

set 进阶用法详解与例题题解

一、set 基础回顾与常用操作

C++ STL 中的std::set是基于红黑树实现的有序不重复集合，默认按升序排列，所有插入、删除、查找操作的时间复杂度均为
O(log n)，是处理有序集合问题的核心工具。

1. 基础定义与初始化

#include<set>usingnamespacestd;set<int>s;// 默认升序的int集合set<int,greater<int>>s2;// 降序排列的int集合set<int>s3(s.begin(),s.end());// 用迭代器区间初始化

2. 核心常用操作

3. 遍历方式

set 只能通过双向迭代器遍历，默认按升序输出：

// 一般遍历for(autoit:s){cout<<it<<" ";}// 正向遍历for(autoit=s.begin();it!=s.end();++it){cout<<*it<<" ";}// 反向遍历for(autoit=s.rbegin();it!=s.rend();++it){cout<<*it<<" ";}

二、set 进阶核心操作

set 的真正价值在于有序性带来的二分查询与边界定位能力，以下是竞赛与工程中最常用的进阶操作。

1. 有序二分查找：lower_bound / upper_bound

set 自带基于树结构的二分查找，是最核心的进阶操作：

• s.lower_bound(x)：返回第一个大于等于x的元素的迭代器
• s.upper_bound(x)：返回第一个大于x的元素的迭代器

set<int>s={1,3,5,7,9};autoit1=s.lower_bound(4);// 指向5（第一个>=4的数）autoit2=s.upper_bound(5);// 指向7（第一个>5的数）

典型场景：查找元素的前驱/后继、范围统计、动态插入并维护边界。

2. 迭代器双向移动：prev / next

set 的迭代器是双向迭代器，不支持随机访问（不能写it += 2），必须通过prev和next移动：

• prev(it, k=1)：返回向前移动k步的迭代器
• next(it, k=1)：返回向后移动k步的迭代器

set<int>s={1,3,5,7,9};autoit=s.find(5);cout<<*prev(it);// 输出3（前一个元素）cout<<*next(it);// 输出7（后一个元素）

注意：移动不能超出begin()和end()的范围，否则会出现未定义行为。

3. 范围删除

set 支持按迭代器区间批量删除元素：

s.erase(first,last);// 删除[first, last)区间内的所有元素

时间复杂度为 O(k + log n)，其中k为删除元素个数，适合批量清理一段范围的数据。

4. 经典应用：前驱与后继查询

这是 set 最经典的进阶用法：在动态有序集合中，快速找到小于x的最大值（前驱）、大于x的最小值（后继）。

标准写法：

// 找x的后继（大于x的最小值）autoit=s.upper_bound(x);intsuff=*it;// 找x的前驱（小于x的最大值）intpre=*prev(it);

配合哨兵元素（如0和(n+1)），可以完美处理边界情况，无需额外判断。

三、进阶例题精讲：可见元素子区间计数

题目：https://ac.nowcoder.com/acm/contest/134527/E

题目大意

给定一个长度为nnn的排列ppp，对每个下标xxx，计算有多少个包含xxx的子区间 ([l,r])，使得p_xp\_xp_x在该子区间中是「可见的」。
可见定义：p_xp\_xp_x是子区间 ([l,x]) 的最大值（左可见），或者是子区间 ([x,r]) 的最大值（右可见）。

思路分析

1. 容斥原理转化问题

要求「左可见 OR 右可见」的区间数量，根据容斥原理：
答案 = 左可见区间数 + 右可见区间数 - 同时左右可见的区间数

2. 左右第一个更大元素

我们需要对每个xxx预处理两个关键值：

• left[x]：xxx左边第一个比p_xp\_xp_x大的元素下标，不存在则为000
• right[x]：xxx右边第一个比p_xp\_xp_x大的元素下标，不存在则为(n+1)(n+1)(n+1)

这两个值决定了p_xp\_xp_x作为最大值的影响范围：

• 只要左端点lll在 (left[x], x] 之间，([l,x]) 的最大值就是p_xp\_xp_x
• 只要右端点rrr在 [x, right[x]) 之间，([x,r]) 的最大值就是p_xp\_xp_x

3. 三部分计数

1. 左可见区间数：lll有 x-left[x] 种选择，rrr只要 >=x 即可（共n−x+1n-x+1n−x+1种）
   cnt_{left} = (x - left[x]) * (n - x + 1)
2. 右可见区间数：rrr有 right[x]-x 种选择，lll只要 <=x 即可（共xxx种）
   cnt_{right} = x * (right[x] - x)
3. 同时左右可见：等价于p_xp\_xp_x是整个 ([l,r]) 的最大值，lll和rrr都在影响范围内
   cnt_{both} = (x - left[x]) * (right[x] - x)

最终每个xxx的答案：
ans[x] = cnt_{left} + cnt_{right} - cnt_{both}

4. 用 set 高效求左右第一个更大元素

这是本题的核心，也是 set 进阶操作的典型应用。
因为数组是排列（值唯一且范围 1 ~ n），我们可以按值从大到小处理每个元素：

1. 预处理pos[v]：记录值为vvv的元素的下标
2. 初始化 set，插入哨兵0和(n+1)，避免边界判断
3. 从nnn到111遍历值vvv：
   • 当前下标 x = pos[v]
   • 此时 set 中已经插入了所有值大于v的元素的下标
   • 用se.upper_bound(x)找到第一个大于x的下标 → 就是right[x]
   • 对该迭代器用prev得到第一个小于x的下标 → 就是left[x]
   • 将xxx插入 set，供后续更小的值查询

正解代码

#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;voidsolve(){intn;cin>>n;vector<int>p(n+1),pos(n+1);for(inti=1;i<=n;i++){cin>>p[i];pos[p[i]]=i;// 记录每个值对应的下标}vector<int>left(n+1,0),right(n+1,n+1);set<int>se;se.insert(0);// 左哨兵se.insert(n+1);// 右哨兵// 按值从大到小处理，插入下标，查询前驱后继for(inti=n;i>=1;i--){intx=pos[i];autoit=se.upper_bound(x);// 第一个大于x的下标 → 右边第一个更大的right[x]=*it;left[x]=*prev(it);// 前一个元素 → 左边第一个更大的se.insert(x);}// 容斥计算每个位置的答案for(intx=1;x<=n;x++){ll L=left[x],R=right[x];ll cnt_left=(x-L)*1LL*(n-x+1);ll cnt_right=x*1LL*(R-x);ll cnt_both=(x-L)*1LL*(R-x);ll ans=cnt_left+cnt_right-cnt_both;cout<<ans<<" \n"[x==n];}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--)solve();return0;}

代码细节说明

1. 哨兵设计：初始插入0和(n+1)，保证所有查询都能找到合法的前驱后继，无需特判边界。
2. long long 强制转换：乘法可能爆int，每处乘法都通过1LL强制转为长整型，避免溢出。
3. 输出优化：" \n"[x == n]是常用技巧，最后一个元素输出换行，其余输出空格。

复杂度分析

• 时间复杂度：每个元素插入、查询 set 各一次，单次 O(log n)，总复杂度 O(nlog n)，满足 n<=5e5 的限制。
• 空间复杂度：(O(n))(O(n))(O(n))，用于存储数组和 set。

样例验证

以第一组样例n=3, p=[2,1,3]为例：

• pos[1]=2, pos[2]=1, pos[3]=3
• 从大到小处理：
  • i=3，x=3：right[3]=4, left[3]=0，插入3
  • i=2，x=1：right[1]=3, left[1]=0，插入1
  • i=1，x=2：right[2]=3, left[2]=1，插入2
• 计算得三个位置答案均为3，与样例输出一致。

本题亮点

本题也可用单调栈求左右第一个更大元素，但用 set 的有序性 + 前驱后继查询优雅实现，代码更简洁，且思路直观，是 set 进阶操作的典型应用场景。