Blocks（单调栈）

Blocks

题目描述

给出N个正整数a[1..N]，再给出一个正整数k，现在可以进行如下操作：每次选择一个大于k的正整数a[i]，将a[i]减去1，选择a[i-1]或a[i+1]中的一个加上1。经过一定次数的操作后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于

k。 总共给出M次询问，每次询问给出的k不同，你需要分别回答。

输入：第一行两个正整数N (N <= 1,000,000)和M (M <= 50)。 第二行N个正整数，第i个正整数表示a[i] (a[i] <= 10^9)。 第三行M个正整数，第i个正整数表示第i次询问的k (k <= 10^9)。

输出：共一行，输出M个正整数，第i个数表示第i次询问的答案。

样例

输入

5 6
1 2 1 1 5
1 2 3 4 5 6

输出

5 5 2 1 1 0

题解

只要区间平均值大于等于 \(k\) 就是合法的，可以让每一个值减 \(k\)，这样只要区间和大于 \(0\) 就是合法的，所以可以维护前缀和 \(sum[i]=sum[i-1]+a[i]-k\) ，判断 \(sum[r]>=sum[l-1]\)。

建一个栈，先压一条从零开始的单调递减序列（不是单调栈，就是单纯递减序列），以栈首元素为左端点，如果一个点没有进栈，那它一定大于等于栈首元素，说明这是一个合法区间，直到有一个点比栈首小，这个区间不合法，进栈（如图1）。

然后得到一个单调递减的序列，以每个元素为左端点，到下一个元素之前的任意一点为右端点都是合法的，

但要求的是最大区间，为什么先要求单调递减序列呢？既然左端点确定了，那就倒序循环遍历右端点，单调递减序列就是为了从右往左找左端点，每遍历到一个点只需要按单调栈的方式，把栈首比它小的 \(pop\) ，记录最后一个就是最左端的，如果之后有一个点，比它小的已经被 \(pop\) 了怎么办？
这时它能找到的最优解一定小于之前的最优解，贪心直接无视它。

#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
#define int long long
int n,m,k,a[N],ans,sum[N],out,mx;

main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		mx=max(mx,a[i]);
	}
	while(m--)
	{
		deque <int> q;
		scanf("%lld",&k);
		out=0;
		if(k>mx)
		{
			printf("0 ");continue;
		} 
		for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]-k;
		q.push_back(0);
		for(int i=1;i<=n;i++) if(sum[i]<sum[q.back()])
		q.push_back(i);
		int c=0;
		for(int i=n;i>=0;i--)
		{
			while(!q.empty()&&sum[i]>=sum[q.back()])
			{
				c=q.back();
				q.pop_back();
			}
			if(sum[c]<=sum[i])
			out=max(out,abs(i-c));
		}
		printf("%lld ",out);
	}
	return 0;	
} 

总结

想到平均值，与区间和有关，那就想办法维护前缀和，将区间和大于零转换为两个前缀和大小关系，建栈维护前缀和单调序列，找合法区间，再扩右边界（实际操作是遍历右边界，找已经维护好的左边界）。