传送门 NC19913 [CQOI2009]
中位数为 b b b 的连续子序列，由于数组为 1 − n 1-n 1−n 的排列，故子序列中 x ( x < b ) x(x<b) x(x<b) 与 y ( y > b ) y(y>b) y(y>b) 的数量相等。
s ′ [ i ] = { 1 s [ i ] > b 0 s [ i ] = b − 1 s [ i ] < b s'[i]=\begin{cases} 1 & s[i]>b\\ 0 & s[i]=b\\ -1 & s[i]<b\\ \end{cases} s′[i]=⎩⎪⎨⎪⎧10−1s[i]>bs[i]=bs[i]<b
设 b b b 索引为 i i i，维护其左右区间的前缀和，统计满足 [ l , r ] ( l ∈ [ 0 , i ] , r ∈ [ i , n ) [l,r](l\in [0,i],r\in [i,n) [l,r](l∈[0,i],r∈[i,n) 的区间和为 0 0 0 的区间数即可。
#include <bits/stdc++.h> using namespace std; #define maxn 200005 int n, b, s[maxn], f[maxn]; int main() { scanf("%d%d", &n, &b); int p, sum = 0; for (int i = 0; i < n; i++) { scanf("%d", s + i); if (s[i] == b) { p = i, s[i] = 0; continue; } s[i] = (s[i] > b ? 1 : -1); } for (int i = p; i >= 0; i--) { sum += s[i]; f[n + sum]++; } long long res = 0; sum = 0; for (int i = p; i < n; i++) { sum += s[i]; res += f[n - sum]; } printf("%lld", res); return 0; }