洛谷P3871 [TJOI2010]中位数(splay)

题目描述

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

这题不是随便做么。。

口胡一下我能想到的做法吧，，

1.$M < 10000$的话vector暴力插入不知道能不能A，

2.直接用平衡树，我写的是splay，不想写代码的话可以用pb_ds里维护了siz域的红黑树

3.先离线，对权值离散化，然后用权值线段树查。

4.沿用https://www.luogu.org/problemnew/show/P1801这道题的做法

#include<cstdio>

using namespace std;

const int MAXN = 1e6 + ;

#define ls(x) ch[x][0]

#define rs(x) ch[x][1]

#define root  ch[0][1]

int fa[MAXN], val[MAXN], rev[MAXN], siz[MAXN], ch[MAXN][], tot = ;

bool ident(int x) {

    return ch[fa[x]][] == x ?  : ;

}

void connect(int x, int _fa, int opt) {

    fa[x] = _fa, ch[fa[x]][opt] = x;

}

void update(int x) {

    siz[x] = siz[ls(x)] + siz[rs(x)] + rev[x];

}

void rotate(int x) {

    int Y = fa[x], R = fa[Y];

    int Yson = ident(x), Rson = ident(Y);

    int B = ch[x][Yson ^ ];

    connect(B, Y, Yson);

    connect(x, R, Rson);

    connect(Y, x, Yson ^ );

    //tag

    update(Y); update(x);

}

void splay(int x, int to) {

    to = fa[to];

    while(fa[x] != to) {

        int y = fa[x];

        if(fa[y] == to) rotate(x);

        else if(ident(x) == ident(y)) rotate(y), rotate(x);

        else rotate(x), rotate(x);

    }

}

int NewNode(int _fa, int _val) {

    val[++tot] = _val;

    fa[tot] = _fa;

    siz[tot] = rev[tot] = ;

    return tot;

}

void insert(int x) {

    if(!root) {root = NewNode(, x); return ;}

    int now = root;

    while(now) {

        siz[now]++;

        if(val[now] == x) {rev[now]++; return ;}

        int nxt = val[now] < x;

        if(!ch[now][nxt]) {ch[now][nxt] = NewNode(now, x); splay(ch[now][nxt], root); return ;}

        now = ch[now][nxt];

    }

}

int ARank(int x) {

    int now = root;

    while(now) {

        //if(siz[now] == x) return val[now];

        int used = siz[now] - siz[rs(now)];

        if(x > siz[ls(now)] && x <= used) return val[now];

        if(used < x) x = x - used, now = ch[now][];

        else now = ch[now][];

    }

}

char opt[];

int main() {

#ifdef WIN32

    freopen("a.in", "r", stdin);

#endif

    int N;

    scanf("%d", &N);

    for(int i = ; i <= N; i++) {

        int x; scanf("%d", &x);

        insert(x);

    }

    int Q;

    scanf("%d", &Q);

    while(Q--) {

        scanf("%s", opt + );

        if(opt[] == 'a') {

            int x;

            scanf("%d", &x);

            insert(x); N++;

        }

        else

            printf("%d\n", ARank(N /  + (N & )));

    }

    return ;

}

巴特西

洛谷P3871 [TJOI2010]中位数(splay)

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章