[CQOI2009]中位数图 这是一道OI真题，我们来看看题目：
顺便放下地址吧：[CQOI2009]中位数图
读了题目之后发现直接枚举是不行的，会超时，那么我们就得换种思路了，我们可以把大于目标数的数设置为1，小于目标数（题目中的b,下同）的设置为-1，然后只要包含目标数的区间的和为1则符合要求，然后应用前缀和的思想便可以快速解决！
我们来看看成功AC的代码吧：
#include<bits/stdc++.h> using namespace std; int n,b; int a[100010],cnt[2*100010]; int ans; int main(){ cin.tie(0); ios::sync_with_stdio(false); cin>>n>>b; int pos=0;//标记目标数的位置 for(int i=1;i<=n;i++){ int x; cin>>x; if(x==b) a[i]=0,pos=i; if(x<b) a[i]=-1; if(x>b) a[i]=1; } int s=0;//s用来装前缀/后缀和 for(int i=pos-1;i>=1;i--){ s+=a[i]; cnt[s+n]++; if(!s) ans++;//后缀和为0的，符合要就 ，ans++ } s=0; for(int i=pos+1;i<=n;i++){ s+=a[i]; ans+=cnt[n-s];//与左边的进行匹配 if(!s) ans++;//前缀和为0的，符合要就 ，ans++ } cout<<ans+1; return 0; }
