企业官网建设流程全解析

小红的中位数查询（easy）

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

easy 版本中，所有的r−l+1都相等，而 hard 版本中没有此限制。通过 easy 版本可以获得 250 分，通过 hard 版本可以获得 50 分。

小红拿到了一个数组，她有若干次询问，每次询问一个区间，她希望你输出该区间的中位数是多少。

保证区间的元素数量为奇数。

在本难度中，保证所有区间的长度都相等。

区间中位数的定义：将区间所有元素从小到大排序后、最中间的那个数。例如[ 2 , 1 , 4 ] [2,1,4][2,1,4]的中位数是2 22，[ 2 , 1 , 4 , 3 , 3 ] [2,1,4,3,3][2,1,4,3,3]的中位数是3 33。

输入描述：

第一行输入两个正整数n , q n,qn,q，代表数组大小、询问次数。
第二行输入n nn正整数a i a_iai​​，代表小红拿到的数组。
接下来的q qq行，每行输入两个正整数l i , r i l_i,r_ili​,ri​​，代表一次询问。
1 ≤ n , q ≤ 10 5 1≤n,q≤10^51≤n,q≤105
1 ≤ a i ≤ 10 9 1≤a_i≤10^91≤ai​≤109
1 ≤ l i ≤ r i ≤ n 1≤l_i≤r_i≤n1≤li​≤ri​≤n
保证所有的r i − l i + 1 r_i−l_i+1ri​−li​+1为奇数，且都相等。

输出描述：

输出q qq行，每行输出一个正整数，代表询问的结果。

示例1

输入：

5 2 2 1 4 3 3 1 3 2 4

输出：

2 3

解题思路

本题是动态区间中位数查询问题，easy 版本保证所有查询区间长度相等且为奇数。采用对顶堆在线维护中位数，结合莫队算法离线处理多个区间查询，避免对每个区间重新排序。

1. 问题等价转化

• 中位数定义：长度为奇数的区间，中位数即排序后正中间的数。
• 动态中位数维护：使用对顶堆结构。一个大根堆L存放较小的一半数，一个小根堆R存放较大的一半数。若元素总数为奇数，约定L比R多一个元素，此时中位数就是L的堆顶；若元素总数为偶数，中位数为两堆顶的平均值。本题区间长度全为奇数，故中位数总为L的堆顶。
• 多区间查询处理：有q qq次询问，每次给定[ l , r ] [l, r][l,r]，如果每次单独计算中位数代价过高。利用莫队算法将所有询问离线，通过左右指针在数组上的移动，动态地往对顶堆中添加或删除元素，快速得到每个询问的中位数。

2. 算法实现

1. 对顶堆维护（DM结构体）：

   • L：大根堆（multiset<ll, greater<ll>>），存较小的一半；
   • R：小根堆（multiset<ll>），存较大的一半。
   • add(x)：若L为空或x ≤ L的堆顶，插入L，否则插入R，然后调用update()。
   • del(x)：判断x属于L还是R，删除对应元素，调用update()。
   • update()：调整L与R的大小，确保L.size() == R.size()或L.size() == R.size() + 1。若L过多，将L顶移到R；若L少于R，将R顶移到L。
   • getv()：若L与R大小不等，中位数为*L.begin()；否则为两堆顶均值（本题用不到偶数情况，直接取L顶并转整型即可）。

2. 莫队离线处理：

   • 分块大小len = sqrt(n)。
   • 询问结构体node含l, r, id，按莫队分块排序：先按l所在块编号升序，同一块内按r排序，若块编号为奇数则r升序，偶数则r降序（奇偶排序优化常数）。
   • 初始化左右指针l=1, r=0，遍历排序后的询问，移动指针时调用dm.add或dm.del维护对顶堆。
   • 每完成一个询问，记录答案ans[id] = (ll)dm.getv()。

3. 输出答案：按输入顺序输出各询问的中位数。

3. 复杂度分析

• 时间复杂度：莫队部分指针移动总次数O ( n q ) O(n\sqrt{q})O(nq​)（或O ( n n ) O(n\sqrt{n})O(nn​)），每次add/del操作涉及multiset的插入/删除，复杂度O ( log ⁡ n ) O(\log n)O(logn)。总复杂度O ( ( n + q ) n log ⁡ n ) O((n+q)\sqrt{n}\log n)O((n+q)n​logn)，在n , q ≤ 10 5 n,q \le 10^5n,q≤105下可通过。
• 空间复杂度：O ( n + q ) O(n+q)O(n+q)存储原数组和询问。

总结

用对顶堆动态维护中位数，结合莫队算法离线处理区间查询，将排序复杂度均摊到指针移动上。easy 版本区间长度相等，但此通用解法同样适用且高效。

代码简要说明

1. DM结构体：封装对顶堆逻辑，支持添加、删除、平衡及获取中位数。
2. 莫队排序：定义node结构体含l, r, id，按块排序并奇偶优化。
3. 主流程：
   • 读入n , q n,qn,q及数组a aa。
   • 读入所有询问，记录id。
   • 对询问排序，初始化l=1, r=0。
   • 遍历排序后的询问，移动指针并调用add/del，存入答案。
   • 按原顺序输出所有答案。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll len;structDM{multiset<ll,greater<ll>>L;multiset<ll>R;voidupdate(){if(L.size()>R.size()+1){ll top=*L.begin();L.erase(L.begin());R.insert(top);}if(L.size()<R.size()){ll top=*R.begin();R.erase(R.begin());L.insert(top);}}voidadd(ll x){if(L.empty()||x<=*L.begin())L.insert(x);elseR.insert(x);update();}voiddel(ll x){if(x<=*L.begin()){autoit=L.find(x);if(it!=L.end())L.erase(it);}else{autoit=R.find(x);if(it!=R.end())R.erase(it);}update();}doublegetv(){if(L.size()!=R.size())return*L.begin();elsereturn(*L.begin()+*R.begin())/2.0;}};structnode{ll id;ll l,r;booloperator<(constnode&a)const{if(l/len!=a.l/len)returnl<a.l;if((l/len)&1)returnr<a.r;returnr>a.r;}};intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,q;cin>>n>>q;len=sqrt(n);vector<ll>a(n+1);for(ll i=1;i<=n;i++)cin>>a[i];DM dm;vector<node>query(q);for(ll i=0;i<q;i++){cin>>query[i].l>>query[i].r;query[i].id=i;}sort(query.begin(),query.end());vector<ll>ans(q);for(ll i=0,l=1,r=0;i<q;i++){auto[id,L,R]=query[i];while(l>L)dm.add(a[--l]);while(r<R)dm.add(a[++r]);while(l<L)dm.del(a[l++]);while(r>R)dm.del(a[r--]);ans[id]=(ll)dm.getv();}for(ll i=0;i<q;i++)cout<<ans[i]<<"\n";return0;}