HDU 2852 KiKi's K-Number 树状数组 + 二分

一共最多才100000个数,并且数值范围0~100000。

树状数组 C[i] 记录数值为 i 的数有多少个。

删除时如果Query( a ) - Query( a - 1 ) == 0 则该数不存在。

求大于a的第K大数只需要对大于a的数二分查找一下,Query( MAXN ) - Query(a)为大于 a 的数的总个数,如果小于K 则不存在。

 #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm> using namespace std; const int MAXN = ; int Q;
int C[MAXN]; int lowbit( int x )
{
return x & (-x);
} void Update( int x, int val )
{
while ( x < MAXN )
{
C[x] += val;
x += lowbit(x);
}
return;
} int Query( int x )
{
int res = ;
while ( x > )
{
res += C[x];
x -= lowbit(x);
}
return res;
} int BiSearch( int l, int r, int val, int zuo )
{
int ans = -;
while ( l <= r )
{
int mid = ( l + r ) >> ;
int tmp = Query( mid ) - Query( zuo );
//printf( "%d %d\n", mid, tmp );
if ( tmp >= val )
{
r = mid - ;
ans = mid;
}
else l = mid + ;
}
return ans;
} int main()
{
while ( ~scanf( "%d", &Q ) )
{
memset( C, , sizeof(C) );
while ( Q-- )
{
int op, a, b;
scanf( "%d", &op );
switch( op )
{
case :
scanf( "%d", &a );
Update( a, );
break; case :
scanf( "%d", &a );
if ( Query( a ) - Query( a - ) == ) puts("No Elment!");
else Update( a, - );
break; case :
scanf( "%d%d", &a, &b );
if ( Query( MAXN - ) - Query( a ) < b ) puts("Not Find!");
else
{
int ans = BiSearch( a, MAXN - , b, a );
printf( "%d\n", ans );
}
break;
}
}
}
return ;
}
上一篇:【NOIP2016】愤怒的小鸟


下一篇:通知 Notification 详解