Description
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
第一行为两个正整数n和b ，第二行为1~n 的排列。
Output
输出一个整数，即中位数为b的连续子序列个数。
7 4 5 7 2 4 3 1 6
Sample Output
4
HINT
第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6} N<=100000
题解
这道题蛮好玩的，有点烧脑。
对于小于b的数，将其设置为-1； 对于大于b的数，将其设置为1； 用类似于求前缀和的方法，只要某一段区间和为0，则该段即符合条件（自己思考）
但是这题的范围是100000 所以我们需要做一点处理，就是将b前后两段分别处理，统计区间和为x的个数，ans=sigma(l[x] * r[x]) 具体细节看代码
代码
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define N 100010int a[N],sl[N * 2],sr[N * 2];int n,b,pos;int main(){ scanf("%d%d",&n,&b); for(int i = 1;i <= n;i++) { scanf("%d",&a[i]); if(a[i] == b) pos = i; } memset(sl,0,sizeof(sl)); memset(sr,0,sizeof(sr)); int sum = 0; sl[N] = sr[N] = 1; for(int i = pos - 1;i >= 1;i--) sum += a[i] < b ? 1 : -1,sl[sum + N] ++; sum = 0; for(int i = pos + 1;i <= n;i++) sum += a[i] > b ? 1 : -1,sr[sum + N] ++; int ans = 0; for(int i = N - n;i <= N + n;i++) ans += sl[i] * sr[i]; PRintf("%lld",ans); return 0;}
