首页 > itarticle > [bzoj 1303][cqoi 2009] 中位数图

[bzoj 1303][cqoi 2009] 中位数图

admin 1月 29, 2021 0

题目大意

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

(1 leqslant n leqslant 100,000)

题目链接

题解

DP。

找到值为 (b) 的位置，记为 (bPos)，记 (f[i + n, ; 0]) 表示区间起点在 (bPos) 左侧、区间终点为 (bPos)、区间内比 (b) 小的数比大的多 (i) 个的区间数，记 (f[i + n, ; 1]) 表示区间起点为 (bPos)、区间终点在 (bPod) 右侧、区间内比 (b) 大的数比小的多 (i) 个的区间数（与刚刚反过来了，为了方便计算答案，很巧的一点啊）。答案为： [
sum_{i = 1 - n}^{n - 1} f[i + n, ; 0] times f[i + n, ; 1] + f[n, ; 0] + f[n, ; 1]
]

代码


const int MAXN = 100005;
int a[MAXN], f[MAXN << 1][2];
int (){
    int n, b;
    scanf("%d%d", &n, &b);
    int bPos;
    for (int i = 0; i < n; i++){
        int x;
        scanf("%d", &x);
        a[i] = x;
        if (x == b) bPos = i;
    }
    int d = 0;
    for (int i = bPos - 1; i >= 0; i--){
        if (a[i] < b) d--;
        if (a[i] > b) d++;
        f[d + n][0]++;
    }
    d = 0;
    for (int i = bPos + 1; i < n; i++){
        if (a[i] > b) d--;
        if (a[i] < b) d++;
        f[d + n][1]++;
    }
    int ans = 1;
    for (int i = 1; i <= 2 * n - 1; i++){
        if (i == n) ans += f[i][0] + f[i][1];
        ans += f[i][0] * f[i][1];
    }
    printf("%dn", ans);
    return 0;
}