本文主要是介绍SDUTOJ 3043 迷之容器 线段树求全局第k小，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
迷之容器
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
FF最近得到了一个神奇的容器。他可以不停地往这个容器里放入数字，如果刚放入的这个数字已存在于容器中，那么容器只会保留其中的一个。
现在FF又有了一个很蛋疼的想法，他在放入了若干个数字之后，想知道容器中第K小的数字是多少。
输入
多组输入。
对于每组数据，初始时容器为空。
每组数据输入一个n(1 <= n <= 100000)，代表有n次查询和放入操作。
接下来的n行，每行一个字符 c和数字x (-1000,000,000<= x <= 1000,000,000)，用空格隔开。
若c为 “ P ”，则表明FF要放入x,此时x ∈[-1000 000 000,1000 000 000]。
若c 为 “Q”，则表明FF想知道容器中第x小的数是多少，若不存在则用 -1代表,此时x∈[1，100000]。
输出
对于每次询问，输出一个数字代表答案。
示例输入
4
P 1
Q 1
P -1
Q 2
示例输出
1
1
提示
来源
zmx
假期刷数据结构线段树的时候真的没遇到这种问题——线段树求第K小（大），今天留下（水题）模板一份：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define ll long longusing namespace std;struct Node
{ll num;int op;
}blf[100010];//存储操作的数组ll sr[100010],lsh[100010];//要输入的数
int d[100010 << 2];//线段树数组，维护有多少数存在
int ans;//答案记录int b_sch(int l,int r,ll key)//二分查找，找要添加的数离散化后（下标）编号是多少
{while(l <= r){int mid = (l + r) >> 1;if(key == lsh[mid])return mid;else if(key > lsh[mid])l = mid + 1;elser = mid - 1;}return -1;
}void up(int step)//回溯函数
{d[step] = d[step << 1] + d[step << 1 | 1];
}
void upd(int s,int t,int uu,int unum,int step)//线段树更新，就是把数设为存在
{if(s >= t){d[step] = unum;return ;}int mid = (s + t) >> 1;if(uu <= mid)upd(s,mid,uu,unum,step << 1);if(uu > mid)upd(mid + 1,t,uu,unum,step << 1 | 1);up(step);
}void qu(int s,int t,ll qq,int step)//线段树询问
{if(s >= t)//如果找到了某个节点{ans = s;//标记他所代表的数的编号return ;}if(t - s > 0)//如果没到最终节点{int mid = (s + t) >> 1;if(qq <= (ll)(d[step << 1]))//如果要找的这个数比左子树上的数小 就必然在左子树qu(s,mid,qq,step << 1);elsequ(mid + 1,t,qq - (ll)(d[step << 1]),step << 1 | 1);//不在左子树，必在右子树，但查找的//第qq（k）小要减去左子树的数的个数才能继续查找}
}int main()
{int n;char str[10];while(~scanf("%d",&n)){int cnt1 = 0,cnt2 = 0;for(int i = 0;i < n;i++){scanf("%s%lld",str,&blf[i].num);if(str[0] == 'P'){blf[i].op = 1;sr[cnt1++] = blf[i].num;}else{blf[i].op = 2;//1代表P 2代表 Q}}sort(sr,sr + cnt1);//排序lsh[++cnt2] = sr[0];for(int i = 1;i < cnt1;i++){if(lsh[cnt2] != sr[i]){lsh[++cnt2] = sr[i];}}//离散化memset(d,0,sizeof(d));//初始化线段树for(int i = 0;i < n;i++){if(blf[i].op == 1){int fh = b_sch(1,cnt2,blf[i].num);//上面有介绍upd(1,cnt2,fh,1,1);//更新}else{if((ll)(d[1]) < blf[i].num){printf("-1\n");//如果已有的数比要查找的k小的话 就不存在}else{ans = 0;qu(1,cnt2,blf[i].num,1);// printf("ans = %d\n",ans);printf("%lld\n",lsh[ans]);}}}}return 0;
}
这篇关于SDUTOJ 3043 迷之容器 线段树求全局第k小的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
