题解 P3871 【[TJOI2010]中位数】

· · 题解

前铺

虽然刚学普通平衡树，但刷了这么多题后，发现用平衡树解的题目方法就一个字：套！如何套呢？我总结了些步骤：

1、分析：看清题目找到题目所要求的的平衡树的哪个操作。

2、修改：在模板上加以修改。

今天我就拿这道题来实地演练一下。

PS：如果你还不会普通平衡树，请出门左转 luogu P3369。

分析

首先，题目说有 add 添加一个整数，那么显然我们需要插入操作。在看到 mid 的从小到大，我们肯定要进行排序，然后题目让我们求中位数，和为中位数？

中位数是指将一个序列按照从小到大排序后处在中间位置的数。（若序列长度为偶数，则指处在中间位置的两个数中较小的那个）

说白了在代码里就是第 （序列长度+1）/2 个数 。那我们就需要求出排名为第 （序列长度+1）/2 个数输出即可。

修改

对于板子来说并没有太多的修改只需保留插入、排序、查询第 x 大的数即可。

总结

本题如果用平衡树解那重点也就只有将中位数这个概念转化成第 (n+1)/2 个大的数。

完整代码

#include<stdio.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

const int N=1e5+86+3e4;

int n,m,tot,root;//tot即为当前序列长度

struct Treap
{
    Treap()
    {
        pri=rand()*rand()%20061124;
        l=r=0;
    }//构造函数初始化
    int l;
    int r;
    int pri;
    int v;
    int siz;
}t[N];

void up(int x)//维护节点个数
{
    t[x].siz=t[t[x].l].siz+t[t[x].r].siz+1;
}

void right_rorate(int &x)//右旋
{
    int tmp=t[x].l;
    t[x].l=t[tmp].r;
    t[tmp].r=x;
    t[tmp].siz=t[x].siz;
    up(x);
    x=tmp;
 } 

void left_rorate(int &x)//左旋
{
    int tmp=t[x].r;
    t[x].r=t[tmp].l;
    t[tmp].l=x;
    t[tmp].siz=t[x].siz;
    up(x);
    x=tmp;
}

int add(int v)//添加操作
{
    t[++tot].v=v;
    t[tot].siz=1;
    return tot;
}

void insert(int &x,int v)//插入操作
{
    if(x==0)
    {
        x=add(v);
        return;
    }
    t[x].siz++;
    if(v>=t[x].v)
        insert(t[x].r,v);
    else
        insert(t[x].l,v);
    if(t[x].l&&t[x].pri>t[t[x].l].pri)
        right_rorate(x);
    if(t[x].r&&t[x].pri>t[t[x].r].pri)
        left_rorate(x);
    up(x);  
}

int find(int x,int rnk)//查询操作
{
    if(rnk==t[t[x].r].siz+1)
        return t[x].v;
    if(rnk>t[t[x].r].siz+1)
        return find(t[x].l,rnk-t[t[x].r].siz-1);
    return find(t[x].r,rnk);
}

int main()
{
    scanf("%d",&n);
    int a;
    char s[3];
    while(n--)
    {
        scanf("%d",&a);
        insert(root,a);
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='a')
        {
            scanf("%d",&a);
            insert(root,a);
        }
        else if(s[0]=='m')
            printf("%d\n",find(root,(tot+1)/2));//转化中位数概念
    }
    return 0;
}

希望对大家有所帮助！