[bzoj1303]中位数图

由于是排列，因此b一定只出现了一次，找到出现的位置并向左右扩展
考虑如何判定是否满足条件，当且仅当$[左边比b小的数ls]+[右边比b小的数rs]=[左边比b大的数lb]+[右边比b大的数rb]$，暴力枚举+线段树复杂度为$o(n^2logn)$
变形上式，得到$ls-lb=rb-rs$，对两边分别处理后对应方案相乘求和即为答案

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],s1[200005],s2[200005];
long long ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        if (a[i]==m){
            int t=n;
            s1[n]=s2[n]=1;
            for(int j=i-1;j;j--)s1[t+=2*(a[j]<m)-1]++;
            t=n;
            for(int j=i+1;j<=n;j++)s2[t+=2*(a[j]>m)-1]++;
            for(int j=1;j<=2*n;j++)ans+=1LL*s1[j]*s2[j];
            printf("%lld",ans);
            return 0;
        }
}