关于本题的一个想法

我们知道，观察连续三个数的结构可以给出

L

的上界或者下界的范围。

但是如果加入

a_x=a_{x-1}

的情况我们还能发现

L

不能取

a_x

这一个值，在本题中完全不判不能取单个值的情况却能够AC？

所以是数据放水了还是我上面提到的情况其实不合法？

求教。

给出代码方便理解我的想法：

CPP

void check(int x)
{
	if(a[x] >= a[x - 1] && a[x] >= a[x + 1]) b[x] = min(a[x] + a[x + 1] + 1, a[x] + a[x - 1] + 1);
	if(a[x] <= a[x - 1] && a[x] <= a[x + 1]) c[x] = max(a[x] + a[x + 1] - 1, a[x] + a[x - 1] - 1);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i], a[i] <<= 1;
	}
	for(int i = 1; i <= n; i++)
	{
		b[i] = -1e18; c[i] = 1e18;
		p1[i] = -1e18; p2[i] = 1e18;
		if(i > 1 && i < n) check(i);
	}
	int ans = 1;
	int l = 0, r = 1, mid = 0;
	while(l < n - 2)
	{
		l++;
		if(l > mid)
		{
			for(int j = r; j >= l; j--)
			{
				p1[j] = max(p1[j + 1], b[j]);
				p2[j] = min(p2[j + 1], c[j]);
			}
			mid = r;
			down = -1e18; up = 1e18;	
		}
		while(r < n && min(p2[l + 1], up) >= max(p1[l + 1], down))
		{
			r++;
			down = max(down, b[r]);
			up = min(up, c[r]);
		}
		ans += r - l;
	}
	cout << ans;
	return 0;
}

关于本题的一个想法

讨论操作

回复

相关推荐

关于本题的一个想法