【BZOJ】2086: [Poi2010]Blocks

题意

(n(1 le n le 1000000))个数(a_i(a_i le 10^9))。(m(1 le m le 50))次询问，每次给出一个(k(k le 10^9))，可以执行操作：每次选择一个大于(k)的(a_i)，将(a_i)减去(1)，然后将(a_{i-1})或(a_{i+1})加上(1)。然后求一个最长的连续子序列使得每个数都不小于(k)。

分析

对于任意一串子序列([l, r])，如果(sum_{i=l}^{r} a_i ge (r-l+1)*k)，则显然合法。

题解

所以首先将(a_i)减掉(k)，然后求最大的(r-l)满足((s_r - s_l) ge 0 (0 le l < r le n))
发现不是很好求，于是有神做法：
首先求出关于(a_i)单调不增的栈(s)，然后从右向左扫，由于求的是最大的(r-l)，所以现在(r)(当前在(i))是逐渐减小，那么(l)(假设为(j))也要逐渐减小才对答案有贡献。所以就算存在一个(k(k>j))满足(s_i - s_k ge 0)，对答案也是没贡献的。所以我们找到在栈里找到一个最小的(j)满足(s_i-s_j ge 0)即可。

#include <bits/stdc++.h>
using namespace std;
inline int getint() {
	int x=0, c=getchar();
	for(; c<48||c>57; c=getchar());
	for(; c>47&&c<58; x=x*10+c-48, c=getchar());
	return x;
}
const int N=1000005;
typedef long long ll;
int a[N], s[N];
ll b[N];
int main() {
	int n=getint(), m=getint();
	for(int i=1; i<=n; ++i) {
		a[i]=getint();
	}
	for(int t=1; t<=m; ++t) {
		int k=getint(), *top=s;
		*++top=0;
		for(int i=1; i<=n; ++i) {
			b[i]=a[i]-k+b[i-1];
			if(b[*top]>b[i]) {
				*++top=i;
			}
		}
		int ans=0;
		for(int i=n; i; --i) {
			for(; top!=s && b[*top]<=b[i]; --top);
			ans=max(ans, i-*(top+1));
		}
		printf("%d%c", ans, " 
"[t==m]);
	}
	return 0;
}