hdu4908:http://acm.hdu.edu.cn/showproblem.php?pid=4908
题意：：给定一个序列，1-n的数字，选定一个作为中位数m，要求有多少连续子序列满足中位数是m
题解;自己不会做，然后别人给了一个O(n)的算法，瞬间吓cry。这个算法不好解释，还是看看代码，然后自己画个图就出来了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 long long last; 7 long long ans[100003]; 8 long long a[40005]; 9 int m,n,cnt,ct,pos; 10 int main(){ 11 while(~scanf("%d%d",&n,&m)){ 12 memset(ans,0,sizeof(ans)); 13 memset(a,0,sizeof(a)); 14 last=0;cnt=ct=50000; 15 for(int i=1;i<=n;i++){ 16 scanf("%I64d",&a[i]); 17 if(a[i]==m) 18 pos=i; 19 } 20 ans[cnt]++; 21 for(int i=pos+1;i<=n;i++){ 22 if(a[i]<m)ans[--cnt]++; 23 else ans[++cnt]++; 24 } 25 last+=ans[ct]; 26 for(int i=pos-1;i>=1;i--){ 27 if(a[i]<m){ 28 last+=ans[++ct]; 29 } 30 else{ 31 last+=ans[--ct]; 32 } 33 } 34 printf("%I64d ",last); 35 } 36 }