Treap是一种动态平衡二叉树结构，具有期望的O(log2n)的复杂度。适用于动态区间数据的查询、更改、维护等操作。
题目大意
一组数从前向后插入队列中，插入的过程中会有查询，查询当前队列中的第k小的数。
题目分析
对于数据的查询，可以考虑使用treap这种平衡二叉树来实现。而且treap这种动态平衡树结构，可以很方便的实现第k大的查询。 需要注意的是，每个节点保存与该节点相同元素的个数count对查询第k个数据时候的影响，见代码。
实现(c++)
#define _CRT_SECURE_NO_WARNINGS#include#include #define MAX_NUM 30010struct TreapNode{ int key; int priority; int size; int count; TreapNode* child[2]; TreapNode(int val){ key = val; priority = rand(); child[0] = child[1] = NULL; count = size = 1; } void Update(){ size = count; if (child[0]){ size += child[0]->size; } if (child[1]){ size += child[1]->size; } }};struct Treap{ TreapNode* root; Treap() :root(NULL){}; void Rotate(TreapNode*& node, int dir){ TreapNode* ch = node->child[dir]; node->child[dir] = ch->child[!dir]; ch->child[!dir] = node; node->Update(); node = ch; //reference } void Insert(TreapNode*& node, int k){ if (!node){ node = new TreapNode(k); } else if (node->key == k){ node->count++; } else{ int dir = node->key < k; Insert(node->child[dir], k); if (node->priority < node->child[dir]->priority){ Rotate(node, dir); } } node->Update(); } int GetKth(TreapNode* root, int k){ TreapNode* node = root; while (node){ if (!node->child[0]){ if (k <= node->count){ return node->key; } else{ k -= (node->count); node = node->child[1]; } } else{ if (node->child[0]->size < k && node->child[0]->size + node->count >= k){ return node->key; } else if (node->child[0]->size >= k){ node = node->child[0]; } else{ k -= (node->child[0]->size + node->count); node = node->child[1]; } } } return 0; }};int gNumber[MAX_NUM];Treap gTreap;int main(){ int number_count, query_count; scanf("%d%d", &number_count, &query_count); for (int i = 0; i < number_count; i++){ scanf("%d", &gNumber[i]); } int query_old = 0; int query_new; for (int i = 1; i <= query_count; i++){ scanf("%d", &query_new); for (int k = query_old; k < query_new; k++){ gTreap.Insert(gTreap.root, gNumber[k]); } query_old = query_new; int result = gTreap.GetKth(gTreap.root, i); printf("%d\n", result); } return 0;}