Description
Tradia对数据结构很感兴趣,她懂得很多有用的数据结构,比如链表、二叉树、图等等。最近她在学习堆的有关知识,并对堆能够在log2N的时间复杂度内返回当前集合的最值感到十分的满意。可是我们都知道,Tradia是一个求知欲很强的学生,她并不满足于得到集合的最值(最大、最小值),同时她还想获得集合当前的第K小数,并且要求每次查询的复杂度要与log2N相当,如果复杂度比log2N还低的话,她或许会以此来申请明年的图灵奖。
然而Tradia自己能力有限,没能想出什么好的解决办法,这时她想到了Jim,希望他能帮帮忙。但是Jim现在正忙着给大家出题呢,所以这个光荣的任务只能拜托聪明的你了!
Input
输入包含多组测试数据。
首先第一行输入一个数T(T<=10),表示总共有T组测试数据。
接下来是每组测试数据,第一行是一个数N(N<=50000),表示有N个操作。接着是这N个操作的描述,操作只有两种:
1、ADD X,表示往当前集合添加一个正数X(X<=200000)
2、QUERY K,查询当前集合的第K小数
注意,一开始集合都是空的,输入保证集合中每个数都不相等,且QUERY操作都是合法的。
Output
首先,输出Case #X:其中X代表是第X组数据(具体格式参照样例)。
然后对每组数据的QUERY查询,输出当前第K小的数即可。
Sample Input
2
2
ADD 1
QUERY 1
4
ADD 2
QUERY 1
ADD 1
QUERY 1
Sample Output
Case #1:
1
Case #2:
2
1
Source
humanjustic@Fourth
思路:
线段树
代码:
#include<iostream> using namespace std; #define N 200005 struct node{ int l; int r; int c; }; node arr[N*3]; void bulid(int l,int r,int k) { arr[k].l = l; arr[k].r = r; arr[k].c =0; if(l==r) return; int mid = (l+r)>>1; bulid(l,mid,2*k); bulid(mid+1,r,2*k+1); } void insert(int d,int k) { if(arr[k].l==arr[k].r) { arr[k].c++; return; } int mid = (arr[k].l+arr[k].r)>>1; if(d>mid) insert(d,2*k+1); else insert(d,2*k); arr[k].c = arr[2*k].c+arr[2*k+1].c; } int search(int d,int k) { if(arr[k].l==arr[k].r) return arr[k].l; if(d>arr[2*k].c) return search(d-arr[2*k].c,2*k+1); else return search(d,2*k); } int main() { int t,cnt = 1; scanf("%d",&t); while(t--) { printf("Case #%d:\n",cnt++); bulid(1,N,1); int n; scanf("%d",&n); for(int i=0;i<n;i++) { char a[6]; int k; scanf("%s %d",a,&k); if(a[0]=='A') insert(k,1); else printf("%d\n",search(k,1)); } } }
相关推荐
BOJ的题目1023. Ancient Keyboard解法 源代码
boj 上08 09 年复试模拟题的答案
boj:算法
JAVA_BOJ
Algorithm-BOJ.zip,BekJon在线法官(Java,Kotlin,SWIFT)和PS路线图,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
BOJ
Algorithm-BOJ-PSJ.zip,Baykon在线判断JAVA问题解决方法(第二章),算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-BOJ-AutoCommit.zip,当您解决baekjoon online judge的问题时,它会自动提交并推送到远程存储库。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-boj-auto-submit.zip,日本央行cli提交脚本,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
资源分类:Python库 所属语言:Python 资源全名:boj-0.0.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的,全数字化且可重复使用的着色书,可用于 通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的全数字可重复使用的图画书,专为孩子,父母...
解决问题 Boj.kr
欢迎来到PS_BOJ 이곳은... J이한BOJ문제들의AC코드들이입니다。 안내 :check_mark: C ++ Python으로풀이합니다。 :check_mark: ++ C ++풀이하며 long long 필요하거나으으으으으으으으으끔씩만끔씩만끔씩만끔씩만...
BOJ:日本央行