[CQOI2009]中位数图

是个还行的思维题.跟我昨天出的题差不多.
样例解释:
4
724
57243
5724316
思路找下这个值所在的位子,记录为0,把小于它的计为-1,把大于它的计为1.
然后就是用个map记录,把当前记录为0,因为必须要经过这个点,所以map只能记录前面的数.然后中间的那个数不是太好处理,单独拿出来处理一下.
代码:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
map<int,int>mp;
int a[N];
int b[N];
int main()
{
    int n,t,val,pos,ans=0,sum=0;
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==t) {b[i]=0;val=a[i];pos=i;}
    }
    mp[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>val) b[i]=1;
        if(a[i]<val) b[i]=-1;
        sum+=b[i];
        if(i<pos) mp[sum]++;
        if(i>pos&&mp[sum])  ans+=mp[sum];
    }//处理中位数后的数
    sum=0;
    for(int i=pos;i;i--)
    {
        sum+=b[i];
        if(!sum) ans++;
    }
    cout<<ans<<endl;
    return 0;
}