[CQOI2009] 中位数

不错的思维题

传送门：$>here<$

---

题意：给出一个N的排列，求出其中有多少个连续子段的中位数是b

数据范围：$N leq 100000$

---

 $Solution$

先考虑中位数的意义：一个序列中，大于它的与小于它的一样多。而由于中位数已经确定，所以最终的序列一定包含它所在的那个位置。

设$$c[i]=egin{cases}0 & ext{} a[i]==b \ 1 & ext{} a[i]>b \ -1 & ext{} a[i]<b end{cases}$$

于是如果我们统计一个$sum[i]$表示$c[i]$的前缀和，在开一个桶表示左侧右侧对应的个数。就可以得到答案

$$ans = sumlimits_{i=-N}^{+N}bl[i]*br[-i]$$

注意下标不能为负数

反思

对于无论是平均数还是中位数，对于计算机来说都不好处理。此时最好的办法就是还原为最简单的求和问题

$my code$

/*By DennyQi 2018*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100010;
const int INF = 1061109567;
const int ad = 1e5;
inline int Max(const int a, const int b){ return (a > b) ? a : b; }
inline int Min(const int a, const int b){ return (a < b) ? a : b; }
inline int read(){
    int x = 0; int w = 1; register char c = getchar();
    for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());
    if(c == '-') w = -1, c = getchar();
    for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;
}
int N,B,pos,Ans;
int a[MAXN],c[MAXN],sum[MAXN],bl[MAXN*2],br[MAXN*2];
int main(){
    N = read(), B = read();
    for(int i = 1; i <= N; ++i){
        a[i] = read();
        if(a[i] < B) c[i] = -1;
        if(a[i] > B) c[i] = 1;
        if(a[i] == B) pos = i;
        sum[i] = sum[i-1] + c[i];
    }
    for(int i = 0; i < pos; ++i){
        bl[sum[pos-1]-sum[i]+ad]++;
    }
    for(int i = pos; i <= N; ++i){
        br[sum[i]-sum[pos]+ad]++;
    }
    for(int i = -N; i <= N; ++i){
        Ans += bl[i+ad] * br[-i+ad];
    }
    printf("%d", Ans);
    return 0;
}