[CQOI2009]中位数图(前缀和)

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int a[N];
map<int,int> mp;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,b,pos,ans = 1,sum = 0;
    cin>>n>>b;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>b) a[i] = 1;
        else if(a[i]<b) a[i] = -1;
        else a[i] = 0, pos = i;
    }
    for(int i=pos - 1;i>=1;i--){
        sum += a[i];
        mp[sum]++;
        if(!sum) ans ++;
    }
    sum = 0;
    for(int i=pos+1;i<=n;i++){
        sum += a[i];
        if(!sum) ans ++;
        if(mp[-sum]) ans += mp[-sum];
    }
    cout<<ans<<'\n';
    return 0;
}