题意：给出n(<=100000)个数，m个询问，询问[L,R]区间内第k小数，两两查询区间互不包含。
解：因为两两查询区间互不包含，所以按L从小到大排序，则必有Li<=Lj ,Ri<=Rj(0<i<j<=n)
所以对于每一个查询，删除当前treap中当前查询不包含的点，插入当前treap中当前查询未插入的点
每个点删，插各一次，用treap实现，所以时间复杂度为O(nlogn)
代码：
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<ctime> #define L(i) T[i].s[0] #define R(i) T[i].s[1] using namespace std; const int N=100011; struct node{ int s[2],sz,pri,v; void set(int x,int y){ sz=1;v=x;pri=y; } }T[N]; struct q{ int l,r,id,k; bool operator < (const q a){ return a.l>l; } }s[N]; int a[N],rt,tot,ans[N]; inline void maintain(int i){T[i].sz=T[L(i)].sz+T[R(i)].sz+1;}//维护 inline void Rotate(int &y,int f){//旋转 int x=T[y].s[!f]; T[y].s[!f]=T[x].s[f]; T[x].s[f]=y; maintain(y);maintain(x); y=x; } inline void insert(int &i,int val){ if (!i){ T[i=++tot].set(val,rand()); return; } bool f=T[i].v>val; insert(T[i].s[!f],val); if (T[T[i].s[!f]].pri>T[i].pri)Rotate(i,f); else maintain(i); } inline void Delete(int &i,int val){ if (val>T[i].v)Delete(T[i].s[1],val); else if(val<T[i].v)Delete(T[i].s[0],val); else{ if (!L(i) && !R(i))i=0; else if (!L(i))i=R(i); else if (!R(i))i=L(i); else{ int f=T[L(i)].pri>T[L(i)].pri;//若左子树pri大于右子树，将左子树右旋至当前节点，则当前节点旋至右子树，删右子树，反之亦然 Rotate(i,f); Delete(T[i].s[f],val); } } if (i)maintain(i); } inline int query(int i,int kth){ if (kth<=T[L(i)].sz)query(L(i),kth); else if (kth==T[L(i)].sz+1)return T[i].v; else query(R(i),kth-T[L(i)].sz-1); } int main(){ int n,m; srand(time(0)); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++)scanf("%d",&a[i]); for (int i=1;i<=m;i++){ scanf("%d%d%d",&s[i].l,&s[i].r,&s[i].k); if (s[i].l>s[i].r)swap(s[i].l,s[i].r); s[i].id=i; } sort(s+1,s+m+1); s[0].l=-1;s[0].r=-2; for (int i=1;i<=m;i++){ for (int j=s[i-1].l;j<=min(s[i-1].r,s[i].l-1);j++)Delete(rt,a[j]); for (int j=max(s[i].l,s[i-1].r+1);j<=s[i].r;j++)insert(rt,a[j]); ans[s[i].id]=query(rt,s[i].k); } for (int i=1;i<=m;i++)printf("%d\n",ans[i]); return 0; }