/* 功能Function Description: BOJ 1257 Jim 和 Tradia的故事II-第K小数---初学线段树
开发环境Environment: DEV C++ 4.9.9.1
技术特点Technique:
版本Version:
作者Author: 可笑痴狂
日期Date: 20120807
备注Notes:
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
*/
//自己的代码---未提交验证--没找到题目来源
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int num;
node *lc,*rc;
int num_of_lc;
}node;
void insert(int t,node *&T)
{
if(T==NULL)
{
T=(node *)malloc(sizeof(node));
T->num=t;
T->lc=T->rc=NULL;
T->num_of_lc=1;
return;
}
else
{
if(t>T->num)
insert(t,T->rc);
else
{
++T->num_of_lc;
insert(t,T->lc);
}
}
}
void query(int k,node *&T) //查询第k小数
{
if(k==T->num_of_lc)
printf("%d\n",T->num);
else if(k<T->num_of_lc)
query(k,T->lc);
else
query(k-(T->num_of_lc),T->rc);
}
int main()
{
int m,i,n,t;
char cmd[10];
node *T;
scanf("%d",&m);
for(i=1;i<=m;++i)
{
T=NULL;
printf("Case #%d:\n",i);
scanf("%d",&n);
while(n--)
{
scanf("%s%d",cmd,&t);
if(cmd[0]=='A')
insert(t,T);
else
query(t,T);
}
}
return 0;
}
//网上代码一：(动态创建)
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *lc,*rc;
int num_of_lc;
}*nodeptr;
nodeptr Tree;
void insert(int m,nodeptr &T)//插入
{
if(T==NULL)
{
T=(nodeptr)malloc(sizeof(node));
T->data=m;
T->lc=NULL;
T->rc=NULL;
T->num_of_lc=0;
}
else
{
if(m>T->data)
insert(m,T->rc);
else
{
T->num_of_lc++;
insert(m,T->lc);
}
}
}
void query(int m,nodeptr &T)//查找k小数
{
if(m==T->num_of_lc+1)
{
printf("%d\n",T->data);
}
else if(m<T->num_of_lc+1)
{
query(m,T->lc);
}
else if(m>T->num_of_lc+1)
{
query((m - T->num_of_lc-1),T->rc);
}
}
int main(void)
{
int t;
int n;
char opt[60];
int m=0;
char num[8];
scanf("%d",&t);
for(int i=0;i<t;i++)
{
Tree=(nodeptr)malloc(sizeof(node));
Tree=NULL;
printf("Case #%d:\n",i+1);
scanf("%d\n",&n);
for(int j=0;j<n;j++)
{
gets(opt); //他这里读取的有点麻烦，可以改成上边的
switch(opt[0])
{
case 'A':
m=0;
while(opt[4+m])
{
num[m]=opt[4+m];
m++;
}
num[m]='\0';
m=atoi(num); //将字符串转化为int型数值
insert(m,Tree);
break;
case 'Q':
m=0;
while(opt[6+m])
{
num[m]=opt[6+m];
m++;
}
num[m]='\0';
m=atoi(num);
query(m,Tree);
break;
}
}
}
// system("pause");
return 0;
}
//网上代码二：(静态创建)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define MAXN 200000
struct node
{
int l,r;
int c;
}Tree[2 * MAXN + 1]; //个人感觉不用乘2
void build(int a,int b,int k)
{
if (a == b)
{
Tree[k].l = a;
Tree[k].r = b;
Tree[k].c = 0;
return;
}
int mid = (a + b) >> 1;
Tree[k].l = a;
Tree[k].r = b;
Tree[k].c = 0;
build(a,mid,k * 2);
build(mid + 1,b,k * 2 + 1);
return;
}
void insert(int b,int k)
{
if (Tree[k].l == Tree[k].r && b == Tree[k].l)
{
Tree[k].c += 1;
return;
}
int mid = (Tree[k].l + Tree[k].r) >> 1;
if (b <= mid)
insert(b,k * 2);
else
insert(b,k * 2 + 1);
Tree[k].c = Tree[k * 2].c + Tree[k * 2 + 1].c;
return;
}
void search(int b,int k,int &cnt)
{
if (Tree[k].l == Tree[k].r)
{
cnt = Tree[k].l;
return;
}
int mid = (Tree[k].l + Tree[k].r) / 2;
if (b > Tree[k * 2].c)
search(b - Tree[k * 2].c,k * 2 + 1,cnt);
else
search(b,k * 2,cnt);
}
int main()
{
int n,cas;
scanf("%d",&cas);
for (int j = 1; j <= cas; ++j)
{
printf("Case #%d:\n",j);
scanf("%d",&n);
build(1,MAXN,1);
int i;
char op[10];
int b;
for (i = 0; i < n; ++i)
{
scanf ("%s %d",op,&b);
if (strcmp(op,"ADD") == 0)
{
insert(b,1);
}
else
{
int cnt;
search(b,1,cnt);
printf("%d\n",cnt);
}
}
}
return 0;
}
BOJ 1257 Jim 和 Tradia的故事II第K小数初学线段树
功不成，身已退