2021 中庸之道
http://codevs.cn/problem/2021/
题目描述 Description
给定一个长度为N的序列,有Q次询问,每次询问区间[L,R]的中位数。
数据保证序列中任意两个数不相同,且询问的所有区间长度为奇数。
输入描述 Input Description
第一行为N,Q。
第二行N个数表示序列。
接下来Q行,每行为L,R,表示一次询问。
输出描述 Output Description
输出Q行,对应每次询问的中位数。
样例输入 Sample Input
5 3
1 4 8 16 2
1 5
3 5
3 3
样例输出 Sample Output
4
8
8
数据范围及提示 Data Size & Hint
40%的数据,N,Q≤100;
70%的数据,N≤100;
100%的数据,N≤1000,Q≤100000,序列中的元素为1到10^9之间的整数。
套上主席树求第K大模板
区间[l,r]中位数转化:k=(r-l)/2+1
例:[5,9]中位数是第7个,k=(9-5)/2+1=3,是第3大
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 100001
using namespace std;
int n,m,l_child[N*],r_child[N*],root[N],sum[N*],tot,id;
int a[N],has[N];
int x,y,k,ans,T;
void build(int pre,int &now,int key,int l,int r)
{
sum[now=++id]=sum[pre]+;
if(l==r) return;
int mid=(l+r)/;
if(key<=mid)
{
r_child[now]=r_child[pre];
build(l_child[pre],l_child[now],key,l,mid);
}
else
{
l_child[now]=l_child[pre];
build(r_child[pre],r_child[now],key,mid+,r);
}
}
void discrete()
{
sort(a+,a+n+);
tot=unique(a+,a+n+)-(a+);
for(int i=;i<=n;i++) has[i]=lower_bound(a+,a+tot+,has[i])-a;
}
int search(int s,int t,int k,int l,int r)
{
if(l==r) return l;
int tmp=sum[l_child[t]]-sum[l_child[s]];
int mid=(l+r)/;
if(tmp>=k) return search(l_child[s],l_child[t],k,l,mid);
else return search(r_child[s],r_child[t],k-tmp,mid+,r);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]),has[i]=a[i];
discrete();
for(int i=;i<=n;i++) build(root[i-],root[i],has[i],,tot);
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
k=(y-x)/+;//转化
ans=search(root[x-],root[y],k,,tot);
printf("%d\n",a[ans]);
}
}