51nod 1682 中位数计数

题目链接戳这里
题意很清晰。输入为A[]，想象一个数组C，以A[i]为基准，若A[j]<A[i]则C[j]为-1，大于为1，等于为0，其中j属于[1,N]。假想有2个数组pre和tail。其中pre[j]是对元素C[j...i]的求和，tail[j]是对元素C[i..j]的求和。
若某一个区间A[s...e]中，排序后A[i]是这个区间的中位数，那么应该有pre[s]+tail[e]=0，其中i属于[s,e]。这个意思可以理解为：若某个数A[i]是区间[s,e]的中位数，那么A[i]的左侧和右侧小于or大于A[i]的数字数量是对称的。

写程序的时候，统计A[i]左侧前缀和，对这些和进行标记，若后缀和中有相同的，说明对称。

#include <bits/stdc++.h>
using namespace std;

const int maxN=8e3+5;
int N, A[maxN], vis[maxN * 2], sum[maxN];

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i)
        scanf("%d", &A[i]);

    for (int i = 1; i <= N; ++i) {
        sum[i] = 0;
        memset(vis, 0, sizeof vis);
        vis[N] = 1;
        for (int j = i - 1; j >= 1; --j) {
            int cmp = A[j] < A[i] ? -1
                : A[j] == A[i] ? 0 : 1;
            sum[j] = sum[j + 1] + cmp;
            ++vis[N + sum[j]];
        }

        int ans = vis[N];
        for (int j = i + 1; j <= N; ++j) {
            int cmp = A[j] < A[i] ? -1
                : A[j] == A[i] ? 0 : 1;
            sum[j] = sum[j - 1] + cmp;
            ans += vis[N - sum[j]];
        }
        printf("%d ", ans);
    }
    return 0;
}