[Solution]CQOI2009 中位数

【题目】

戳这里

【思路】

记录一个新序列,新序列中的数为,-1代表原序列的当前位置的数小于b,1表示大于b,0表示等于b.

计算新序列前缀和,如果两个位置的前缀和的话,证明这一段区间内大于b的个数等于小于b的个数,那么如果这段区间包含b这个数,这一段区间一定是满足条件的区间。

记b的位置为ins,不难发现满足条件的.

从而读入序列,记录下b的位置为ins.计算1~ins-1位置的前缀和,记录下[-n,n]内前缀和为某个值的前缀和有多少个。

再计算ins~n的前缀和,每计算一个累加上1~ins-1位置的前缀和与此前缀和值相等的个数。

【代码】

#include<cstdio>
#include<cstring>
inline char getc()
{
    static const int L = 20000;
    static char buf[L] , *S = buf , *T = buf;
    if (S == T)
    {
        T = (S = buf) + fread(buf , 1 , L , stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint()
{
    static char c;
    while((c = getc())<32);
    int tmp = c - '0';
    while((c = getc())>=32)
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return tmp;
}
int Add , S1[200002]  , a[100001];
int *low = S1 + 100001;
int main()
{
    int n , m;
    scanf("%d%d" , &n , &m);
    register int i;
    int ins;
    for(i = 1 ; i <= n ; ++i)
    {
        scanf("%d" , &a[i]);
        if (a[i] == m)
            ins = i;
    }
    int add = 0;
    low[0] = 1;
    for(i = 1 ; i < ins ; ++i)
    {
        if (a[i] < m)
            add--;
        else if (a[i] > m)
            add++;
        low[add]++;
    }
    long long ans = 0;
    for(i = ins ; i <= n ; ++i)
    {
        if (a[i] < m)
            add--;
        else if (a[i] > m)
            add++;
        ans += low[add];
    }
    printf("%lld" , ans);
    return 0;
}
comments powered by Disqus