51nod 1349 最大值

题目看这里

找到每个元素g[i]作为最大值的区间[L,R]，那么以他为最大值的区间数有(i-L+1)*(R-i+1)个。

为了加速，以k为最大值的区间数放入H[k]，再以此统计一个前缀和，更新入H。那么>=s的区间个数就是H[1e5]-H[s-1]。

留意：为了避免区间重复，对于同样的元素，左边遇到时继续延伸，用<=号，右边遇到时不再延伸，用<号。

比如{3,3}，防止既以第一个3为基准统计了区间[1,2]，又以第2个3为基准统计了[1,2]。

另，统计区间数时，因为有重复元素，比如以k为最大值的区间数为cnt，那么应该是H[k]+=cnt。而非H[k]=cnt。

#include <stdio.h>

#include <string.h>

#define ll long long

const ll maxN=1e5+;

ll N, M, K, T;

ll g[maxN], h[maxN];

ll L[maxN], R[maxN];

int main() {

#ifndef ONLINE_JUDGE

    freopen("data.in", "r", stdin);

#endif

    scanf("%lld", &N);

    for (ll i = ; i <= N; ++i)

        scanf("%lld", &g[i]);

    scanf("%lld", &K);

    for (ll i = ; i <= N; ++i) {

        L[i] = i - ;

        R[i] = i + ;

    }

    for (ll i = ; i <= N; ++i)

        while (L[i] && g[L[i]] <= g[i])

            L[i] = L[L[i]];

    for (ll i = N; i >= ; --i)

        while (R[i] <= N && g[R[i]] < g[i])

            R[i] = R[R[i]];

    /*

    for (ll i = 1; i <= N; ++i)

        printf("%lld %lld\n", L[i], R[i]);

    puts("");

    */

    memset(h, , sizeof h);

    for (ll i = ; i <= N; ++i)

        h[g[i]] += (i - L[i]) * (R[i] - i);

    for (ll i = ; i < maxN; ++i)

        h[i] += h[i - ];

    for (ll i = , s; i < K; ++i) {

        scanf("%lld", &s);

        printf("%lld\n", h[maxN - ] - h[s - ]);

    }

    return ;

}