hdu 2852 KiKi's K-Number (线段树)
2024-09-04 13:21:58
版权声明:本文为博主原创文章,未经博主允许不得转载。
题意:
一个容器,三种操作:
(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 ;
}
最新文章
- SharePoint ";System.Data.SqlClient.SqlException (0x80131904): Parameter &#39;@someColumn&#39; was supplied multiple times.“
- EndNote(二)之英文引文导入方式
- .NET 泛型
- Spark机器学习读书笔记-CH04
- Spot光照资料
- Linux——常用命令详解
- 专门为码农定制的14款创意的T裇(T-Shirt)设计
- linux du 与 df 命令
- String类中的equals()方法
- 20151225jquery学习笔记---选项卡UI
- SQL GROUP BY GROUPING SETS,ROLLUP,CUBE(需求举例)
- Linux 火狐浏览器安装Flash插入
- [Android]Parcelable encountered IOException writing serializable object (name = xxx)
- 推荐前端开发手机调试打印神器console.log()
- Linux之环境搭建(一)
- 2、JavaScript 基础二 (从零学习JavaScript)
- 【工具相关】Web-XAMPP的安装
- SESSION和cookie的使用和区别
- js里面的全局属性 全局对象 全局函数
- substr()和substring()函数
热门文章
- 【bzoj1067】[SCOI2007]降雨量 倍增RMQ
- 【bzoj5099】[POI2018]Pionek 双指针法
- java中的error该不该捕获
- 转:linux命令: tail ,head 显示文件某行内容 与sed在线编辑器
- [AT2377] [agc014_e] Blue and Red Tree
- 洛谷 P2659 美丽的序列 解题报告
- WebLogic XMLDecoder反序列化漏洞(CVE-2017-10271)复现
- 洛谷 P1410 子序列(DP)
- 如何在 ASP.NET 应用程序中实现模拟用户身份(在ASP.NET中以管理员身份运行网站)
- dom4j之selectSingleNode方法