[LUOGU] P3871 [TJOI2010]中位数

题目描述

给定一个由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秒

Splay,kth

#include<iostream>

#include<cstdio>

using namespace std;

inline int rd() {

    int ret=0,f=1;

    char c;

    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;

    while(isdigit(c))ret=ret*10+c-'0',c=getchar();

    return ret*f;

}

const int MAXN=1000005;

int num;

int val[MAXN],cnt[MAXN],siz[MAXN];

int ch[MAXN][2],fa[MAXN];

int root,tot;

inline int newnode(int x){num++;val[++tot]=x;cnt[tot]=siz[tot]=1;return tot;}

inline bool check(int x){return x==ch[fa[x]][1];}

inline void pushup(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];}

void rotate(int x){

    int y=fa[x],z=fa[fa[x]];

    bool ck=check(x);

    fa[ch[x][ck^1]]=y;ch[y][ck]=ch[x][ck^1];

    ch[x][ck^1]=y;fa[y]=x;fa[x]=z;

    if(z) ch[z][ch[z][1]==y]=x;

    pushup(y);pushup(x);

}

void splay(int x){

    for(int f=fa[x];f;rotate(x),f=fa[x])

        if(fa[f]) rotate(check(x)==check(f)?f:x);

    root=x;

}

void insert(int x){

    if(!root){root=newnode(x);return;}

    int cur=root,f=0;

    while(1){

        if(val[cur]==x){num++;cnt[cur]++;pushup(cur);pushup(f);splay(cur);return;}

        f=cur;cur=ch[cur][x>val[cur]];

        if(!cur){cur=newnode(x);fa[cur]=f;ch[f][x>val[f]]=cur;pushup(f);splay(cur);return;}

    }

}

int kth(int x){

    int cur=root;

    while(1){

        if(x<=siz[ch[cur][0]]) cur=ch[cur][0];

        else{

            x-=siz[ch[cur][0]]+cnt[cur];

            if(x<=0) return val[cur];

            cur=ch[cur][1];

        }

    }

}

int n,m;

int main(){

    n=rd();

    for(int i=1;i<=n;i++) insert(rd());

    m=rd();

    char s[10];

    for(int i=1;i<=m;i++){

        scanf("%s",s);

        if(s[0]=='a') insert(rd());

        else printf("%d\n",kth((num+1)/2));

    }

    return 0;

}

巴特西

[LUOGU] P3871 [TJOI2010]中位数

最新文章

热门文章