[51nod - 1215] 数组的宽度

题意：

给定长度为 N≤50000$N\le 50000$ 的数组 A$A$，记任一子串为 Al…r$A_{l\dots r}$。求 ∑l=1N∑r=lN(max{Al…r}−min{Al…r})${\displaystyle \sum _{l=1}^N\sum _{r=l}^N(max\{A_{l\dots r}\}-min\{A_{l\dots r}\})}$。

分析：

将式子拆成两部分：

∑l=1N∑r=lNmax{Al…r}−∑l=1N∑r=lNmin{Al…r}$${\displaystyle \sum _{l=1}^N\sum _{r=l}^{N}max\{A_{l\dots r}\}-\sum _{l=1}^N\sum _{r=l}^{N}min\{A_{l\dots r}\}}$$

枚举 Ai$A_i$，算其可以作为多大的区间的最大值和最小值。例如其作为最大值可以支配 [li,ri]$[l_i,r_i]$ 的区间，那么对左和式的贡献就是 (i−li+1)×(ri−i+1)$(i-l_i+1)\times (r_i-i+1)$。对于每一个都算一下支配的区间，就可以得出答案。

算支配的区间等价于求左右边两边第一个大于（小于）它的数所在的位置，往里靠一步的位置上就是可以支配的最大区间。用单调栈维护。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 5e4 + 10;
int N;
int arr[N_MAX], stk[N_MAX], top;
int l[N_MAX], r[N_MAX];
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d", arr + i);
  }

  for (int i = 1; i <= N; i++) {
    while (top && arr[stk[top]] > arr[i]) {
      r[stk[top--]] = i;
    }
    l[i] = stk[top];
    stk[++top] = i;
  }
  while (top) {
    r[stk[top--]] = N + 1;
  }
  long long acc1 = 0;
  for (int i = 1; i <= N; i++) {
    acc1 += 1LL * arr[i] * (r[i] - i) * (i - l[i]);
  }

  memset(l, 0, sizeof(l));
  memset(r, 0 , sizeof(r));
  for (int i = 1; i <= N; i++) {
    while (top && arr[stk[top]] <= arr[i]) {
      r[stk[top--]] = i;
    }
    l[i] = stk[top];
    stk[++top] = i;
  }
  while (top) {
    r[stk[top--]] = N + 1;
  }
//  for (int i = 1; i <= N; i++) printf("%d %d\n", l[i], r[i]);
  long long acc2 = 0;
  for (int i = 1; i <= N; i++) {
    acc2 += 1LL * arr[i] * (r[i] - i) * (i - l[i]);
  }
  printf("%lld\n", abs(acc2 - acc1));

}