www.vijos.cn/Problem_Show.asp
也是[CQOI2009]中位数图
额。。设b所在位置为x，
设一个数列S中大于b的数的数量-小于b的数的数量F(S)
那么这个序列由x左边的一些和右边的一些构成，且F(Left)+F(Right)=0。。
那么就很简单了。。从x往右扫描一遍，记录每个F(S)出现了几次，放在Count数组里
再往左扫描一遍，若当前F值为now,只要把答案+上Count[-now]就可以了
0ms1A。。真是爽啊。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
const int maxn=1e5+10;
int main()
{
//freopen("in","r",stdin);
int n,b;int A[maxn];
int C[maxn*2]={0};
cin>>n>>b;int x;
rep(i,n) scanf("%d",A+i),x=(A[i]==b?i:x);
int now=0;
C[now+maxn]++;
for(int i=x+1;i<n;i++)
{
if(A[i]>b) now++;
else now–;
C[now+maxn]++;
}
long long ans=0;
now=0;ans+=C[now+maxn];
for(int i=x-1;i>=0;–i)
{
if(A[i]>b) now++;
else now–;
ans+=C[maxn-now];
}
cout<<ans<<endl;
}
P.S最近在做以前浙江省数学竞赛的卷子，突然灵机一动想出了一道编程题，就交到Vijos上面去了。。不知道能不能通过囧。。