e return del(v
a[a[t].left].size + 1) return find(a[t].right,k-a[a[t].left].size-1); return a[t].key; } int main() { int i,j,k; while (scanf("%d%d",&n,&m) != EOF) { tot = root = 0; char ope[10]; while (n--) { scanf("%s",ope); if (ope[0] == 'I') { scanf("%d",&k); insert(root,k); } else printf("%d\n",find(root,a[root].size+1-m)); } } }
http://www.nocow.cn/index.php/Size_Balanced_Tree这里面SBT讲的还不错，自己还是要多看几遍，还没完全弄懂 http://blog.csdn.net/jarily/article/details/8679236 这个博客也是讲SBT的 http://blog.csdn.net/acceptedxukai/article/details/6921334
这个题目看到别人用了线段树来做；线段树每个节点保存当前编号的数出现的次数。每次查询从小到大第N-K+1个数（N为当前数的总数）。 贴上别人的代码；学习一下； #include
#include
#include
using namespace std; #define MAXN 1001000 #define lson l,m,root<<1 #define rson m+1,r,root<<1|1 int n,k; int node[MAXN<<2]; void push_up(int root) { node[root]=node[root<<1]+node[root<<1|1]; } void build(int l,int r,int root) { if(l==r) { node[root]=0; return ; } int m=(l+r)>>1; build(lson); build(rson); push_up(root); } void update(int n,int l,int r,int root) { if(l==r) { node[root]++; return ; } int m=(l+r)>>1; if(n<=m) update(n,lson); else update(n,rson); push_up(root); } int query(int p,int l,int r,int root) { if(l==r) { return l; } int m=(l+r)>>1; int ret; if(p<=node[root<<1]) ret=query(p,lson); else ret=query(p-node[root<<1],rson); return ret; } void solve() { char a[5]; int ff; build(1,MAXN,1); int counts=0; for(int i=1;i<=n;i++) { scanf("%s",a); if(a[0]=='I') { scanf("%d",&ff); update(ff,1,MAXN,1); counts++; } else printf("%d\n",query(counts-k+1,1,MAXN,1)); } } int main() { while(scanf("%d%d",&n,&k)!=EOF) solve(); return 0; }
还有人用了treap树，那个和SBT类似； 这道题主要还是练一下最小堆； 对最小堆还不是很熟悉，还是要多练；可以当做自己的模板来使用 #include
#include
#include
using namespace std; int heap[1000010],size; void down(int r)//往下交换 { while(r
heap[son+1]?son+1:son; if(son<=size && heap[r]>heap[son]) swap(heap[r],heap[son]); else return; r=son; } } void up(int r)//往上交换，查询 { while(r!=1) { if(heap[r]
>=1; } } void heap_push(int k)//入队 { heap[++size]=k; up(size); } void heap_pop()//出队 { heap[1]=heap[size--]; down(1); } int main() { int n,k,m; char s[5]; while(scanf("%d%d",&n,&k)!=EOF) { size=0; for(int i=0;i
k) heap_pop(); } else { printf("%d\n",heap[1]); } } } return 0; }
用堆来模拟优先队列。