【25杭电春季营热身赛】 T1001 氯化钠

Problem Description

对于一个长度为 $n$ 的数组 $a$ ，定义 $val(l,r) =\min(a_l,a_{l+1},…,a_{r-1},a_r)+\max(a_l,a_{l+1},…,a_{r-1},a_r)$ 。小y想知道对于所有的 $val(l,r),1\le l \le r \le n$ ，降序排列后，第 $k$ 个数是多少，也就是第 $k$ 大的 $val$ 。

Input

第一行一个正整数 $T (T≤200)$ 表示数据组数。

对于每组数据：

第一行输入两个整数 $n$ 和 $k$，$(1≤n≤10^5，1≤k≤\frac{n(n+1)}{2})$ 分别表示数组长度，要求第多少大的 $val$。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示 $a_i$ 的值。 $(0≤a_i≤10^9)$ 。

保证 $∑n=1064824$。

Output

对于每组数据，输出一个整数，表示所有的 $val(l,r)$ ，$1≤l≤r≤n$ 中，第 $k$ 大的 $val$ 的大小。

Sample Input

2
5 3
1 2 3 3 4
10 10
9 6 7 5 5 4 7 2 5 8

Sample Output

7
13

题解

在刘春英老师发的题解上面补充

我们可以先确定最小值。去寻找当 $a_i$ 作为最小值时，区间的最左端 $L$ 和最右端 $R$ 在什么地方。换句话说，在 $[l,r],(L\le l \le i,i\le r \le R)$ 内这个区间的最小值都是 $a_i$ 。先令 $a_0 = a_{n+1} = -2e9$ ，假设遍历到了 $a_i$ ，找到最大的 $0 \le j <i$ ，满足 $a_j < a_i$ ，记 $le_i=j+1$。对于右边同理，找到最小的 $ i < j \leq n + 1 $ ，满足 $ a_j \leq a_i $ ，记 $ ri_i = j - 1$。至于为什么有一侧是严格小于，这是因为如果都是小于等于，后面算出来的区间就会有重复。举个例子，如果 $a=[1,1,1,1,1,1]$ ，分别取第三个和第四个 $1$ ，按照正确的方法求出来的区间分别是 $[1,3]$ 、$[1,4]$ ，如果两侧都是小于等于，那么求出来的区间都会是 $[1,6]$ ，当第三个和第四个 $1$ 分别作为最小值时，求出来的区间可能会有重复，因此必须要有一侧是严格小于。用单调栈就可以实现。

然后我们转化一下问题，当 $val$ 的大小为 $mid$ 时，二分求一下是否至少有 $k$ 个区间满足 $\max + \min \ge mid$ 。

考虑 check，考虑枚举每个 $a_i$ 作为 $\min$ ，再在所有区间 $[l, r], le_i \leq l \leq i, i \leq r \leq ri_i$ 中，统计多少个区间满足 $ \max \geq mid - \min $ 。可以以 $i$ 为起点做前缀 $\max$ ， $i$ 为终点做后缀 $\max$ ，发现这两个数组具有单调性，于是又可以二分找到最近的满足条件的前后缀最大值的下标，假设不合适的左右下标为 $ l_0, r_0 $ 。那么不合适的区间个数就是 $(i - l_0 + 1) \times (r_0 - i + 1)$ ，再用总的 $(i - le_i + 1) \times (ri_i - i + 1)$ 减去即可。check 用 st 表二分，或者线段树上二分，复杂度都是 $O(n \log n)$ 。

代码

#define int long long
const int N = 2e5 + 50;
int a[N];
int le[N], ri[N];
int lg2[N], f[N][20];
int n, k;
int query(int l, int r)
{
	int k = lg2[r - l + 1];
	return max(f[l][k], f[r - (1 << k) + 1][k]);
}

bool check(int x)
{
	int tot = 0;
	for (int i = 1; i <= n; ++i)
	{
		int l = le[i] - 1, r = i + 1;
		int L, R;
		while (l + 1 < r)
		{
			int mid = (l + r) >> 1;
			if (query(mid, i) < x - a[i])//mid-min
				r = mid;
			else
				l = mid;
		}
		L = r;
		l = i - 1, r = ri[i] + 1;
		while (l + 1 < r)
		{
			int mid = (l + r) >> 1;
			if (query(i, mid) < x - a[i])
				l = mid;
			else
				r = mid;
		}
		R = l;
		tot += (i - le[i] + 1) * (ri[i] - i + 1) - (i - L + 1) * (R - i + 1);
	}
	return tot >= k;
}

void solve()
{

	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	a[0] = -inf, a[n + 1] = -inf;
	stack<int> stk;

	for (int i = 2; i <= n; ++i)
		lg2[i] = lg2[i >> 1] + 1;
	for (int i = 1; i <= n; ++i)
		f[i][0] = a[i];
	for (int j = 1; j <= lg2[n]; ++j) // 初始化
	{
		for (int i = 1; i + (1 << (j - 1)) <= n; ++i)
		{
			f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
		}
	}

	for (int i = n + 1; i >= 0; --i)
	{

		while (!stk.empty() && a[stk.top()] > a[i]) // 此处可以更改比较关系
		{
			le[stk.top()] = i + 1;
			stk.pop();
		}
		stk.push(i);
	}
	while (!stk.empty())
		stk.pop();
	for (int i = 0; i <= n + 1; ++i)
	{

		while (!stk.empty() && a[stk.top()] >= a[i]) // 此处可以更改比较关系
		{
			ri[stk.top()] = i - 1;
			stk.pop();
		}
		stk.push(i);
	}

	int l = 0, r = inf;
	while (l + 1 < r)
	{
		int mid = l + r >> 1;
		if (check(mid)) // 二分答案 if(check(mid))
			l = mid;	// 最小化
		else
			r = mid;
	}
	cout << l << endl;
}