https://www.luogu.org/problemnew/show/P1801
Black Box是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量i。最开始的时候Black Box是空的．而i等于0。这个Black Box要处理一串命令。
命令只有两种：
ADD(x):把x元素放进BlackBox;
GET:i加1，然后输出Blackhox中第i小的数。
记住：第i小的数，就是Black Box里的数的按从小到大的顺序排序后的第i个元素。例如：
我们来演示一下一个有11个命令的命令串。（如下图所示）
现在要求找出对于给定的命令串的最好的处理方法。ADD和GET命令分别最多200000个。现在用两个整数数组来表示命令串：
1.A(1)，A(2)，…A(M)：一串将要被放进Black Box的元素。每个数都是绝对值不超过2000000000的整数，M$200000。例如上面的例子就是A=(3，1，一4，2，8，-1000，2)。
2.u(1)，u(2)，…u(N)：表示第u(j)个元素被放进了Black Box里后就出现一个GET命令。例如上面的例子中u=(l，2，6，6)。输入数据不用判错。
输入格式：
第一行，两个整数，M，N。
第二行，M个整数，表示A(l)……A(M)。
第三行，N个整数，表示u(l)…u(N)。
输出格式：
输出Black Box根据命令串所得出的输出串，一个数字一行。
题意：动态查找一段区间的第K大值
法一：堆排序。注意到题目里面的信息“第i小的数，就是Black Box里的数的按从小到大的顺序排序后的第i个元素”，那么怎么维护第i小的数呢？维护一个大小为i的大顶堆，堆顶元素即是第i小的数。这里记h2表示大顶堆，h1表示小顶堆，每轮数据先读入h1，h1的顶部是这轮数据的最小值。这时候如果h2的大小为i，判断h2的堆顶（也就是h2的最大值）是不是比h1的堆顶（也就是h1的最小值）小，如果是的话，交换两者的值，知道h2堆顶的值小于等于h1堆顶的值。这时候输出h2堆顶的值即为所求，是不是很巧妙？思路参考自：https://www.luogu.org/blog/34238/solution-p1801
#include <iostream> #include<cstdio> #include<queue> using namespace std; priority_queue<int,vector<int>,greater<int> > h1;//小顶堆 priority_queue<int> h2;//大顶堆 int A[200010],u[200010]; int main(int argc, char** argv) { int m,n;scanf("%d %d",&m,&n); for(int i=1;i<=m;i++) scanf("%d",&A[i]); int last=1; int j=1; for(int i=1;i<=n;i++){ int k;scanf("%d",&k); for(;last<=k;last++){ h1.push(A[last]); } while(h2.size()<j&&(!h1.empty())){ int top=h1.top(); h1.pop(); h2.push(top); } while(h2.size()==j&&(!h1.empty())&&(h2.top()>h1.top())){ int top2=h2.top();h2.pop(); int top1=h1.top();h1.pop(); h2.push(top1); h1.push(top2); } printf("%d\n",h2.top()); j+=1; } return 0; }
法二：线段树单点更新，区间查询，二分查找。线段树的思想是每出现一个数，就在这个数的位置加上一个1，表示这个数出现了一次，然后从整个区间查询刚好i次的位置，输出这个位置对应的数即可。但注意要先离散化，因为区间范围为：-2000000000~+2000000000，非常大。具体见代码：
#include <iostream> #include<cstdio> #include<unordered_map> #include<algorithm> #define lson p<<1 #define rson p<<1|1 using namespace std; int A[200010]; int sum[200010<<2]; unordered_map<int,int> mp; void add(int p,int l,int r,int x,int c){ if(l==r){ sum[p]+=c; return; } int mid=(l+r)>>1; if(x<=mid) add(lson,l,mid,x,c); else add(rson,mid+1,r,x,c); sum[p]=sum[lson]+sum[rson]; } int quiry(int p,int l,int r,int a,int b){ if(a>r||(b<l)) return 0; if(a<=l&&r<=b){ return sum[p]; } int mid=(l+r)>>1; return quiry(lson,l,mid,a,b)+quiry(rson,mid+1,r,a,b); } int main(int argc, char** argv) { int m,n;scanf("%d %d",&m,&n); for(int i=1;i<=m;i++) {scanf("%d",&A[i]);mp[i]=A[i];}//离散化 sort(A+1,A+m+1); int last=1; int j=1; for(int i=1;i<=n;i++){ int cnt;scanf("%d",&cnt); for(;last<=cnt;last++){ int pos=lower_bound(A+1,A+m,mp[last])-A;//离散化 add(1,0,200010,pos,1); } int l=1,r=m; while(l<r){ int mid=(l+r)>>1; if(quiry(1,0,200010,0,mid)<j) l=mid+1; else r=mid; } printf("%d\n",A[l]); j+=1; } return 0; }
原文：https://www.cnblogs.com/zhuixunfighting/p/10261634.html