万红丛中小片绿

第一篇题解思路（没有代码那篇）

#include <bits/stdc++.h>
using namespace std;
const int N = 100006;
int n, a[N], q, x, y, maxn[N][31], minn[N][31], m, ans, lef, rig, f[N], mid, mm;
int query(int l, int r)
{
    int z = log2(r - l + 1);
    return max(maxn[l][z], maxn[r - (1 << z) + 1][z]);
}
int main()
{
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i), maxn[i][0] = a[i], f[a[i]] = i;
	for (int i = 1; i <= 22; i++)
		for (int j = 1; j + (1 << i) - 1 <= n; j++)
			maxn[j][i] = max(maxn[j][i - 1], maxn[j + (1 << (i - 1))][i - 1]);
	a[0] = a[n + 1] = (1 << 30);
	while(q--)
	{
		scanf("%d%d", &x, &y);
		if (x - y + 1 <= 0 && x + y - 1 > n)
		{
			printf("0\n");
			continue;
		}
		if (y == 1)
		{
			printf("1\n");
			continue;
		}
		ans = 0;
		if (y == 2)
		{
			ans = (x != 1 && (x == 2 || a[x - 2] > a[x])) + (x != n && (x == n - 1 || a[x + 2] > a[x]));
			printf("%d\n", ans);
			continue;
		}
		if (x - y + 1 > 0)
		{
			lef = x - y + 1;
			rig = x;
			m = query(lef, rig);
			if (m == a[rig])
			{
				if (lef == 1 || a[lef - 1] > m)
					ans += y - 1;
			}
			else if (m == a[lef])
				ans = (lef == 1 || query(lef + 1, rig) < a[lef - 1]);
			else if (a[lef - 1] > a[rig])
			{
				mm = query(f[m] + 1, rig);
				if (mm > query(lef, f[m] - 1))
					ans += (f[mm] - lef);
			}
			else
			{
				mm = query(f[m] + 1, rig);
				if (mm > query(lef, f[m] - 1) && mm < a[lef - 1])
					ans++;
			}
		}
		if (x + y - 1 <= n)
		{
			lef = x;
			rig = x + y - 1;
			m = query(lef, rig);
			if (m == a[lef])
			{
				if (rig == n || a[rig + 1] > m)
					ans += y - 1;
			}
			else if (m == a[rig])
				ans = (rig == n || query(lef, rig - 1) < a[rig + 1]);
			else if (a[lef - 1] > a[rig])
			{
				mm = query(lef, f[m] - 1);
				if (mm > query(f[m] + 1, rig))
					ans += (f[mm] - lef);
			}
			else
			{
				mm = query(lef, f[m] - 1);
				if (mm > query(f[m] + 1, rig) && mm < a[rig + 1])
					ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}