题目传送门：E - Max Min (atcoder.jp)

题目大意

给定N，X，Y和一个长度为N的序列。

求该序列中最大值为X，最小值为Y的连续子序列的数量。

PS：以下所讲的子序列均指连续子序列。

思路

一开始没想到是容斥原理，看了Jinagly大佬的代码才豁然开朗。

函数getRangeOf(X, Y)返回最小值大于等于Y，最大值小于等于X的子序列的数量。

那么根据容斥原理，我们要得到最小值为Y，且最大值为X的子序列数量，那么就要从getRangeOf(X, Y)中减去(X - 1,Y)和(X, Y - 1)，因为多减去了一个重复部分(X - 1,Y + 1)，所以加上(X - 1,Y + 1)就是答案。

有点像二维前缀和的思路。

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
const int maxn = 2e5 + 9;

int a[maxn], N, X, Y;

int getRangeOf(int x,int y)//x最大值，y最小值 
{
	int res = 0;
	for(int i = 1,j = 1;i <= N; ++ i)
		if(a[i] > x || a[i] < y)j = i + 1;
		else res += i - j + 1;
	return res;
}

signed main()
{
	cin >> N >> X >> Y;
	for(int i = 1;i <= N; ++ i)scanf("%lld", a + i);
	cout << getRangeOf(X, Y) - getRangeOf(X - 1,Y) - getRangeOf(X, Y + 1) + getRangeOf(X - 1,Y + 1);
	return 0;
}