「LuoguP1627 / T36198」 [CQOI2009]中位数

Description

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

Input

第一行为两个正整数n和b，第二行为1~n的排列。

【数据规模】

对于30%的数据中，满足n≤100；

对于60%的数据中，满足n≤1000；

对于100%的数据中，满足n≤100000,1≤b≤n。

Output

输出一个整数，即中位数为b的连续子序列个数。

Sample Input

7 4
5 7 2 4 3 1 6

Sample Output

题解

因为这道题不关心数据具体为多少，只关心每个数比b大或小，
所以首先在读入的时候就忽视数据绝对大小，只存相对b的大小
（小于b存-1 等于b存0 大于b存1

O(n^2)：
枚举区间长度L和左端点i 利用前缀和可以O(1)得到区间和易知区间和为0的话在这个区间内b为中位数
（证明：因为区间和为0 所以在这个区间内的-1数量和1的数量相等也就是比b小的和比b大的数一样多）

期望60，却因为数据巨水搞到90(喵喵喵？)

~~本来打算卡一波常A掉然后发n方题解哈哈哈哈~~

90分代码：

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

inline int read()

{

    char ch=getchar();

    int x=0;bool s=1;

    while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}

    return s?x:-x;

}

int a[100007];

int s[100007];

int main()

{

    //scan

    int n,mid,p;

    n=read(),mid=read();

    unsigned long long ans=0;

    for(int i=1;i<=n;++i)

    {

        int x=read();

        if(x<mid)a[i]=-1;

        else if(x>mid)a[i]=1;

        else p=i;

    }

    for(int i=1;i<=n;++i)

    s[i]=s[i-1]+a[i];

    //run

    for(int l=1;l<=n;l+=2)

    {

    int k=min(p,n-l+1);

    for(int i=max(1,p-l+1);i<=k;++i)

    {

        int j=i+l-1;

        if(s[j]-s[i-1]==0)ans++;

    }

    }

    cout<<ans<<endl;

    return 0;

}

AC做法：（先懵着脑袋看后有讲解）

读入的同时记录b出现的坐标为p。从p-1到1扫一遍，从p+1到n扫一遍，用类计数排序的方式记录 ↓

int s=0;

for(int i=p-1;i;--i){

    s+=a[i];

    L[s+c]++;//c=100001 避免负坐标

}

s=0;

for(int i=p+1;i<=n;++i){

    s+=a[i];

    R[s+c]++;

}

L[ s + c ]表所有左端点为1到p-1，右端点为p-1的区间中，区间和为s的情况数
同理R[ s + c ]表所有左端点为p+1，右端点为p+1到n的区间中，区间和为s的情况数

而对于一个区间< l , r >，如果< l , p-1 >的区间和 + < p+1 , r >的区间和==0的话，就是一个符合条件的区间。
所以根据乘法原理，L[ s + c ] × R[ ( - s ) + c ] == p左边的区间和为s时的所有可能情况（此时右边区间和为-s）所以

ans+=L[ s + c ] × R[ ( - s ) + c ] ( s = - n to n ) ;

最后因为以上只计算了 l < p 且 r > p 的区间，所以还要

ans+=L[ 0 + c ]  (l<p r==p) +R[0+c] (l==p r>p) +1(l==p r==p);

AC代码：

#include<iostream>

#include<cstdio>

using namespace std;

#define R register

inline int read()

{

    char ch=getchar();

    int x=0;bool s=1;

    while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}

    return s?x:-x;

}

int a[100007],l[200007],r[200007];

int main()

{

    //scan

    int n=read(),b=read(),p;

    for(R int i=1;i<=n;++i)

    {

        int x=read();

        if(x<b)a[i]=-1;

        else if(x>b)a[i]=1;

        else p=i;

    }

    //predo

    int s=0,c=100001;

    for(R int i=p-1;i;--i)

    {

        s+=a[i];

        l[s+c]++;

    }

    s=0;

    for(R int i=p+1;i<=n;++i)

    {

        s+=a[i];

        r[s+c]++;

    }

    //run

    int ans=0;

    for(R int i=-n;i<=n;++i)

    {

        ans+=l[i+c]*r[-i+c];

    }

    ans+=l[0+c]+r[0+c]+1;

    cout<<ans<<endl;

    return 0;

}

巴特西