set 进阶用法详解与例题题解一、set 基础回顾与常用操作C STL 中的std::set是基于红黑树实现的有序不重复集合默认按升序排列所有插入、删除、查找操作的时间复杂度均为O(log n)是处理有序集合问题的核心工具。1. 基础定义与初始化#includesetusingnamespacestd;setints;// 默认升序的int集合setint,greaterints2;// 降序排列的int集合setints3(s.begin(),s.end());// 用迭代器区间初始化2. 核心常用操作操作功能时间复杂度s.insert(x)插入元素x重复则不生效O(log n)s.erase(x)删除值为x的元素O(log n)s.erase(it)删除迭代器it指向的元素O(log n)s.find(x)查找x返回迭代器不存在返回s.end()O(log n)s.count(x)返回x的出现次数0或1O(log n)s.size()返回集合元素个数(O(1))(O(1))(O(1))s.empty()判断集合是否为空(O(1))(O(1))(O(1))s.clear()清空集合(O(n))(O(n))(O(n))3. 遍历方式set 只能通过双向迭代器遍历默认按升序输出// 一般遍历for(autoit:s){coutit ;}// 正向遍历for(autoits.begin();it!s.end();it){cout*it ;}// 反向遍历for(autoits.rbegin();it!s.rend();it){cout*it ;}二、set 进阶核心操作set 的真正价值在于有序性带来的二分查询与边界定位能力以下是竞赛与工程中最常用的进阶操作。1. 有序二分查找lower_bound / upper_boundset 自带基于树结构的二分查找是最核心的进阶操作s.lower_bound(x)返回第一个大于等于x的元素的迭代器s.upper_bound(x)返回第一个大于x的元素的迭代器setints{1,3,5,7,9};autoit1s.lower_bound(4);// 指向5第一个4的数autoit2s.upper_bound(5);// 指向7第一个5的数典型场景查找元素的前驱/后继、范围统计、动态插入并维护边界。2. 迭代器双向移动prev / nextset 的迭代器是双向迭代器不支持随机访问不能写it 2必须通过prev和next移动prev(it, k1)返回向前移动k步的迭代器next(it, k1)返回向后移动k步的迭代器setints{1,3,5,7,9};autoits.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的最小值autoits.upper_bound(x);intsuff*it;// 找x的前驱小于x的最大值intpre*prev(it);配合哨兵元素如0和(n1)可以完美处理边界情况无需额外判断。三、进阶例题精讲可见元素子区间计数题目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大的元素下标不存在则为000right[x]xxx右边第一个比p_xp\_xp_x大的元素下标不存在则为(n1)(n1)(n1)这两个值决定了p_xp\_xp_x作为最大值的影响范围只要左端点lll在 (left[x], x] 之间([l,x]) 的最大值就是p_xp\_xp_x只要右端点rrr在 [x, right[x]) 之间([x,r]) 的最大值就是p_xp\_xp_x3. 三部分计数左可见区间数lll有 x-left[x] 种选择rrr只要 x 即可共n−x1n-x1n−x1种cnt_{left} (x - left[x]) * (n - x 1)右可见区间数rrr有 right[x]-x 种选择lll只要 x 即可共xxx种cnt_{right} x * (right[x] - x)同时左右可见等价于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我们可以按值从大到小处理每个元素预处理pos[v]记录值为vvv的元素的下标初始化 set插入哨兵0和(n1)避免边界判断从nnn到111遍历值vvv当前下标 x pos[v]此时 set 中已经插入了所有值大于v的元素的下标用se.upper_bound(x)找到第一个大于x的下标 → 就是right[x]对该迭代器用prev得到第一个小于x的下标 → 就是left[x]将xxx插入 set供后续更小的值查询正解代码#includebits/stdc.husingnamespacestd;usinglllonglong;voidsolve(){intn;cinn;vectorintp(n1),pos(n1);for(inti1;in;i){cinp[i];pos[p[i]]i;// 记录每个值对应的下标}vectorintleft(n1,0),right(n1,n1);setintse;se.insert(0);// 左哨兵se.insert(n1);// 右哨兵// 按值从大到小处理插入下标查询前驱后继for(intin;i1;i--){intxpos[i];autoitse.upper_bound(x);// 第一个大于x的下标 → 右边第一个更大的right[x]*it;left[x]*prev(it);// 前一个元素 → 左边第一个更大的se.insert(x);}// 容斥计算每个位置的答案for(intx1;xn;x){ll Lleft[x],Rright[x];ll cnt_left(x-L)*1LL*(n-x1);ll cnt_rightx*1LL*(R-x);ll cnt_both(x-L)*1LL*(R-x);ll anscnt_leftcnt_right-cnt_both;coutans \n[xn];}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--)solve();return0;}代码细节说明哨兵设计初始插入0和(n1)保证所有查询都能找到合法的前驱后继无需特判边界。long long 强制转换乘法可能爆int每处乘法都通过1LL强制转为长整型避免溢出。输出优化 \n[x n]是常用技巧最后一个元素输出换行其余输出空格。复杂度分析时间复杂度每个元素插入、查询 set 各一次单次 O(log n)总复杂度 O(nlog n)满足 n5e5 的限制。空间复杂度(O(n))(O(n))(O(n))用于存储数组和 set。样例验证以第一组样例n3, p[2,1,3]为例pos[1]2, pos[2]1, pos[3]3从大到小处理i3x3right[3]4, left[3]0插入3i2x1right[1]3, left[1]0插入1i1x2right[2]3, left[2]1插入2计算得三个位置答案均为3与样例输出一致。本题亮点本题也可用单调栈求左右第一个更大元素但用 set 的有序性 前驱后继查询优雅实现代码更简洁且思路直观是 set 进阶操作的典型应用场景。
算法常见题型之STL set进阶：二分查找与迭代器双向移动
发布时间：2026/7/31 10:16:38
set 进阶用法详解与例题题解一、set 基础回顾与常用操作C STL 中的std::set是基于红黑树实现的有序不重复集合默认按升序排列所有插入、删除、查找操作的时间复杂度均为O(log n)是处理有序集合问题的核心工具。1. 基础定义与初始化#includesetusingnamespacestd;setints;// 默认升序的int集合setint,greaterints2;// 降序排列的int集合setints3(s.begin(),s.end());// 用迭代器区间初始化2. 核心常用操作操作功能时间复杂度s.insert(x)插入元素x重复则不生效O(log n)s.erase(x)删除值为x的元素O(log n)s.erase(it)删除迭代器it指向的元素O(log n)s.find(x)查找x返回迭代器不存在返回s.end()O(log n)s.count(x)返回x的出现次数0或1O(log n)s.size()返回集合元素个数(O(1))(O(1))(O(1))s.empty()判断集合是否为空(O(1))(O(1))(O(1))s.clear()清空集合(O(n))(O(n))(O(n))3. 遍历方式set 只能通过双向迭代器遍历默认按升序输出// 一般遍历for(autoit:s){coutit ;}// 正向遍历for(autoits.begin();it!s.end();it){cout*it ;}// 反向遍历for(autoits.rbegin();it!s.rend();it){cout*it ;}二、set 进阶核心操作set 的真正价值在于有序性带来的二分查询与边界定位能力以下是竞赛与工程中最常用的进阶操作。1. 有序二分查找lower_bound / upper_boundset 自带基于树结构的二分查找是最核心的进阶操作s.lower_bound(x)返回第一个大于等于x的元素的迭代器s.upper_bound(x)返回第一个大于x的元素的迭代器setints{1,3,5,7,9};autoit1s.lower_bound(4);// 指向5第一个4的数autoit2s.upper_bound(5);// 指向7第一个5的数典型场景查找元素的前驱/后继、范围统计、动态插入并维护边界。2. 迭代器双向移动prev / nextset 的迭代器是双向迭代器不支持随机访问不能写it 2必须通过prev和next移动prev(it, k1)返回向前移动k步的迭代器next(it, k1)返回向后移动k步的迭代器setints{1,3,5,7,9};autoits.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的最小值autoits.upper_bound(x);intsuff*it;// 找x的前驱小于x的最大值intpre*prev(it);配合哨兵元素如0和(n1)可以完美处理边界情况无需额外判断。三、进阶例题精讲可见元素子区间计数题目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大的元素下标不存在则为000right[x]xxx右边第一个比p_xp\_xp_x大的元素下标不存在则为(n1)(n1)(n1)这两个值决定了p_xp\_xp_x作为最大值的影响范围只要左端点lll在 (left[x], x] 之间([l,x]) 的最大值就是p_xp\_xp_x只要右端点rrr在 [x, right[x]) 之间([x,r]) 的最大值就是p_xp\_xp_x3. 三部分计数左可见区间数lll有 x-left[x] 种选择rrr只要 x 即可共n−x1n-x1n−x1种cnt_{left} (x - left[x]) * (n - x 1)右可见区间数rrr有 right[x]-x 种选择lll只要 x 即可共xxx种cnt_{right} x * (right[x] - x)同时左右可见等价于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我们可以按值从大到小处理每个元素预处理pos[v]记录值为vvv的元素的下标初始化 set插入哨兵0和(n1)避免边界判断从nnn到111遍历值vvv当前下标 x pos[v]此时 set 中已经插入了所有值大于v的元素的下标用se.upper_bound(x)找到第一个大于x的下标 → 就是right[x]对该迭代器用prev得到第一个小于x的下标 → 就是left[x]将xxx插入 set供后续更小的值查询正解代码#includebits/stdc.husingnamespacestd;usinglllonglong;voidsolve(){intn;cinn;vectorintp(n1),pos(n1);for(inti1;in;i){cinp[i];pos[p[i]]i;// 记录每个值对应的下标}vectorintleft(n1,0),right(n1,n1);setintse;se.insert(0);// 左哨兵se.insert(n1);// 右哨兵// 按值从大到小处理插入下标查询前驱后继for(intin;i1;i--){intxpos[i];autoitse.upper_bound(x);// 第一个大于x的下标 → 右边第一个更大的right[x]*it;left[x]*prev(it);// 前一个元素 → 左边第一个更大的se.insert(x);}// 容斥计算每个位置的答案for(intx1;xn;x){ll Lleft[x],Rright[x];ll cnt_left(x-L)*1LL*(n-x1);ll cnt_rightx*1LL*(R-x);ll cnt_both(x-L)*1LL*(R-x);ll anscnt_leftcnt_right-cnt_both;coutans \n[xn];}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--)solve();return0;}代码细节说明哨兵设计初始插入0和(n1)保证所有查询都能找到合法的前驱后继无需特判边界。long long 强制转换乘法可能爆int每处乘法都通过1LL强制转为长整型避免溢出。输出优化 \n[x n]是常用技巧最后一个元素输出换行其余输出空格。复杂度分析时间复杂度每个元素插入、查询 set 各一次单次 O(log n)总复杂度 O(nlog n)满足 n5e5 的限制。空间复杂度(O(n))(O(n))(O(n))用于存储数组和 set。样例验证以第一组样例n3, p[2,1,3]为例pos[1]2, pos[2]1, pos[3]3从大到小处理i3x3right[3]4, left[3]0插入3i2x1right[1]3, left[1]0插入1i1x2right[2]3, left[2]1插入2计算得三个位置答案均为3与样例输出一致。本题亮点本题也可用单调栈求左右第一个更大元素但用 set 的有序性 前驱后继查询优雅实现代码更简洁且思路直观是 set 进阶操作的典型应用场景。
