原题链接 思路分析： 根据中位数的性质，我们可以知道在一定的区间范围内，所有大于它与小于它的数的个数是相等的。 所以如果一个区间满足大于中位数与小于中位数的个数相等，且中位数在其中，则是符合题意的区间。（设大于中位数个数与小于中位数个数均为 n n n ，加上中位数自己本身，总长度为 2 ∗ n + 1 2*n+1 2∗n+1,长度必定为奇数，无需特判。） 在读入的时候，将大于中位数的数据赋值 1 1 1，小于中位数的数据赋值 − 1 -1 −1 ，等于中位数的数据赋值 0 0 0 ，并记录中位数的下标，左右遍历统计即可。 左遍历的时候如果区间和为 0 0 0 ，区间存在则 a n s + + ans++ ans++，并利用 M a p Map Map 统计 s u m s sums sums 的情况，如果右边有区间和为 − s u m s -sums −sums，则可以与左边的 s u m s sums sums 配对。 中位数本身就是符合条件的区间，所以有 M a p [ 0 ] + + Map[0]++ Map[0]++ 。 C o d e : Code: Code:
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define MaxN 100010 #define LL long long LL A[MaxN]; map <int,int> Map; signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n,x,pos; cin >> n >> x; for(int i=1; i<=n; i++){ cin >> A[i]; if( A[i] < x ) A[i]=-1; else if( A[i] > x ) A[i]=1; else A[i]=0, pos=i; } Map[0]++; int sums=0,ans=0; for(int i=pos-1; i>=1; i--){ sums+=A[i]; if( sums == 0 ) ans++; Map[sums]++; } sums=0; for(int i=pos+1; i<=n; i++){ sums+=A[i]; ans+=Map[-sums]; } cout << ans+1; return 0; }