题目：http://poj.org/problem?id=1442
简单的插入、查询第k大数的题。这本来应该算一道经典的堆的应用题，结果我用SBT水过去了。。。算了，有机会要用堆实现一下。
SBT 版：
顺便说下，用cin一次TLE一次1000MS惊现过去，换成scanf 400MS无压力。。。（跟其他人比还是太慢了。。。）
POJ 1442 SBT #include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <iomanip>
#include <climits>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>using namespace std;const int maxn= 100010;class SBT{
public:void Clear(){memset(K,0,sizeof(K));memset(L,0,sizeof(L));memset(R,0,sizeof(R));memset(S,0,sizeof(S));RT= SZ= 0;}void Insert(int key) {Insert(RT,key);}int Delete(int key) {return Delete(RT,key);}int Succ(int key) {return Succ(RT,key);}int Pred(int key) {return Pred(RT,key);}int Rank(int key) {return Rank(RT,key);}int Search(int key) {return Search(RT,key);}int Select(int key) {return Select(RT,key);}private:int K[maxn];int L[maxn];int R[maxn];int S[maxn];int RT, SZ;void LeftRotate(int &x){int k= R[x];R[x]= L[k];L[k]= x;S[k]= S[x];S[x]= S[L[x]]+S[R[x]]+1;x= k;}void RightRotate(int &x){int k= L[x];L[x]= R[k];R[k]= x;S[k]= S[x];S[x]= S[L[x]]+S[R[x]]+1;x= k;}void MaintainFat(int &t){if (S[L[L[t]]]>S[R[t]]){RightRotate(t);MaintainFat(R[t]);MaintainFat(t);return;}if (S[R[L[t]]]>S[R[t]]){LeftRotate(L[t]);RightRotate(t);MaintainFat(L[t]);MaintainFat(R[t]);MaintainFat(t);return;}if (S[R[R[t]]]>S[L[t]]){LeftRotate(t);MaintainFat(L[t]);MaintainFat(t);return;}if (S[L[R[t]]]>S[L[t]]){RightRotate(R[t]);LeftRotate(t);MaintainFat(L[t]);MaintainFat(R[t]);MaintainFat(t);return;}}void Maintain(int &t, int flag){if (!flag){if (S[L[L[t]]] >S[R[t]])RightRotate(t);else if (S[R[L[t]]] >S[R[t]]){LeftRotate(L[t]);RightRotate(t);}elsereturn;}else{if (S[R[R[t]]] >S[L[t]])LeftRotate(t);else if (S[L[R[t]]] >S[L[t]]){RightRotate(R[t]);LeftRotate(t);}elsereturn;}Maintain(L[t], false);Maintain(R[t], true);Maintain(t, true);Maintain(t, false);}void Insert(int &t, int key){if (t==0){t= ++SZ;K[t]= key;S[t]= 1;return;}S[t]++;if (key<K[t])Insert(L[t],key);elseInsert(R[t],key);Maintain(t,key>K[t]);}int Delete(int &t, int key){S[t]--;if ((key==K[t])||(key<K[t]&&L[t]==0)||(key>K[t]&&R[t]==0)){int ret= K[t];if (L[t]==0 || R[t]==0)t= L[t]+R[t]; // T change to his Leftson or RightsonelseK[t]= Delete(L[t], K[t]+1); // Not find then delete the last find Pointreturn ret;}else{if (key<K[t])return Delete(L[t],key);elsereturn Delete(R[t],key);}}int Search(int t, int key){ //return root pointif (t==0 || key==K[t])return t;if (key<K[t])return Search(L[t],key);elsereturn Search(R[t],key);}int Select(int t, int k){ // return K-th int treeint num= S[L[t]]+1;if (k==num)return K[t];else if (k<num)return Select(L[t],k);elsereturn Select(R[t],k-num);}int Succ(int t, int key){if (t==0)return key;if (key>=K[t]) //
return Succ(R[t], key);else{int r= Succ(L[t], key);if (r==key)return K[t];elsereturn r;}}int Pred(int t, int key){if (t==0)return key;if (key<=K[t]) //
return Pred(L[t], key);else {int r= Pred(R[t], key);if (r==key)return K[t];elsereturn r;}}int Rank(int t, int key){if (t==0)return 1;if (key<=K[t]) //
return Rank(L[t], key);else if (key>K[t])return S[L[t]]+1+Rank(R[t],key);}
};int main()
{int a[30005];int com[30005];memset(com,0,sizeof(com));SBT sbt;int sbtnum=0;int n,m;scanf("%d%d",&m,&n);for (int i=0;i<m;i++)scanf("%d",&a[i]);for (int i=0;i<n;i++){int k;scanf("%d",&k);com[k]++;}int k=0;for (int i=0;i<m;i++){sbt.Insert(a[i]);sbtnum++;while(com[sbtnum]){com[sbtnum]--;k++;printf("%d\n",sbt.Select(k));}}return 0;
}
STL priority_queue堆版：
先占个位^_^~~~
线段树版：
先占个位^_^~~~