题解 原P4171 【[CQOI2009]中位数图】

标记一遍相对大小，大的标1，小的标-1。只要连续n项和为0，就能满足题目条件。 ```cpp #include<cstdio> #include<cctype> using namespace std; int array[100005],left[200005],right[200005]; inline int read() { int x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); } return x; } int main() { int n,b,mid,ans=1; //最开始的1是自己 n=read();b=read(); for(int i=0;i<n;i++) { array[i]=read(); if(array[i]==b) mid=i; }//找到中位数 //计数排序 //处理左半边 int sum=0; for(int i=mid-1;i>=0;i--) { sum+=array[i]>array[mid]?1:-1; left[100000+sum]++; } //处理右半边 sum=0; for(int i=mid+1;i<n;i++) { sum+=array[i]>array[mid]?-1:1; right[100000+sum]++; } for(int i=100000-n;i<=100000+n;i++) ans+=left[i]*right[i]; //乘法原理 ans+=left[100000];ans+=right[100000]; //自身与两边组合 printf("%d",ans); return 0; } ```