boj 347

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));}}
}