题目大意

给定一个排列和 ， 在该排列中。求该排列的长为奇数且以 为中位数的子段个数。

题解

考虑将排列映射成另一个序列，某一位置上的数为 那么映射后这一位置上的数变为 。那么必然映射后的序列会有一个 。

问题转化为求新生成的序列中，包含这个 在内且子段和为 的子段个数。这个可以用前缀和比较简单的做到。

#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
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; 
}
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
inline int sgn(int x){
    return (x < 0 ? -1: (x > 0 ? 1: 0));
}
template<typename T>
T gcd(T a, T b){
    return (!b) ? a: gcd(b, a % b);
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

/*--------------------------------------------------------------------*/
/*--------------------------------------------------------------------*/

int cnt[200005] = {0}, n, b;
int main(){
    n = read(), b = read();
    int sum = 0, offset = n;
    cnt[offset] = 1;
    while (n--){
        int t = read();
        sum += sgn(t - b);
        if (t == b) break;
        ++cnt[offset + sum];
    }
    ll ans = cnt[sum + offset];
    while (n--){
        int t = read();
        sum += sgn(t - b);
        ans += cnt[sum + offset];
    }
    printf("%lld\n", ans);
    return 0;
}