题解：P1168 中位数
无名之雾
·
·
题解
大家好，我是个毒瘤，我非常喜欢暴力数据结构，于是我就用分块过了这个题。
题意转换
求前 n 个的数字的中位数不难转换为求区间第 k 大问题。其中 k=n/2+1。
思路
我们维护两个数组，$cnt1_{i,j}$ 表示前 $i$ 个数列块中第 $j$ 个值域块中数字出现的次数和，$cnt2_{i,j}$ 表示前 $i$ 个数列块中第 $j$ 这个数字出现的次数。
接下来进行查询：
- 对于每个散块。我们暴力维护 $ans1$ 与 $ans2$ 这两个数组来记录散块中的信息。
- 对于整块，直接从头开始扫值域块。累加每个块的 $ans1$ 至 $cnt1$ 数组已确定第 $k$ 大在那个值域块里。然后通过 $ans2$ 与 $cnt2$ 两个数组扫一遍确定答案。
## 实现
注意不要开 `long long` 同时数组不要开太大，不然 MLE。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline void write(int x){
if(x==0){putchar('0');return;}
int len=0,k1=x,c[10005];
if(k1<0)k1=-k1,putchar('-');
while(k1)c[len++]=k1%10+'0',k1/=10;
while(len--)putchar(c[len]);
}
const int N=1e5+5;
int block,block2;
int nw[N],a[N],pos[N],pos2[N],cnt1[400][400],cnt2[400][N],z[N],o;
int ans[400],ans2[N];
int ask(int x,int y,int k) {
int res=0,pd=0;
for(int i=x;i<=min(y,pos[x]*block);i++)ans[pos2[nw[i]]]++,ans2[nw[i]]++;
if(pos[x]!=pos[y]){
for(int i=(pos[y]-1)*block+1;i<=y;i++)ans[pos2[nw[i]]]++,ans2[nw[i]]++;
}
for(int i=1;i<=pos2[o];i++){
int ld=cnt1[pos[y]-1][i]-cnt1[pos[x]][i];
if(ld<0)ld=0;
if(res+(ld+ans[i])<k){
res+=ans[i];
if(cnt1[pos[y]-1][i]-cnt1[pos[x]][i]>0)res+=cnt1[pos[y]-1][i]-cnt1[pos[x]][i];
}
else{
pd=i;
break;
}
}
int anss=-1;
for(int i=(pd-1)*block2+1;i<=pd*block2;i++){
res+=ans2[i];
if(cnt2[pos[y]-1][i]-cnt2[pos[x]][i]>0)res+=cnt2[pos[y]-1][i]-cnt2[pos[x]][i];
if(res>=k){
anss=z[i];
break;
}
}
for(int i=x;i<=min(y,pos[x]*block);i++)ans[pos2[nw[i]]]--,ans2[nw[i]]--;
if(pos[x]!=pos[y]){
for(int i=(pos[y]-1)*block+1;i<=y;i++)ans[pos2[nw[i]]]--, ans2[nw[i]]--;
}
return anss;
}
signed main() {
int n=read();
block=sqrt(n);
for(int i=1;i<=n;i++){
a[i]=read();
pos[i]=(i-1)/block+1;
z[++o]=a[i];
}
sort(z+1,z+o+1);
o=unique(z+1,z+o+1)-z-1;
block2=sqrt(o);
for(int i=1;i<=o;i++)pos2[i]=(i-1)/block2+1;
for(int i=1;i<=n;i++){
nw[i]=lower_bound(z+1,z+o+1,a[i])-z;
cnt1[pos[i]][pos2[nw[i]]]++;
cnt2[pos[i]][nw[i]]++;
}
for(int i=1;i<=pos[n];i++){
for(int j=1;j<=pos2[o];j++){
cnt1[i][j]+=cnt1[i-1][j];
}
for(int j=1;j<=o;j++){
cnt2[i][j]+=cnt2[i-1][j];
}
}
for(int i=1;i<=n;i+=2){
write(ask(1,i,i/2+1));
puts("");
}
return 0;
}
```