[CQOI2009]中位数图

说白了这就是个前缀和

做法

设

$f(x)= \begin{cases} 1& \text{x > b}\\ 0& \text{x = b}\\ -1& \text{x < b} \end{cases} \\$ $s(x) = \sum_{i=1}^{x} f(i)$

显然，当 $s(i) - s(j) = 0$ 且 $i \equiv j ( \mod 2)$ ，说明 $a_{i...j}$ 这个连续子序列的中位数是 $b$ ，开个桶统计一下前缀和即可。

CODE

#include<bits/stdc++.h>
using namespace std;
#define I inline
#define ri register int
#define ll long long
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , u) for(ri i = head[u] ; i ; i = e[i].nxt)

I int read() {
    int s = 0 ,w = 1; char ch = getchar();
    while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
    while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
    return s * w;
}
const int N = 1e6 + 5 , P = 1e6;
int n , m , s[N * 2] , a[N * 2][2] , Ans;

signed main() {
    n = read() , m = read();
    a[P][0] = 1;
    For(i , 1 , n) {
        int x = read(); s[i] = s[i - 1];
        if(x > m) ++ s[i]; 
        if(x < m) -- s[i];
        Ans += a[s[i] + P][(i + 1) & 1];
        ++ a[s[i] + P][i & 1];
    }
    cout << Ans << endl;
    return 0;
}