HDU 2852 KiKi's K-Number【 树状数组 二分 】
2024-08-27 10:02:32
题意:给出m个操作,
0:是增加一个数,add(x,1)
1:是删除一个指定的数,这个是看sum(x) - sum(x-1)是否为0,为0的话则不存在,不为0的话,则add(x,-1)
2:是查询比x大的数中第k大的数,
先求出比x小的个数s,假设比x大的数中第k大的数为y,
那么比y小的个数有s+k个
二分y的值来找
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
using namespace std; typedef long long LL;
const int INF = (<<)-;
const int mod=;
const int maxn=; int a[maxn],c[maxn];
int k; int lowbit(int x){ return x &(-x);} int sum(int x){
int ret=;
while(x>){
ret+=c[x];x-=lowbit(x);
}
return ret;
} void add(int x,int d){
while(x<maxn){
c[x]+=d;x+=lowbit(x);
}
} int solve(int x){
int v=x;
int s=sum(x);
int kk=k+s;
int lb=,ub=maxn,mid; for(int i=;i<=;i++){
mid=(lb+ub)/;
if(sum(mid) < kk) lb =mid;
else ub = mid;
// printf("lb = %d ub = %d mid = %d\n",lb,ub,mid);
}
return ub;
} int main(){
int m;
while(scanf("%d",&m) != EOF){
memset(c,,sizeof(c));
while(m--){
int cmd;
scanf("%d",&cmd);
if(cmd == ){
int x;
scanf("%d",&x);
add(x,);
}
if(cmd == ){
int x;
scanf("%d",&x);
if(sum(x) - sum(x-) == ) printf("No Elment!\n");
else add(x,-);
}
if(cmd == ){
int x;
scanf("%d %d",&x,&k);
if(sum(maxn-) - sum(x) < k) printf("Not Find!\n");
else printf("%d\n",solve(x));
}
}
}
return ;
}
最新文章
- iOS-SDWebimage底层实现原理
- CDH离线数据导入solr:利用MapReduceIndexerTool将json文件批量导入到solr
- 转:SAAS 测试
- 如何在真机上调试Android应用程序(图文详解)(zz)
- 在pcDuino上刷了AndDroid,Ubuntu,XBMC
- Android ListView实现圆角
- 深入浅出聊Unity3D项目优化:从Draw Calls到GC
- ArcGIS API for JavaScript 4.2学习笔记[30] 点和线高程查询(第八章完结)
- Centos6.5离线安装lsb_release
- linux -->; ubuntu和mac通过samba共享
- vs code使用Git
- STM32-cJSON库的打包和解析
- Codeforces617E(莫队)
- hadoop MapReduce 入门
- zabbix准备:mysql安装
- Project Euler:Problem 63 Powerful digit counts
- getpagesize.c:32: __getpagesize: Assertion `_rtld_global_ro._dl_pagesize != 0&#39; failed
- ClickHouse 简单试用
- PlantUML&mdash;&mdash;3.Graphviz的安装
- Python基础学习五 内置模块