[ABC247E] Max Min 题解

FFTotoro · 2022-10-22 21:07:56 · 题解

本题需要应用容斥原理。

题目要求统计 A 中满足最大值为 X，最小值为 Y 的连续子序列的个数。

首先，如果 A 中包含比 X 大的元素，那么子序列肯定不能包含它，于是，它就把目前的序列分成了两个序列。

例如，A=(21,23,3,21,7,20),X=22,Y=6，A 中的 23 肯定不能被包含，于是 A 就被划分成了 (21) 和 (3,21,7,20)。

所以，对于每个分割出来的子序列（暂且称为 B），我们只需寻找有多少个 B 的连续子序列 C 既包含 X 又包含 Y。

这是容斥原理就派上用场了：

设 L 为所有子序列，P 为不包含 X 的所有子序列，Q 为不包含 Y 的所有子序列，那么答案就是 |L|-|P|-|Q|+|P\cap Q|。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n,x,y; cin>>n>>x>>y;
  vector<int> a(n);
  for(auto &i:a)cin>>i;
  auto f=[&](int x,int y){
    int c=0;
    for(int i=0,j=0;i<n;i++){
      if(a[i]<y||a[i]>x)j=i+1;
      c+=i-j+1;
    }
    return c;
  };
  cout<<f(x,y)-f(x-1,y)-f(x,y+1)+f(x-1,y+1)<<endl;
  return 0;
}