?
动态询问第k小，只有插入和查询两种操作，第一发平衡树。。纪念（sad 不全，没有删除操作，本题没要求嘛）。主要是不会离散化用线段树不会写。。拼死敲了两天Treap
#include #include #include #include #include #include #include #include #include #include #include #include #include #define maxn 1005 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1<<40+10 #define pp pair #define ull unsigned long long using namespace std; int n; struct node{ node *ch[2]; int r,v,s; node (){} node (int v){ch[0]=NULL;ch[1]=NULL;r=rand();this->v=v;s=1;} bool operator <(const node& c)const{ return r s; if(ch[1]!=NULL)s+=ch[1]->s; } }; void rotate(node* &o,int d){ node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o; o->maintain();k->maintain();o=k; } void insert(node* &o,int x) { if(o==NULL) o=new node(x); else{ int d=o->cmp(x); insert(o->ch[d],x); if(o->ch[d]->r>o->r)rotate(o,d^1); } o->maintain(); } bool Find(node* o,int x) { while(o!=NULL) { int d=o->cmp(x); if(d==-1)return 1; else o=o->ch[d]; } return 0; } int find_kth(node* o,int k) { if(o==NULL||k>o->s)return -1; int s=(o->ch[0]==NULL?0:o->ch[0]->s); if(k==s+1)return o->v; else if(k<=s) return find_kth(o->ch[0],k); else return find_kth(o->ch[1],k-s-1); } void solve() { node *root=NULL; char op[2];int x; while(n--) { scanf(%s %d,op,&x); if(op[0]=='P') { if(Find(root,x))continue; insert(root,x); } else printf(%d ,find_kth(root,x)); } } int main() { while(~scanf(%d,&n)) solve(); return 0; }