11377: 【原1377】序列

题目

题目描述

author: yuan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1377 

题目描述

有一个长度为N的数列{A1,A2,...,AN}，这N个数字恰好是1...N的一个排列。你需要求出这个序列有多少个子序列{Ai,Ai+1,...,Aj}满足：i<=j且j-i+1为奇数，这个序列的中位数为B。例如{5,1,3}的中位数为3。

输入说明

输入文件第一行包含两个正整数N和B，满足1<=N<=100000且1<=B<=N。

第二行包含N个整数Ai。

输出说明

输出文件仅包含一个整数，为满足条件的子序列个数。

样例输入

7 4
5 7 2 4 3 1 6

样例输出

4

数据范围

对于30%的数据，1<=n<=100;

对于70%的数据，1<=n<=10000;

对于100%的数据，1<=n<=100000；

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e5 + 100;

int N, B, A[maxN], a[maxN], pos, l[2 * maxN] = {0}, r[2 * maxN] = {0},
                                       left1 = 0, right1 = 0;

int main() {
    int sum=0;

    cin >> N >> B;

    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        if (A[i] > B) {
            a[i] = 1;
        } else if (A[i] == B) {
            a[i] = 0;
            pos = i;
        } else {
            a[i] = -1;
        }
    }

    left1 = right1 = N;

    for (int i = pos; i > 0; i--) {
        left1 += a[i];
        l[left1]++;
    }

    for (int i = pos; i <= N; i++) {
        right1 += a[i];
        r[right1]++;
    }

    for (int i = 1; i <= 2 * N; i++) {
        sum += (l[i] * r[2 * N - i]);
    }

    cout << sum;

    return 0;
}

yyong119's solution

#include <cstdio>
#include <iostream>
#define MAX_N 100010
#define OFFSET 100010
using namespace std;
int n, B, B_pos;
int a[MAX_N];
int left_sum[MAX_N + OFFSET], right_sum[MAX_N + OFFSET];
inline int read() {
    char ch = getchar(); int res = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res;
}
int main() {
    n = read(), B = read();
    for (register int i = 0; i < n; ++i) {
        int tmp = read();
        if (tmp < B) a[i] = -1;
        else if (tmp > B) a[i] = 1;
        else B_pos = i;
    }
    int cur_sum = 0;
    for (register int i = B_pos - 1; i >= 0; --i) {
        cur_sum += a[i];
        ++left_sum[OFFSET + cur_sum];
    }
    cur_sum = 0;
    for (register int i = B_pos + 1; i < n; ++i) {
        cur_sum += a[i];
        ++right_sum[OFFSET - cur_sum];
    }
    long long ans = 1;
    for (register int i = 0; i < MAX_N + OFFSET; ++i)
        ans += left_sum[i] * right_sum[i];
    printf("%lld", ans + left_sum[OFFSET] + right_sum[OFFSET]);
    return 0;
}