题意：给你一个序列和m个区间[l,r]，每次输出每个区间中第k大的值为多少。区间之间有重叠但没有完全包含。
解析：由于区间没有完全包含。所以先将区间按左端点排序，每次查询一个新区间时将其与上一个区间重叠部分保留，其余删去，在加入自己新的部分，最后查询第k大值。这是一道考察treap应用的好题。
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int n,m; int a[100005],ans[50005]; struct query { int l,r,k,frm; }q[50005]; bool cmp(query x,query y) { return x.l==y.l?x.r<y.r:x.l<y.l; } struct node { int ch[2]; int val,w,sz; int rep; node() { ch[0]=ch[1]=val=w=sz=rep=0; } }t[150005]; int cnt,root; void maintain(int u) { t[u].sz=t[u].rep+t[t[u].ch[0]].sz+t[t[u].ch[1]].sz; } void rot(int &f,int c)//1:left 0:right { int son=t[f].ch[c]; t[f].ch[c]=t[son].ch[c^1]; t[son].ch[c^1]=f; t[son].sz=t[f].sz; maintain(f); f=son; } void insert(int num,int& h) { if(!h) { t[++cnt].val=num; t[cnt].w=rand(); t[cnt].sz=t[cnt].rep=1; root=cnt; return; } t[h].sz++; if(num==t[h].val)t[h].rep++; else if((num>t[h].val&&!t[h].ch[1])||(num<t[h].val&&!t[h].ch[0])) { t[++cnt].val=num; t[cnt].w=rand(); t[h].ch[num>t[h].val]=cnt; t[cnt].sz=t[cnt].rep=1; if(t[cnt].w<t[h].w)rot(h,num>t[h].val); } else { insert(num,t[h].ch[num>t[h].val]); if(t[t[h].ch[num>t[h].val]].w<t[h].w)rot(h,num>t[h].val); } } void del(int num,int& h) { if(t[h].val==num) { if(t[h].rep>1)t[h].rep--,t[h].sz--; else if(!t[h].ch[0]||!t[h].ch[1])h=t[h].ch[0]+t[h].ch[1]; else { rot(h,t[h].ch[1]<t[h].ch[0]); del(num,h); } return; } t[h].sz--; if(num<t[h].val)del(num,t[h].ch[0]); else del(num,t[h].ch[1]); } int find(int k,int h) { int sum=t[t[h].ch[0]].sz; if(sum<k&&sum+t[h].rep>=k)return t[h].val; else if(k<=sum)return find(k,t[h].ch[0]); else return find(k-sum-t[h].rep,t[h].ch[1]); } int main() { int i,j; srand(53363); scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d",&a[i]); for(i=1;i<=m;i++) { scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k); q[i].frm=i; } sort(q+1,q+m+1,cmp); for(i=1;i<=m;i++) { if(q[i].l>q[i-1].r) { root=0; for(j=q[i].l;j<=q[i].r;j++)insert(a[j],root); } else { for(j=q[i-1].l;j<q[i].l;j++)del(a[j],root); for(j=q[i-1].r+1;j<=q[i].r;j++)insert(a[j],root); } ans[q[i].frm]=find(q[i].k,root); } for(i=1;i<=m;i++)printf("%d\n",ans[i]); return 0; }
