Powered by:NEFU AB-IN

【CQOI2009】中位数图

• 题意

  给出$1-n$的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是$b$。

  中位数是指把所有元素从小到大排列后，位于中间的数。

• 思路

  遇到中位数的题，可以往两方面想

  • 大于中位数的记为$1$，小于中位数的记为$-1$
  • 堆栈

  明显这个题可以采用第一种思路

  既然是排列，那么就可以先找出这个数的位置，然后从这个位置开始，往左往右开始遍历，并记录前缀和，当$l\_sum[x]+r\_sum[y]=0$时，说明这个可行

  注意：

  • 下标可能有负数，因此每个数加上一个$n$
  • 中位数本身就是$0$，那么自己就是一个连续子序列，而且还可以和左右是$0$的组成序列，可以发现是$0$的点不可能与中位数组成偶数长度，因为加一减一奇数不会构成$0$，所以$sum$初始值是$l\_sum[n]+r\_sum[n]+1$
  • 不用考虑长度是偶数的情况，还是因为上面的原因

  

• 代码

  /*
   * @Author: NEFU AB_IN
   * @Date: 2021-09-08 16:24:12
   * @FilePath: \Vscode\ACM\NiuKe\2021.9.8\b.cpp
   * @LastEditTime: 2021-09-08 16:36:57
   * @brief 【CQOI2009】中位数图
   */
  #include <bits/stdc++.h>
  using namespace std;
  #define LL long long
  #define MP make_pair
  #define SZ(X) ((int)(X).size())
  #define IOS                      \
      ios::sync_with_stdio(false); \
      cin.tie(0);                  \
      cout.tie(0);
  #define DEBUG(X) cout << #X << ": " << X << endl;
  typedef pair<int, int> PII;
  
  const int N = 1e6 + 10;
  int a[N], l[N << 1], r[N << 1];
  int n, k;
  
  signed main()
  {
      IOS;
      cin >> n >> k;
      int pos;
      for (int i = 1; i <= n; ++i)
      {
          cin >> a[i];
          if (a[i] == k)
              pos = i;
      }
      int sum = 0;
      for (int i = pos - 1; i >= 1; --i)
      {
          sum += (a[i] > k) ? 1 : -1;
          l[sum + n]++;
      }
      sum = 0;
      for (int i = pos + 1; i <= n; ++i)
      {
          sum += (a[i] > k) ? 1 : -1;
          r[sum + n]++;
      }
      sum = l[n] + r[n] + 1;
      for (int i = 0; i <= 2 * n; ++i)
      {
          sum += l[i] * r[2 * n - i];
      }
      cout << sum << '\n';
      return 0;
  }
  
  

完结