luogu P1168 中位数 |树状数组+二分

题目描述

给出一个长度为NN的非负整数序列A_i，对于所有1 ≤ k ≤ (N + 1) / 21≤k≤(N+1)/2，输出A_1, A_3, …, A_2k - 1的中位数。即前1,3,5,…个数的中位数。

输入格式

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

第2行包含N个非负整数A_i (A_i ≤ 10^9)

输出格式

共(N + 1) / 2(N+1)/2行，第ii行为A_1, A_3, …, A_2k - 1 的中位数。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=1e5+10;

int a[N],b[N],c[N], n;

bool vis[N];

inline void add(int x,int y){

	for(;x<N;x+=x&(-x))c[x]+=y;

}

inline int sum(int x){

	int ans=0;

	for(;x;x-=x&(-x))ans+=c[x];

	return ans;

}

signed main(){

	cin>>n;

	for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];

	sort(b+1,b+1+n);

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

		int op=lower_bound(b+1,b+1+n,a[i])-b;

		while(vis[op])op++;

		vis[op]=1;

		a[i]=op;

	}

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

		add(a[i],1);

		if(!(i&1))continue;

		int l=0,r=n,ans=0;

		while(l<=r){

			int mid=(l+r)>>1;

			if(sum(mid-1)<=sum(n+1)-sum(mid)){

				l=mid+1;

				ans=mid;

			}else r=mid-1;

		}

		cout<<b[ans]<<endl;

	}

}

巴特西

luogu P1168 中位数 |树状数组+二分

题目描述

输入格式

输出格式

最新文章

热门文章