CF2137F Prefix Maximum Invariance
题意：
给定数组a和b，要求构造一个新数组z，对于所有 \(1 \leq i\leq n\) 满足 \(max(a_1,...,a_i) = max(z_1,...,z_i)\)，即前缀最大值完全相同。定义 \(f(a,b)\) 表示在满足上述条件的z中，能使 \(z_i=b_i\) 的最大数量。求 \(\sum_{l=1}^n \sum_{r=l}^n f\left( a[l..r], b[l..r] \right)\) 的结果。
对于所有子区间求和的题目，首先想到枚举左端点或右端点，但这种思路在本题行不通。于是想到对每个位置计算贡献。
对于一个位置 \(i\)，假设左端点 \(l\) 已经固定的情况下，\(z_i\) 的取值有两种情况：
1、\(max[a_l,...,a_{i-1}] < a_i\)，那么 \(a_i\) 一定是这个区间的新的前缀最大值，\(z_i\) 必须等于 \(a_i\)。
2、\(max[a_l,...,a_{i-1}] >= a_i\)，那么 \(a_i\) 不会是新的前缀最大值，\(z_i \leq max[a_l,...,a_i]\) 即可。
考虑有多少个区间 \([l,r]\) 能使 \(z_i=b_i\)。显然右端点的数量是 \(n-i+1\) 个，所以只需要考虑有多少个左端点 \(l\)。
当从左到右枚举 \(i\) 时，假设对于每个 \(1 \leq j \leq i\)，都维护好了数组 \(mx_j\)，表示 \([j,i-1]\) 的最大值。
对于情况1，只需要找到有几个 \(mx_j\)，使得 \(mx_j < a_i\)。
对于情况2，只需要找到有几个 \(mx_j\)，使得 \(mx_j \geq b_i\)。
暴力维护 \(mx\) 和查询是 \(n^2\) 的，但是注意到 \(mx\) 具有单调性。这就意味着，每次更新 \(mx\) 时，需要修改的元素是连续的。所以可以通过单调栈来维护。
情况2的查询只需要在这个单调栈中二分即可。
Code:
#include <iostream>
#include <vector>
#include <stack>
using namespace std;using ll = long long;struct node
{int mx,l;
};void solve()
{int n;cin >> n;vector<int> a(n+10),b(n+10);for (int i = 1 ; i <= n ; i++) cin >> a[i];for (int i = 1 ; i <= n ; i++) cin >> b[i];//枚举左右端点做不了，考虑拆位算贡献ll ans = 0;vector<int> stk; //vector实现栈方便二分for (int i = 1 ; i <= n ; i++){while (!stk.empty() && a[stk.back()] < a[i]) stk.pop_back();if (a[i] == b[i]) //第1种情况{if (!stk.empty()) ans += (ll)(i-stk.back()) * (n-i+1);else ans += (ll)i * (n-i+1);}int l = -1;int r = stk.size();while (l+1 != r){int mid = (l+r) >> 1;if (a[stk[mid]] >= b[i]) l = mid;else r = mid;}if (l != -1) ans += (ll)stk[l] * (n-i+1); //第二种情况stk.push_back(i);}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--) solve();return 0;
}