NC19913 [CQOI2009]中位数图

题目地址：

https://ac.nowcoder.com/acm/problem/19913

基本思路：

最近几天都没写题解，感冒了难受QAQ。这题比较经典的套路了，我们观察这是1~n的排列，也就是说只在数组中出现一次，知道了这个我们想假如令小于的数为，大于的数为，等于的数为，那么要找到题目要求的连续子序列，我们只要在的位置左右找到两个位置使其满足加上的和为，这部分我们可以根据前缀和先算一边的情况，然后用map储存每个数的出现次数，然后再算另一边的时候加上map里储存的次数就是了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 1e5 + 10;
int n,b,a[maxn],sum[maxn];
map<int,int> memo;
signed main() {
  IO;
  cin >> n >> b;
  int pos = 0;
  rep(i,1,n){
    cin >> a[i];
    if(a[i] == b) pos = i;
  }
  rep(i,1,n){//将数组b转化成只含0,-1,1的数组;
    if(a[i] < b) sum[i] = -1;
    else if(a[i] > b) sum[i] = 1;
    else sum[i] = 0;
  }
  int pre = 0,ans = 0;
  //找右边的位置，并且map记录次数;
  rep(i,pos,n) { pre = pre + sum[i]; memo[-pre]++; }
  pre = 0;
  per(i,pos,1) {
    pre = pre + sum[i];
    ans += memo[pre];//如果出现了左边部分和等于右边部分和取负，那么这段区间就是可行的;
  } 
  cout << ans << '\n';
  return 0;
}