洛谷 P3871 [TJOI2010]中位数 题解【堆】【线段树】

作者: wjyyy 分类: ,线段树,解题报告 发布时间: 2018-06-13 17:28

点击量: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:
6
1 2 13 14 15 16
5
add 5
add 3
mid
add 20
mid
输出样例#1:
5
13

说明

对于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)]);
        }
    }
}

 

说点什么

avatar
  Subscribe  
提醒
/* */