题目大意

题意

分析

分析

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int n;
int a[500005],p[500005];
int stk[500005];
int top;
int sum[500005];
int res = 0;

signed main()
{
    cin >>n ;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++) {
        cin >> p[i];
        p[i] = n - p[i] + 1;
    }
    reverse(a+1,a+1+n);
    reverse(p+1,p+1+n);
    // for(int i = 1;i <= n;i++) cout << a[i] <<" \n"[i==n];
    // for(int i = 1;i <= n;i++) cout << p[i] <<" \n"[i==n];

    for(int i = 1;i <= n;i++){
        while(top && a[stk[top]] <= a[i]) top--;
        stk[++top] = i;
        sum[top] = (i-stk[top-1])*a[i] + sum[top-1];
        int pos = lower_bound(stk+1,stk+1+top,p[i]) - stk;
        res += sum[pos-1] + (p[i]-stk[pos-1])*a[stk[pos]];
    }

    cout << res << endl;
    return 0;
}