小红的中位数查询（easy）【牛客tracker 每日一题】

小红的中位数查询easy时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述easy 版本中所有的r−l1都相等而 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≤1051 ≤ a i ≤ 10 9 1≤a_i≤10^91≤ai​≤1091 ≤ l i ≤ r i ≤ n 1≤l_i≤r_i≤n1≤li​≤ri​≤n保证所有的r i − l i 1 r_i−l_i1ri​−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. 算法实现对顶堆维护DM结构体L大根堆multisetll, greaterll存较小的一半R小根堆multisetll存较大的一半。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顶并转整型即可。莫队离线处理分块大小len sqrt(n)。询问结构体node含l, r, id按莫队分块排序先按l所在块编号升序同一块内按r排序若块编号为奇数则r升序偶数则r降序奇偶排序优化常数。初始化左右指针l1, r0遍历排序后的询问移动指针时调用dm.add或dm.del维护对顶堆。每完成一个询问记录答案ans[id] (ll)dm.getv()。输出答案按输入顺序输出各询问的中位数。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((nq)\sqrt{n}\log n)O((nq)n​logn)在n , q ≤ 10 5 n,q \le 10^5n,q≤105下可通过。空间复杂度O ( n q ) O(nq)O(nq)存储原数组和询问。总结用对顶堆动态维护中位数结合莫队算法离线处理区间查询将排序复杂度均摊到指针移动上。easy 版本区间长度相等但此通用解法同样适用且高效。代码简要说明DM结构体封装对顶堆逻辑支持添加、删除、平衡及获取中位数。莫队排序定义node结构体含l, r, id按块排序并奇偶优化。主流程读入n , q n,qn,q及数组a aa。读入所有询问记录id。对询问排序初始化l1, r0。遍历排序后的询问移动指针并调用add/del存入答案。按原顺序输出所有答案。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll len;structDM{multisetll,greaterllL;multisetllR;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()){autoitL.find(x);if(it!L.end())L.erase(it);}else{autoitR.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(constnodea)const{if(l/len!a.l/len)returnla.l;if((l/len)1)returnra.r;returnra.r;}};intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,q;cinnq;lensqrt(n);vectorlla(n1);for(ll i1;in;i)cina[i];DM dm;vectornodequery(q);for(ll i0;iq;i){cinquery[i].lquery[i].r;query[i].idi;}sort(query.begin(),query.end());vectorllans(q);for(ll i0,l1,r0;iq;i){auto[id,L,R]query[i];while(lL)dm.add(a[--l]);while(rR)dm.add(a[r]);while(lL)dm.del(a[l]);while(rR)dm.del(a[r--]);ans[id](ll)dm.getv();}for(ll i0;iq;i)coutans[i]\n;return0;}