链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

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

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

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

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

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

输入描述:

第一行输入两个正整数n,qn,qn,q，代表数组大小、询问次数。
第二行输入nnn个正整数aia_iai​，代表小红拿到的数组。
接下来的qqq行，每行输入两个正整数li,ril_i,r_ili​,ri​，代表一次询问。
1≤n,q≤1051\leq n,q \leq 10^51≤n,q≤105
1≤ai≤1091\leq a_i \leq 10^91≤ai​≤109
1≤li≤ri≤n1\leq l_i \leq r_i \leq n1≤li​≤ri​≤n
保证所有的ri−li+1r_i-l_i+1ri​−li​+1为奇数，且都相等。

输出描述:

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

示例1

输入

复制5 2 2 1 4 3 3 1 3 2 4

5 2
2 1 4 3 3
1 3
2 4

输出

复制2 3

2
3

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q,a[N],ans[N];
vector<int> v;
pair<int,int> p[N];
int main(){cin.tie(0);ios::sync_with_stdio(0);cin>>n>>q;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=q;i++) cin>>p[i].first>>p[i].second;int len=p[1].second-p[1].first+1;for(int i=1;i<=n;i++){v.insert(lower_bound(v.begin(),v.end(),a[i]),a[i]);//保证了长度为len的区间是有序的，从而取中间值求平均数if(v.size()==len){int id=len/2;ans[i]=v[id];v.erase(lower_bound(v.begin(),v.end(),a[i-len+1]));}}for(int i=1;i<=q;i++){cout<<ans[p[i].second]<<endl;}
}