洛谷P1168 中位数(权值线段树)

た入场券 2021-12-16 16:07 333阅读 1赞

## 题目描述 ##

给出一个长度为N的非负整数序列Ai，对于所有1 ≤ k ≤ (N + 1) / 2，输出A1, A3, …, A2k - 1的中位数。即前1,3,5，…个数的中位数。

## 输入输出格式 ##

输入格式：

第1行为一个正整数N，表示了序列长度。

第2行包含N个非负整数Ai (Ai≤109)。

输出格式：

共(N + 1) / 2行，第ii行为A1, A3, ,A2k−1的中位数。

## 输入输出样例 ##

输入样例\#1：

7
    1 3 5 7 9 11 6

输出样例\#1：

1
    3
    5
    6

## 说明 ##

对于20%的数据，N≤100；

对于40%的数据，N≤3000；

对于100%的数据，N≤100000。

题意:给定一个长度为N的序列，求前1,3,5,7,...,(n&1?n:n-1)位的中位数 n<=1e5 a\[i\]<=1e9

题解:权值线段树板子题，即求全局第k大，依次插入n个数，遇到奇数次数就用权值线段树查询当前序列的第i+1>>1位小的数即可，由于a\[i\]<=1e9，所以先对数据进行离散化；

//AC代码
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+5;
    int tree[maxn*4];
    int dtc[maxn];
    int a[maxn];
    void pushup(int root)
    {
        tree[root]=tree[root<<1]+tree[root<<1|1];
    }
    void update(int root,int l,int r,int index)
    {
        if(l==r)
        {
            tree[root]++;
            return;
        }
        int mid=l+r>>1;
        if(mid>=index)
        update(root<<1,l,mid,index);
        else
        update(root<<1|1,mid+1,r,index);
        pushup(root);
    }
    int querry(int root,int l,int r,int k)
    {
        if(l==r)
        return l;
        int mid=l+r>>1;
        if(tree[root<<1]>=k)
            return querry(root<<1,l,mid,k);
        return querry(root<<1|1,mid+1,r,k-tree[root<<1]);
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i = 1;i <= n;++i){
            scanf("%d",&a[i]);
            dtc[i]=a[i];
        }
        sort(a+1,a+1+n);
        int cnt=unique(a+1,a+1+n)-a-1;
        for(int i = 1;i <= n;++i)
            dtc[i]=lower_bound(a+1,a+1+cnt,dtc[i])-a;
        for(int i = 1;i <= n;++i)
        {
            update(1,1,n,dtc[i]);
            if(i&1)
            {
                int ans=querry(1,1,n,i+1>>1);
                printf("%d\n",a[ans]);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/aaddvvaanntteezz/p/10805172.html