本文共 827 字，大约阅读时间需要 2 分钟。

解法:

转换题意后，这题就是给定一个序列a，给出m个询问，问[0,k]的第pos小的数.

特殊就特殊在是从0开始的。

可以保存询问，我们让不同的询问ki从小到大排列，从小到大枚举k，将前ki个数存入树状数组，这时候可以通过二分答案来枚举答案mid，查询小于等于mid的数num，找出num=pos的最小的mid，就是第pos小的数了。

时间复杂度是O(nlog^2n)

应该能更快...还没去想

#include 
   
    using namespace std;const int maxn=2e5+5;struct node{    int x, y;}a[maxn], b[maxn];int c[maxn];int bit[maxn];int cmp(node a, node b){    if(a.x>b.x)return 1;    else if(a.x==b.x)    {        if(a.y
    
     0; i-=lowbit(i))sum+=bit[i];//    printf("sum\n");    return sum;}int ans[maxn];int main(){    int t, i, j, n, m;        scanf("%d", &n);        for(i=0; i
     
      >1;                if(sum(mid+1)>=q[i].pos)                {                    mi=min(mi, mid);                    r=mid-1;                }                else l=mid+1;            }            ans[q[i].id]=mi;        }        for(i=0; i
     
    
   

转载地址：http://nnywb.baihongyu.com/