[CQOI 2009] 中位数

题目大意

给出 1n1 \sim n 的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是 bb

1n100,0001 \leqslant n \leqslant 100,000

题目链接

【SQOI 2009】中位数 - Luogu 1627

题解

DP。

找到值为 bb 的位置,记为 bPosbPos,记 f[i+n,  0]f[i + n, \; 0] 表示区间起点在 bPosbPos 左侧、区间终点为 bPosbPos、区间内比 bb 小的数比大的多 ii 个的区间数,记 f[i+n,  1]f[i + n, \; 1] 表示区间起点为 bPosbPos、区间终点在 bPodbPod 右侧、区间内比 bb 大的数比小的多 ii 个的区间数(与刚刚反过来了,为了方便计算答案,很巧的一点啊)。答案为:

i=1nn1f[i+n,  0]×f[i+n,  1]+f[n,  0]+f[n,  1]\sum_{i = 1 - n}^{n - 1} f[i + n, \; 0] \times f[i + n, \; 1] + f[n, \; 0] + f[n, \; 1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
const int MAXN = 100005;
int a[MAXN], f[MAXN << 1][2];
int main(){
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("%d\n", ans);
return 0;
}