试图了解这个解决方案

Question

我试图解决一个问题，我进入我没能解决一些障碍，在这里出发是问题：Codeforces - 817D

现在我试图蛮力它，使用基本得到我可以生成的数组中的每个段的最小值和最大值，然后跟踪它们我将它们相减并将它们加在一起以获得最终的不平衡，这看起来不错，但它给了我一个超出时间限制的原因暴力强制n *（ n + 1）/ 2数组的子节点给出n是10^6，所以我只是无法绕过它，之后像几个小时没有得到任何新的想法，我决定看到一个解决方案，我什么都不懂在说实话：/，这里是解决方案：

#include <bits/stdc++.h> 
#define ll long long  
int a[1000000], l[1000000], r[1000000]; 
    int main(void) { 
     int i, j, n; 
     scanf("%d",&n); 
     for(i = 0; i < n; i++) scanf("%d",&a[i]); 
     ll ans = 0; 
     for(j = 0; j < 2; j++) { 
      vector<pair<int,int>> v; 
      v.push_back({-1,INF}); 
      for(i = 0; i < n; i++) { 
       while (v.back().second <= a[i]) v.pop_back(); 
       l[i] = v.back().first; 
       v.push_back({i,a[i]}); 
      } 
      v.clear(); 
      v.push_back({n,INF}); 
      for(i = n-1; i >= 0; i--) { 
       while (v.back().second < a[i]) v.pop_back(); 
       r[i] = v.back().first; 
       v.push_back({i,a[i]}); 
      } 
      for(i = 0; i < n; i++) ans += (ll) a[i] * (i-l[i]) * (r[i]-i); 
      for(i = 0; i < n; i++) a[i] *= -1; 
     } 
     cout << ans; 
    } 

我试图追踪它，但我一直想知道为什么是矢量使用，我得到的唯一想法是他想使用向量作为一个堆栈，因为他们都行为相同（几乎），但然后事实，我不甚至不知道为什么我们需要一个堆栈，而这个等式ans += (ll) a[i] * (i-l[i]) * (r[i]-i);真的令我困惑，因为我不知道它从哪里来。

Answer 1

那么这是一个计算的野兽。我必须承认，我也不完全理解它。暴力解决方案的问题是，你必须重新计算值或重新整理。

在稍微修改的例子中，你计算的2, 4, 1输入下列值

[2, *, *] (from index 0 to index 0), imbalance value is 0; i_min = 0, i_max = 0 
[*, 4, *] (from index 1 to index 1), imbalance value is 0; i_min = 1, i_max = 1 
[*, *, 1] (from index 2 to index 2), imbalance value is 0; i_min = 2, i_max = 2 
[2, 4, *] (from index 0 to index 1), imbalance value is 2; i_min = 0, i_max = 1 
[*, 4, 1] (from index 1 to index 2), imbalance value is 3; i_min = 2, i_max = 1 
[2, 4, 1] (from index 0 to index 2), imbalance value is 3; i_min = 2, i_max = 1 

where i_min and i_max are the indices of the element with the minimum and maximum value. 
For a better visual understanding, i wrote the complete array, but hid the unused values with * 

因此，在最后一种情况下[2, 4, 1]，蛮力查找最小值（i加“距离”重新排序它）值，因为您已经通过计算[2,4]和[4,1]来计算问题的子空间的值，所以这不是必需的。但仅比较这些值是不够的，还需要跟踪最小和最大元素的索引，因为在计算[2, 4, 1]时，可以在下一步中重新使用这些索引。

这背后的理念是一个名为dynamic programming的概念，其中来自计算的结果被存储以再次使用。通常，您必须在速度和内存消耗之间进行选择。

所以要回到你的问题，这里是我的理解：

• 阵列l和r用于存储当前的
• 矢量留下的最大数量或右的索引v用于查找大于当前值的最后一个数字（及其索引）（a[i]）。它跟踪上升的号码系列，例如在第一所述5输入5,3,4被存储，则3并且当4到来时，3被弹出，但需要的5的索引（存储在l[2]）
• 再有就是这个花式计算（ans += (ll) a[i] * (i-l[i]) * (r[i]-i)） 。存储的最大值（以及第二次运行中的最小值）索引与价值a[i]一起计算，这对我而言现在没有多大意义，但似乎可行（对不起）。
• 最后，阵列a中的所有值由-1，这意味着，老最大值现在是最低要求，并且计算完成再次相乘（第二外的运行for循环在j）的

最后一步（乘以a,-1）和外部for循环j不是必需的，但它是重用代码的一种优雅方式。

希望这会有所帮助。