题目传送门: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; }
Comments NOTHING