题解 P1168 【中位数】
lonely_log · · 题解
权值树状数组+二分查找+离散化
C++
1.部分分的想法，就是用类似通排的方法，用一个数组k，每次在k[a[i]]和k[a[i-1]]加1，然后从下标1开始往后扫，当扫到的数的个数是序列的“中位数”就输出。（当然因为a[i]太大而且最多100000个数所以我们要离散一下）
2.这种想法可以改一下，就是用一个前缀和+二分查找（前缀和数组sum），sum[i]表式小于等于i的数有多少个。二分时当sum[mid]大于等于(想一想为什么要等于）“中位数”，上界缩小。反之，下界缩小。因为k[a[i]]不是一次性加完（就是在线），所以前缀和数组每次都要更改，很费时间。
3.诶！！前缀和数组要更改！不就是线段树或树状数组吗！我们可以将前缀和数组更改的部分换成树状数组（这里只需要单点修改和区间查询，所以树状数组就够了）。
于是我们就十分愉快地得出了正解！！！
如果不是很理解“中位数”可以看一下代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<math>
#include<cstring>
using namespace std;
const int N=100005;
struct asd
{
int id,val;
}z[N];
bool cmp(asd a,asd b)
{
return a.val<b.val;
}
int a[N],b[N],c[N],n;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int val)//单点修改
{
while(x<=n)
{
c[x]+=val;
x+=lowbit(x);
}
}
int getsum(int x)//区间查询
{
int s=0;
while(x)
{
s+=c[x];
x-=lowbit(x);
}
return s;
}
int Find(int x)//二分查找
{
int l=1,r=n,mid;
while(l<=r)
{
mid=(l+r)>>1;//这个写法等价于mid=(l+r)/2，老师说用位运算比较有逼格 :D
int s=getsum(mid);//小于等于mid的数的个数
if(s>=x/2+1)r=mid-1;//个数大于等于“中位数”，上界缩小（x是要求中位数的序列的长度）
else l=mid+1;//反之，下界缩小
}
return b[l];
}
void Disc()//离散化
{
sort(z+1,z+n+1,cmp);//按照值的大小排序，相等也无所谓
for(int i=1;i<=n;i++)
{
a[z[i].id]=i;//z[i].id是这个数在未排序的序列中的编号，用i替换原来的值
b[i]=z[i].val;//b[i]表示的是离散后的数值为i的数的真实值
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&z[i].val);
z[i].id=i;
}
Disc(); //离散化
cout<<b[a[1]]<<endl;
add(a[1],1);
for(int i=3;i<=n;i+=2)
{
add(a[i],1);//在a[i]位加一
add(a[i-1],1);//在a[i-1]位加一
printf("%d\n",Find(i));//二分查找
}
return 0;
}