「Bzoj 1303」「CQOI2009」中位数图 (前缀和+乘法原理)

BZOJ 1303
因为题目是$1-n$排列，所以$b$只会出现一次，那么我们记录$b$的位置$p$，然后我们不难发现当$b$旁边连续的几个数中大于$b$和小于$b$的数的个数相同就会对答案作出贡献。我们记录左边大于$b$的数为$1$，小于$b$的数为$-1$，也就是差分序列(括号序列)，然后从$p-1$到$1$求前缀和，记录在$sum$中，然后$l$数组就是记录某个前缀和出现的次数。右边同理，但是大于$b$的数为$-1$，小于$b$的数为$1$。然后根据乘法原理，左边有$l_i$个可匹配，右边有$r_i$个可匹配，答案就是$\sum_{i=-n}^n l_ir_i$，负数要处理一下，加一个常数，但是注意数组的大小就要乘以二了.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5, N = 100000;
int n, b, p, a[MAXN], l[MAXN*2], r[MAXN*2]; 
void clean() {}
void solve() {
    clean();
    for (int i=1;i<=n;i++) {
        scanf("%d", &a[i]);
        if (a[i] == b) p = i; 
    }
    int sum = 0;
    l[N] = r[N] = 1;
    for (int i=p-1;i>0;i--) 
        sum += (a[i] > b) ? 1 : -1, l[sum + N]++;
    sum = 0;
    for (int i=p+1;i<=n;i++) 
        sum += (a[i] < b) ? 1 : -1, r[sum + N]++;
    int ans = 0;
    for (int i=N-n;i<=N+n;i++) ans += l[i] * r[i];
    printf("%d\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%d%d", &n, &b), solve();
    return 0;
}