模拟赛题讲解[21]

来自 yukuai26 2022-10-06 noi.ac #2849

题目描述：

小明给你一个 \(1\sim N\) 的排列，他想问你该排列有多少个长度为奇数的连续子序列的中位数是 \(K\)。

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

输入格式：

第一行为两个正整数 \(N\) 和 \(K\)。

第二行为 \(1\sim N\) 的排列。

输出格式：

一个整数表示答案。

样例输入：

7 4
5 7 2 4 3 1 6

样例输出：

4

数据范围：

对于 \(100\)% 的数据，\(1 \leq k \leq n \leq 10^5\)

---

题解：

注意到 \(k\) 作为中位数的区间一定满足「小于 \(k\) 的数的个数」等于「大于 \(k\) 的数的个数」。记 \(p\) 为 \(k\) 的位置。

因此我们可以把小于 \(k\) 的置为 \(-1\) ，把大于 \(k\) 的置为 \(1\) ，然后把 \(p\) 左右的所有可能的值的出现次数记录。

具体地，设 \(f(i)\) 表示以 \(p-1\) 为起点和为 \(i\) 的子段的出现次数

同理设 \(g(i)\) 表示以 \(p+1\) 为起点和为 \(i\) 的子段的出现次数，则答案为 \[ f(0) + g(0) + 1+ \sum f(i) \times g(-i) \] \(f(0)+g(0)\) 表示不要 \(p\) 右边的部分和不要 \(p\) 左边的部分的方案数，\(+1\) 是 \(p\) 自己一个也算

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,k,res,p,sum,a[N],f[N*2+15],g[N*2+15];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k;
    for(int i=1; i<=n; i++)
        cin >> a[i], a[i] = ((a[i] == k && (p = i)) ? 0 : (a[i] < k ? -1 : 1));
    // for(int i=1; i<=n; i++) cout << a[i] << " \n"[i==n];
    sum = 0; for(int i=p-1; i; i--) sum += a[i], ++f[sum + N];
    sum = 0; for(int i=p+1; i<=n; i++) sum += a[i], ++g[sum + N];
    for(int i=-n; i<=n; i++) res += f[N-i] * g[N+i]; res += f[N]; res += g[N]; ++res;
    cout << res << '\n';
    return 0;
}