区间查找题解（优先队列+二分）

Problem:C

Time Limit:1000ms

Memory Limit:65535K

Description

给定两个长度为 n 的数组 A 和 B，对于所有的 ai+bj 从小到大排序，并输出第 L 个到第 R 个数。

Input

第一行三个数 n,L,R。然后分别输入a[i]和b[i];

Output

输出第L个数到第R个数！

Sample Input

2 1 4
1 3
2 4

Sample Output

3 5 5 7 
注意最后的数后面带1个空格！

Hint

1<=n<1e5;1<=L<=R<=n^2;R-L<1e5;1<=a[i],b[i]<=1e9;

思路：

可以先看看我的另一篇题解：洛谷1631 序列合并（优先队列）_yusen_123的博客-CSDN博客

n^2个和，可以分成n个序列。

A[1]+B[1] <= A[1]+B[2] <= … <= A[1]+B[N]

A[2]+B[1] <= A[2]+B[2] <= … <= A[2]+B[N]

……

A[N]+B[1] <= A[N]+B[2] <= … <= A[N]+B[N]

二分找大于等于第L-1个相加数的最小数（二分时有个小技巧，可以在o(n)的时间复杂度下求<=x的数有多少）。

找到大于等于第L-1个相加数的最小数x，统计每个序列<=x有多少个数；找到每个数列>x的第一个数入优先队列。

注意：当第l-1和之后的若干个数相等时，cnt>l-1，我们可以先输出cnt-l+1个x，再更新下l；

对于每一个序列，我们维护一个最小值，用优先对列，当某一行一个数被输出，我们就让这行下一值进入优先队列。

代码：

#define _CRT_SECURE_NO_WARNINGS 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

        while (cn > 0 && a[i] + b[cn] > ans)
            cn--;
        cnt += cn;
        if (cn + 1 <= n)
            q.push({ i,(int)cn + 1,a[i] + b[cn + 1] });
    }
    if (cnt > L - 1)
    {
        for (LL i = L; i <= min(cnt, R); i++)
            printf("%lld ", ans);
        L = cnt + 1;
    }
    cnt = R - L + 1;
    cn = 0;
    while (!q.empty())
    {
        o = q.top();
        q.pop();
        if (cn == cnt)
            break;
        printf("%lld ", o.cn), cn++;
        if (o.j + 1 <= n)
            q.push({ o.no,o.j + 1,a[o.no] + b[o.j + 1] });
    }
    return 0;
}