版权声明:本文为博主原创文章,未经博主允许不得转载。

hdu 2852

题意:

  一个容器,三种操作:

    (1) 加入一个数 e

    (2) 删除一个数 e,如果不存在则输出 No Elment!

    (3) 查询比a大的数中的第k小数,不存在就输出 Not Find!

解法:

  关于第三点,可以先查询小于等于a的数的个数cnt,然后直接查询第cnt+k小数就行了 。

  二分+树状数组 或者 主席树(有点杀鸡用牛刀的感觉 。。。) 也是可以做的  _(:з」∠)_

code:线段树

 #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
#define ll long long using namespace std; const int N=1e5+; int L[N*],R[N*],cnt[N*]; inline void bulidtree(int l,int r,int k){
L[k]=l; R[k]=r;
cnt[k]=;
if (l==r) return;
int mid=(l+r)>>;
bulidtree(l,mid,k<<);
bulidtree(mid+,r,(k<<)|);
} inline void update(int p,int d,int k){
cnt[k]+=d;
if (L[k]==R[k]) return;
int mid=(L[k]+R[k])>>;
if (p<=mid) update(p,d,k<<);
else update(p,d,(k<<)|);
} inline int query(int x,int y,int k){
if (L[k]==x && R[k]==y)
return cnt[k];
int mid=(L[k]+R[k])>>;
if (y<=mid) return query(x,y,k<<);
else if (x>mid) return query(x,y,(k<<)|);
else return query(x,mid,k<<)+query(mid+,y,(k<<)|);
} inline int find(int x,int k){
if (cnt[k]<x) return -;
while (L[k]!=R[k]){
if (x<=cnt[k<<]) k=k<<;
else {
x-=cnt[k<<];
k=(k<<)|;
}
}
return L[k];
} int main(){
int m;
while (~scanf("%d",&m)){
int p,x,y;
bulidtree(,N-,);
while (m--){
scanf("%d",&p);
switch(p){
case :
scanf("%d",&x);
update(x,,);
break;
case :
scanf("%d",&x);
if (query(x,x,)) update(x,-,);
else puts("No Elment!");
break;
case :
scanf("%d%d",&x,&y);
int ans=find(query(,x,)+y,);
if (~ans) printf("%d\n",ans);
else puts("Not Find!");
break;
}
}
}
return ;
}

最新文章

  1. SharePoint &quot;System.Data.SqlClient.SqlException (0x80131904): Parameter &#39;@someColumn&#39; was supplied multiple times.“
  2. EndNote(二)之英文引文导入方式
  3. .NET 泛型
  4. Spark机器学习读书笔记-CH04
  5. Spot光照资料
  6. Linux——常用命令详解
  7. 专门为码农定制的14款创意的T裇(T-Shirt)设计
  8. linux du 与 df 命令
  9. String类中的equals()方法
  10. 20151225jquery学习笔记---选项卡UI
  11. SQL GROUP BY GROUPING SETS,ROLLUP,CUBE(需求举例)
  12. Linux 火狐浏览器安装Flash插入
  13. [Android]Parcelable encountered IOException writing serializable object (name = xxx)
  14. 推荐前端开发手机调试打印神器console.log()
  15. Linux之环境搭建(一)
  16. 2、JavaScript 基础二 (从零学习JavaScript)
  17. 【工具相关】Web-XAMPP的安装
  18. SESSION和cookie的使用和区别
  19. js里面的全局属性 全局对象 全局函数
  20. substr()和substring()函数

热门文章

  1. 【bzoj1067】[SCOI2007]降雨量 倍增RMQ
  2. 【bzoj5099】[POI2018]Pionek 双指针法
  3. java中的error该不该捕获
  4. 转:linux命令: tail ,head 显示文件某行内容 与sed在线编辑器
  5. [AT2377] [agc014_e] Blue and Red Tree
  6. 洛谷 P2659 美丽的序列 解题报告
  7. WebLogic XMLDecoder反序列化漏洞(CVE-2017-10271)复现
  8. 洛谷 P1410 子序列(DP)
  9. 如何在 ASP.NET 应用程序中实现模拟用户身份(在ASP.NET中以管理员身份运行网站)
  10. dom4j之selectSingleNode方法