link

0x00 思路

「可怜有一个长度为 \(n\) 的正整数序列 \(A\)，但是她觉得 \(A\) 中的数字太小了，这让她很不开心。」

「于是她选择了 \(m\) 个区间 \([l_i, r_i]\) 和两个正整数 \(a, k\)。她打算从这 \(m\) 个区间里选出恰好 \(k\) 个区间，并对每个区间执行一次区间加 \(a\) 的操作。（每个区间最多只能选择一次。）」

「对区间 \([l, r]\) 进行一次加 \(a\) 操作可以定义为对于所有 \(i\in [l, r]\)，将 \(A_i\) 变成 \(A_i + a\) 。现在可怜想要知道怎么选择区间才能让操作后的序列的最小值尽可能的大，即最大化 \(\min_{i=1}^{n} {A_i}\)。」

很明显，这道题有区间加，有查询，所以可以想到用树状数组。不应该是线段树？

接着，我们可以观察到：
「让操作后的序列的最小值尽可能的大」

因此，我们可以很容易的想到二分（因为二分就是用来解决最小值最大，最大值最小的）。

0x01 优化

当然，虽然我们用了二分把时间进行了一次优化，但是对于 \(3000ms\) 来说，还是太慢了。所以我们需要进一步的优化。那么就需要我们先理解这个思路到底要我们做什么。我们二分的肯定是答案，即最小值的最大值为多少。因为我们可以对一个较大的区间去一次寻找中间值，看在满足使用 \(k\) 个区间及以内这个条件的时候能否满足此答案。

现在的问题就是：我到底该怎么选择这 \(k\) 个区间才能使得选择方案最优？

不好确定对不对？

既然我们没法很容易的得出最优方案，所以我们可以尝试用贪心来想一想。

当然，我们可以一个元素一个元素的去解决（使得当前元素满足答案或者无法满足），这样再去思考怎么选择区间最优不就容易了吗？

由于我们是一个一个元素思考的，那么在这个元素左边的元素一定都符合条件，所以我们为了使得用区间个数尽可能少，一定会由于贪心思想而选择区间端点最靠右且未被用过的，以尽可能减少使用区间的个数。若我们仍然无法满足二分的答案，那么就一定做不到这个值了。

当然，还可以使用优先队列再次优化时间。

code

#include
#define lowbit(x) (x&(-x))
using namespace std;
const int N=2e5+5;
int n,q,k,a;
long long tree[N],m[N],dif[N],sum[N];
bool book[N];
typedef struct Questions//存区间
{
	int l,r;
	friend bool operator<(const Questions& a,const Questions& b)
	{
		return a.rb.r:a.lQ;//用优先队列直接查找右端点最靠右的，节省时间
	int i,j,num=0;
	memset(book,0,sizeof(book));
	for(i=1;i<=n;i++)
		tree[i]=sum[i]-sum[i-lowbit(i)];
	for(i=1;i<=n;i++)
	{
		if(ques(i)>=x)
			continue;
		for(j=1;j<=q&&sec[j].l<=i;j++)
			if(sec[j].r>=i&&!book[j])//每个区间只能用一次
				Q.push(sec[j]),book[j]=1;
		while(ques(i)k)
			return 0;
	}
	return 1;
}
int ef(int l,int r)//二分
{
	if(l==r)
		return l;
	if(l==r-1)
	{
		if(check(r))
			return r;
		return l;
	}
	int mid=l+r>>1;
	if(check(mid))
		return ef(mid,r);
	return ef(l,mid-1);
}
int main()
{
	int i,j,T,l=0,r=1e9;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d %d %d",&n,&q,&k,&a); 
		sum[0]=0;
		for(i=1;i<=n;i++)
		{
			scanf("%lld",&m[i]);
			dif[i]=m[i]-m[i-1];
			sum[i]=sum[i-1]+dif[i];//初始化
		}
		for(i=1;i<=q;i++)
			scanf("%d %d",&sec[i].l,&sec[i].r);
		sort(sec+1,sec+1+q,cmp);
		printf("%d\n",ef(l,r));
	}
	return 0;
}