题目

分析

看到中位数，当然会想到二分答案。

考虑检查答案。自然，我们需要找出中位数小于二分值\(k\)的区间的个数。考虑构造一个\(b\)：

\[b_i=(-1)^{[a_i\ge k]}
\]

可以发现，这个\(b\)满足，如果区间\([l,r]\)的中位数小于\(k\)，则\(\sum_{i=l}^r b_i>0\)。

现在检查仍然是\(O(n^2)\)的，过不了。考虑优化。

把\(b\)写成前缀和的形式：\(s_i=\sum_{j=1}^i b_j\)。

那么一个区间\([l,r]\)需要被统计就对应着\(s_r-s_{l-1}>0\)，也即是\(s_r>s_{l-1}\)。

这是一个顺序对的问题，可以用树状数组统计。时间是\(O(n\log_2n\log_2(\max a))\)

需要注意的有：

1. 注意统计\([1,r]\)形式的区间，也即是统计\(s_r>0\)的情况。

2. 注意树状数组下标为正。

3. 注意总共有\(\frac {n(n+1)}{2}\)个区间。

代码

#include <cstdio>

typedef long long LL;

#define int LL

const int MAXN = 1e5 + 5;

template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}

template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}

template<typename _T>

_T MAX( const _T a, const _T b )

{

	return a > b ? a : b;

}

template<typename _T>

_T MIN( const _T a, const _T b )

{

	return a < b ? a : b;

}

int BIT[MAXN];

int a[MAXN], s[MAXN];

int N;

int lowbit( const int &x ) { return x & ( -x ); }

void update( int x, const int v ) { for( ; x <= N ; x += lowbit( x ) ) BIT[x] += v; }

int getSum( int x ) { int ret = 0; while( x ) ret += BIT[x], x -= lowbit( x ); return ret; }

bool chk( const int len )

{

	LL ret = 0; int mn = N;

	for( int i = 1 ; i <= N ; i ++ ) s[i] = a[i] >= len ? -1 : 1;

	for( int i = 1 ; i <= N ; i ++ ) s[i] += s[i - 1], ret += s[i] > 0, mn = MIN( mn, s[i] );

	for( int i = 1 ; i <= N ; i ++ ) BIT[i] = 0, s[i] += 1 - mn;

	for( int i = 1 ; i <= N ; i ++ ) ret += getSum( s[i] - 1 ), update( s[i], 1 );

	return ret <= 1ll * N * ( N + 1 ) / 4;

}

signed main()

{

	int l = 1e9, r = -1;

	read( N );

	for( int i = 1 ; i <= N ; i ++ ) read( a[i] ), l = MIN( l, a[i] ), r = MAX( r, a[i] );

	int mid;.

	while( r - l > 1 )

	{

		if( chk( mid = l + r >> 1 ) ) l = mid;

		else r = mid - 1;

	}

	if( chk( r ) ) write( r );

	else write( l );

	putchar( '\n' );

	return 0;

}

[ARC101B]Median of Medians

题目

分析

代码