主席树模板。
注意内存，每次 insert 会增加 log2n<<1 个节点，初始化线段树有 n<<2 个节点。
总结点数 = ( n<<2 ) + ( n * log2n<<1 )。
C++没有计算 log2() 的函数，但提供了 log10()，根据换底公式 log2n = log10n / log102。
// q.c#include#include #include #include #include using namespace std;const int M=100000+10;/************************************************************************/int cnt,lc[M<<5],rc[M<<5],s[M<<5],L[M<<5],R[M<<5];void build(int &o,int l,int r) { if(!o) o=++cnt; L[o]=l,R[o]=r; if(l==r) return ; int mid=(l+r)>>1; build(lc[o],l,mid),build(rc[o],mid+1,r);}void cpy(int x,int y) { lc[x]=lc[y],rc[x]=rc[y],s[x]=s[y],L[x]=L[y],R[x]=R[y];}void UP(int o) { s[o]=s[lc[o]]+s[rc[o]];}void insert(int &o,int p,int x) { if(!o) o=++cnt; cpy(o,p); if(L[o]==R[o]) { s[o]++; return ; } int mid=(L[o]+R[o])>>1; if(x<=mid) lc[o]=0,insert(lc[o],lc[p],x); else rc[o]=0,insert(rc[o],rc[p],x); UP(o);}int query(int o,int p,int k) { if(L[o]==R[o]) return L[o]; int tmp=s[lc[o]]-s[lc[p]]; if(k<=tmp) return query(lc[o],lc[p],k); else return query(rc[o],rc[p],k-tmp);}/************************************************************************/struct Data { int x,y; bool operator < (const Data &A) const { if(x!=A.x) return x