#include<iostream> #include<cstring> using namespace std; //题目要求:给出1~n的一个排列, //统计该排列有多少个长度为奇数的连续子序列的中位数是b。 //思路:把b记为0,比b大的元素记为1,比b小的元素记为-1, //一个连续区间内必须包含b,-1与1的个数必须相同 //一个数组,用位置表示b左侧元素的后缀和,值表示各数值个数 //1 4 2 5 3 7 6 int main(){ int n, b; cin >> n >> b; int num[n]; int pos; //记录b的位置 //把b记为0,比b大的元素记为1,比b小的元素记为-1 for(int i = 1; i <= n; i++){ cin >> num[i]; if(num[i] == b){ num[i] = 0; pos = i; } else if(num[i] > b){ num[i] = 1; } else{ num[i] = -1; } } int left_delta = 0; //记录b左侧的后缀和 int right_delta = 0; //记录b右侧的前缀和 int left[2*n+1]; //维护后缀和各值的个数 memset(left, 0, sizeof(left));//初始化记录后缀和值个数的数组,起初个数均为0 for(int i = pos-1; i >= 1; i--){ left_delta += num[i]; left[left_delta + n] ++; //因为存在负数,所以将数组平移(用每个数+n的位置表示该数的值),平移后再记录 } int cnt = 1; // 记录总个数,初始值为1 (考虑b本身为一种序列) int cnt0 = 0; //记录b右侧前缀和值为0的个数 for(int i = pos+1; i <= n; i++){ right_delta += num[i]; cnt += left[-right_delta + n]; //left[]数组中记录的与右侧非0前缀和互为相反数的数的个数即为该位置数可以组合的个数 if(right_delta == 0){ cnt0++; } } cnt += cnt0 + left[n]; //对于前缀和与后缀和为0的情况 cout << cnt << endl; }