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
4
题解
因为这道题不关心数据具体为多少，只关心每个数比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;
}