第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000
题解：思维题，转化成0， 1， -1，从b的位置往两边算一个前缀和，并记录两边的cnt，可能有负数，+n即可。
#include <bits/stdc++.h> const int maxn=1e5+5; int a[maxn], lc[2*maxn], rc[2*maxn]; int main() { int n, b; scanf("%d%d", &n, &b); int pos, data; for(int i=1; i<=n; i++) { scanf("%d", &data); if(data==b) { pos=i; a[i]=0; } else a[i]= data>b? 1:-1; } int lsum=0, rsum=0; for(int i=pos+1; i<=n; i++) { rsum+=a[i]; rc[n+rsum]++; } for(int i=pos-1; i; i--) { lsum+=a[i]; lc[n+lsum]++; } long long ans=0; for(int i=-n; i<=n; i++) { if(i!=0) ans+=1ll*lc[-i+n]*rc[i+n]; else ans+=lc[-i+n]+rc[i+n]+1ll*lc[-i+n]*rc[i+n]; } printf("%lld\n", ans+1); return 0; }
原文：https://www.cnblogs.com/Yokel062/p/11476946.html
