【每日一题】中位数图

题意

给定一个 排列，求长度为奇数子串以 为中位数的子串个数。

solution

由于求的是中位数，所以我们只需要关心这个数和 的大小关系就好了，大于 看作 1，小于 看作 -1，等于 看作 0，问题转化为求包含 0 且和为 0 的子串有多少个。

从 的位置开始遍历，map 统计右边累加的和，然后从左边累加的和中查找对应的相反数个数，累加即可。同时，如果遍历过程中任何一边已经存在和为 0 的情况，也为可行解。

Code

#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
int n, b, sum, pos, res, a[200005];
int main() {
  cin >> n >> b;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (a[i] > b)
      a[i] = 1;
    else if (a[i] < b)
      a[i] = -1;
    else if (a[i] == b) {
      a[i] = 0;
      pos = i;
    }
  }
  for (int i = pos + 1; i <= n; i++) {
    sum += a[i];
    mp[sum]++;
    if (sum == 0) res++;
  }
  sum = 0;
  for (int i = pos - 1; i; i--) {
    sum += a[i];
    res += mp[-sum];
    if (sum == 0) res++;
  }
  cout << res + 1 << '\n';
  return 0;
}