洛谷 P3871 [TJOI2010]中位数 题解【堆】【线段树】
点击量:172
看到这个题的第一眼我想的是线段树,不过这个题更优的解法是堆(对顶堆),两种解法都实现了一下。
题目描述
给定一个由N个元素组成的整数序列,现在有两种操作:
1 add a
在该序列的最后添加一个整数a,组成长度为N + 1的整数序列
2 mid 输出当前序列的中位数
中位数是指将一个序列按照从小到大排序后处在中间位置的数。(若序列长度为偶数,则指处在中间位置的两个数中较小的那个)
例1:1 2 13 14 15 16 中位数为13
例2:1 3 5 7 10 11 17 中位数为7
例3:1 1 1 2 3 中位数为1
输入输出格式
输入格式:
第一行为初始序列长度N。第二行为N个整数,表示整数序列,数字之间用空格分隔。第三行为操作数M,即要进行M次操作。下面为M行,每行输入格式如题意所述。
输出格式:
对于每个mid操作输出中位数的值
输入输出样例
输入样例#1:61 2 13 14 15 165add 5add 3midadd 20mid输出样例#1:513说明
对于30%的数据,1 ≤ N ≤ 10,000,0 ≤ M ≤ 1,000
对于100%的数据,1 ≤ N ≤ 100,000,0 ≤ M ≤ 10,000
序列中整数的绝对值不超过1,000,000,000,序列中的数可能有重复
每个测试点时限1秒
很容易就看得出来,我们对于每次询问要找到第$ \lfloor \frac{n+1}{2} \rfloor $小的数作为中位数。我们只需要把所有数据读入,然后离散化,就可以用线段树来维护了。(实际上splay更优但是我还写不好TAT)
我们介绍一下堆的做法。我们需要一个大根堆,一个小根堆,小的数优先插入到大根堆里去。如果一个数比大根堆的堆顶要小,就把它插入大根堆中去,否则插入小根堆。这样使得大根堆里所有的数小于等于小根堆里所有的数,如果只改变大小根堆的堆顶,这个性质依然不会改变。我们要做的是维护两个堆平衡,也就是小根堆的数的个数与大根堆的数的个数最多相差1,这样方便我们找中位数。
查询时,我们要调整两个堆,使得大根堆的数的个数不小于小根堆。当数的总数为奇数时,此时大根堆的数的个数会比小根堆多1,输出大根堆堆顶的元素即可;当数的个数为奇数时,两个堆数的个数相等,按照题目要求,同样输出大根堆的堆顶。
堆版Code:(偷懒用的STL)
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int> q1;//大根堆
priority_queue<int,vector<int>,greater<int> > q2;
int cnt[3];
void q1toq2()
{
int k=q1.top();
q1.pop();
cnt[1]--;
q2.push(k);
cnt[2]++;
return;
}
void q2toq1()
{
int k=q2.top();
q2.pop();
cnt[2]--;
q1.push(k);
cnt[1]++;
return;
}
void add(int x)
{
int k;
if(!q1.empty())
k=q1.top();
if(q1.empty()||x<=k)
{
q1.push(x);
cnt[1]++;
}
else
{
q2.push(x);
cnt[2]++;
}
while(cnt[1]-cnt[2]>=2)
q1toq2();
while(cnt[2]-cnt[1]>=2)
q2toq1();
}
int n;
void ask()
{
int t=n+1>>1;
while(cnt[1]<t)
q2toq1();
while(cnt[1]>t)
q1toq2();
int k=q1.top();
printf("%d\n",k);
return;
}
int main()
{
int a;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
add(a);
}
int m;
char s[123];
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",s);
if(s[0]=='a')
{
n++;
scanf("%d",&a);
add(a);
}
else
ask();
}
return 0;
}
线段树Code:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
using std::sort;
struct node
{
int l,r,v,lazy;
node(int l,int r,int v)
{
this->l=l;
this->r=r;
this->v=v;
lazy=0;
}
node(){lazy=0;}
}t[500000];
struct Has
{
int a,b,c;//a是原来的值,b是原来的位置,c是hash值
friend bool operator <(Has x,Has y)
{
return x.a<y.a;
}
}b[120000];
bool cmp(Has x,Has y)
{
return x.b<y.b;
}
int a[120000],g[120000];
int re[120000];
int typ[12000];
void build(int k,int l,int r)
{
t[k].l=l;
t[k].r=r;
if(l==r)
{
t[k].v=g[l];
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
t[k].v=t[ls].v+t[rs].v;
return;
}
void pushdown(int k)
{
t[k].v+=t[k].lazy*(t[k].r-t[k].l+1);
if(t[k].l==t[k].r)
{
t[k].lazy=0;
return;
}
t[ls].lazy+=t[k].lazy;
t[rs].lazy+=t[k].lazy;
t[k].lazy=0;
}
void change(int k,int l,int r,int x)
{
pushdown(k);
if(t[k].l==l&&t[k].r==r)
{
t[k].lazy+=x;
return;
}
t[k].v+=x*(r-l+1);
if(l>Mid)
change(rs,l,r,x);
else if(r<=Mid)
change(ls,l,r,x);
else
{
change(ls,l,mid,x);
change(rs,mid+1,r,x);
}
return;
}
int Ask(int k,int x)
{
pushdown(k);
if(t[k].l==t[k].r)
//if(x<=t[k].v)
return t[k].l;
pushdown(ls);
pushdown(rs);
if(t[ls].v>=x)
return Ask(ls,x);
else
return Ask(rs,x-t[ls].v);
}
int main()
{
memset(g,0,sizeof(g));//基于g做线段树
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i].a=a[i];
b[i].b=i;
}
int cnt=n;
scanf("%d",&m);
char s[123];
for(int i=1;i<=m;i++)
{
scanf("%s",s);
if(s[0]=='a')
{
scanf("%d",&a[++cnt]);
b[cnt].a=a[cnt];
b[cnt].b=cnt;
typ[i]=1;
}
else
typ[i]=2;
}
sort(b+1,b+cnt+1);
int indx=0;
b[0].a=-0x7fffffff;
for(int i=1;i<=cnt;i++)
if(b[i].a==b[i-1].a)
b[i].c=b[i-1].c;
else
{
b[i].c=++indx;
re[indx]=b[i].a;
}
sort(b+1,b+cnt+1,cmp);//排回来
for(int i=1;i<=n;i++)
g[b[i].c]++;
build(1,1,cnt);
cnt=n;//当前数的个数
int middle;
for(int i=1;i<=m;i++)
{
if(typ[i]==1)
{
cnt++;
change(1,b[cnt].c,b[cnt].c,1);
}
else
{
middle=(cnt+1)>>1;
printf("%d\n",re[Ask(1,middle)]);
}
}
}
说点什么