题目意思是有两种命令ADD(x)和GET(x)
ADD(x) 在已有序列中加入x元素
GET(x) 在执行x次ADD命令后得到已有序列中第i小的元素 ( i初始为0每次执行GET命令前i要先加1)
ADD和GET最多都是30000
刚开始做的时候 用到了nth_element函数 ,TLE了
因为nth_element 的复杂度为O(n) ,显然整个解过程的复杂度为O(n*n)不能满足时间要求
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; const int inf = 0x3f3f3f3f; const int N = 30009; const double esp = 1e-6; int v[N]; struct treap { treap *l, *r; int val, pri; //节点值,优先级 int size; treap(int vv) { l = NULL; r = NULL; pri = rand(); //随机数作为优先级 val = vv; } }*root; int lsize(treap *p) { return p->l ? p->l->size : 0; } int rsize(treap *p) { return p->r ? p->r->size : 0; } void lro(treap *&p) //左旋,右孩子变成根,根变成左孩子 { treap *tmp = p->r; p->r = tmp->l; tmp->l = p; tmp->size = p->size; p->size = lsize(p) + rsize(p)+1; p = tmp; } void rro(treap *&p) //右旋,左孩子变成根,根变成右孩子 { treap *tmp = p->l; p->l = tmp->r; tmp->r = p; tmp->size = p->size; p->size = lsize(p) + rsize(p)+1; p = tmp; } void insert(treap *&p, int val) { if(!p) //插入 { p = new treap(val); p->size = 1; } else if(val <= p->val) //进入左孩子 { p->size++; insert(p->l, val); if( p->l->pri < p->pri ) rro(p); } else //进入右孩子 { p->size++; insert(p->r, val); if(p->r->pri < p->pri) lro(p); } } int find(int k, treap *p) { int tmp = lsize(p); if(k == tmp + 1) return p->val; else if(k<=tmp) return find(k, p->l); else return find(k-1-tmp, p->r); } int main() { root = NULL; int n, m, x, now=1; scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) scanf("%d", &v[i]); for(int i=1; i<=m; i++) { scanf("%d", &x); for( ; now<=x; now++) { insert( root, v[now] ); } printf("%d\n", find(i, root)); } return 0; }