M_sea

洛谷3871 [TJOI2010]中位数
Luogu分析要求中位数就要对数据排序。维护一颗平衡树,资瓷插入和求中位数这两个操作。求中位数可以视为求第$k$大...
扫描右侧二维码阅读全文
01
2018/11

洛谷3871 [TJOI2010]中位数

Luogu

分析

要求中位数就要对数据排序。

维护一颗平衡树,资瓷插入和求中位数这两个操作。

求中位数可以视为求第$k$大,这里的$k=\frac{size[root]+1}{2}$

然后就可以用平衡树氵过去了。

用的是fhq treap,慢的很。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=110000+10;

struct fhq_treap {
    int ch[MAXN][2];
    int sz[MAXN],val[MAXN],rnd[MAXN];
    int root,cnt;
    fhq_treap() { this->root=this->cnt=0; }
    inline void init() { root=cnt=0; }
    inline int new_node(int x) { sz[++cnt]=1,val[cnt]=x,rnd[cnt]=rand(); return cnt; }
    inline void pushup(int o) { sz[o]=sz[ch[o][0]]+sz[ch[o][1]]+1; }
    inline void split(int now,int k,int& x,int& y) {
        if (!now) { x=y=0; return; }
        if (val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y);
        else y=now,split(ch[now][0],k,x,ch[now][0]);
        pushup(now);
    }
    inline int merge(int A,int B) {
        if (!A||!B) return A+B;
        if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B); pushup(A); return A; }
        else { ch[B][0]=merge(A,ch[B][0]); pushup(B); return B; }
    }
    inline int kth(int k) {
        int now=root;
        while (1) {
            if (k<=sz[ch[now][0]]) now=ch[now][0];
            else if (k==sz[ch[now][0]]+1) return now;
            else k-=sz[ch[now][0]]+1,now=ch[now][1];
        }
    }
    inline void insert(int k) {
        int x,y; split(root,k,x,y);
        root=merge(merge(x,new_node(k)),y);
    }
    inline int getMid() {
        return val[kth((sz[root]+1)/2)];
    }
} T;

char op[256];

int main() {
    int n=read(); T.init();
    for (re int i=1;i<=n;++i) T.insert(read());
    int m=read();
    while (m--) {
        scanf("%s",op+1);
        if (op[1]=='a') {
            int k=read();
            T.insert(k);
        }
        else if (op[1]=='m') printf("%d\n",T.getMid());
    }
    return 0;
}
最后修改:2018 年 11 月 09 日 06 : 50 PM

发表评论