区间查找，二分，思维

Contest (nefu.edu.cn)

区间查找

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;

解析：

 这道题与P1631 序列合并，思维，优先队列-CSDN博客道题相近

这不过需要用二分将第L下的数求出来

需要注意：

这里二分求得是第L-1小的数+1

为什么不直接求第L小的数呢？

直接求第L小的数可能会因为数组第L小得数相邻得数与他一样而求成比他大1的数，这样后需处理就会很麻烦，所以直接求第L-1小的数+1

具体看代码：
 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
LL n, l, r;
LL a[N], b[N],to[N];
typedef struct st {
	LL first, second;
}st;
 
 
int check(LL num, LL lim) {
	LL cnt = 0;
	int p = n;
	for (int i = 1; i <= n; i++) {
		while (p >= 1 && a[i] + b[p] >= num)p--;//慢慢体会，非常妙
		cnt += (LL)p;
	}
	return cnt >= lim;
}
 
LL bin(LL L, LL R, LL lim) {
	LL mid, ret = 0;
	while (L <= R) {
		mid = L + (R - L) / 2;
		if (check(mid,lim)) {
			ret = mid;
			R = mid - 1;
		}
		else {
			L = mid + 1;
		}
	}
	return ret;
}
 
bool operator>(const st& a, const st& b) {
	return a.first > b.first;
}
 
int main() {
	scanf("%lld%lld%lld", &n, &l, &r);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &b[i]);
	}
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + n);
	LL lnum=bin(0,(LL)2e9+5, l - 1);//二分结果为第L个数字加1
	LL cnt = 0;
	for (int i = 1,p=n; i <= n; i++) {
		to[i] = ((i == 1) ? n : (to[i - 1]));
		while (to[i] > 0 && a[i] + b[to[i]] >= lnum)--to[i];//慢慢体会，非常妙
		cnt += (LL)to[i];
	}
	for (LL i = l; i <= min(cnt, r); ++i)printf("%lld ", lnum - 1);//特殊情况处理，如，1，5，5，5，5，5，9，求第5到第7个数
	l = cnt + 1;
	priority_queue < st, vector, greater>q;
	for(int i = 1; i <= n; i++) {
		if (to[i] < n)q.push({ (a[i] + b[++to[i]]), (i) });
	}
	int t;
	for (LL i = l; i <= r; i++) {
		printf("%lld ", q.top().first);
		t = q.top().second;
		q.pop();
		if(to[t]
			q.push({ a[t] + b[++to[t]], t });
		
	}
	return 0;
}