题目链接：传送门

Description

给你一个N的排列，求

Hint

1<=N<=2e5

Sample Input

3 2 1 3

Sample Output

9

Solution

我的做法好像和网上的不一样。。。 通过找规律观察可以发现每一个数的贡献为这个数的值前面第一个比它小的数到它的距离后面第一个比它小的数到它的距离 然后就是要预处理出它前面/后面第一个比它小的数的位置 这个东西我是直接暴力往前跳的，感性理解好像复杂度有保证，但是还不会证明。。。

Summary

这道B题想了我一个上午，看来还是太弱了 一开始思路很乱，感觉想不出，不过幸好没看题解，不然又错过了一次锻炼思维的机会 虽然花了这么久才做出来，但是至少没看题解，所以还是有收获的

Code

    #include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    const int Maxn = 200000 + 100;
    int N;
    int A[Maxn], Next[Maxn], Pre[Maxn];
    int main()
    {
    #ifdef hk_cnyali
        freopen("B.in", "r", stdin);
        freopen("B.out", "w", stdout);
    #endif
        scanf("%d", &N);
        for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
        for (int i = 2; i <= N; ++i)
        {
            if (A[i - 1] < A[i])
            {
                Pre[i] = i - 1;
                continue;
            }
            else 
            {
                int now = i - 1;
                while (now && A[now] > A[i])
                    now = Pre[now];
                Pre[i] = now;
            }
        }
        Next[N] = N + 1;
        for (int i = N - 1; i >= 1; --i)
        {
            if (A[i + 1] < A[i])
            {
                Next[i] = i + 1;
                continue;
            }
            else 
            {
                int now = i + 1;
                while (now && A[now] > A[i])
                    now = Next[now];
                Next[i] = now;
            }
        }
        LL Ans = 0;
        for (int i = 1; i <= N; ++i)
            Ans += (LL)(1ll * A[i] * (i - Pre[i]) * (Next[i] - i));
        cout<<Ans<<endl;
        return 0;
    }