题解
设$b$所在位置是$k$，那么对于$k$及$b$左边的所有位置求一个$d[i]$，表示$i$到$k-1$有几个小于$b$的数。那么对于$k$及其右边的位置$j$我们定义$d[j]$为$k+1$到$j$有几个小于$b$的数，这样对于一个$j$我们想要找到所有的$i$，使得
整理为
用map实现。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
map<int, int> mp;
int n, a[100005], b, k, ans = 0;
void init(){
n = read(), b = read();
for(int i = 1; i <= n; ++i){
a[i] = read();
if(a[i] == b) k = i;
}
}
void solve(){
int cnt = 0;
for(int i = k; i >= 1; --i){
if(a[i] < b) cnt++;
mp[0 - i - 2 * cnt]++;
}
cnt = 0;
for(int i = k; i <= n; ++i){
if(a[i] < b) cnt++;
ans += mp[2 * cnt - i];
}
printf("%d\n", ans);
}
int main(){
init();
solve();
return 0;
}