题解

Problem: A1623

Tag：单调栈

给定一个数组，求所有子数组极差之和。

枚举右端点，处理出对应所有左端点的最大值之和与最小值之和。这个可以单调栈维护。

namespace cjdst{
    void solve(){
		int n;
		std::cin >> n;
		std::vector <ll> a(n + 5);
		std::vector <ll> stack1, stack2;
		ll cur1 = 0, cur2 = 0, ans = 0;
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
			while(!stack1.empty() && a[stack1.back()] <= a[i]){
				cur1 -= (stack1.back() - (stack1.size() <= 1 ? 0 : stack1[stack1.size() - 2])) * a[stack1.back()];
				stack1.pop_back();
			}
			while(!stack2.empty() && a[stack2.back()] >= a[i]){
				cur2 -= (stack2.back() - (stack2.size() <= 1 ? 0 : stack2[stack2.size() - 2])) * a[stack2.back()];
				stack2.pop_back();
			}
			cur1 += (i - (stack1.empty() ? 0 : stack1.back())) * a[i];
			cur2 += (i - (stack2.empty() ? 0 : stack2.back())) * a[i];
			stack1.push_back(i), stack2.push_back(i);
			ans += (cur1 - cur2);
		}
		std::cout << ans << '\n';
	}
}

时间复杂度：$O(n)$。

当然，也可以建笛卡尔树：

namespace cjdst{
	void solve(){
		int n;
		std::cin >> n;
		std::vector <int> a(n + 5);
		std::vector <int> stack1, stack2;
		std::vector <int> lson1(n + 5), rson1(n + 5), lson2(n + 5), rson2(n + 5);
		std::vector <ll> siz1(n + 5), siz2(n + 5);
		int root1 = -1, root2 = -1;
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
			int lst1 = -1, lst2 = -1;
			while(!stack1.empty() && a[stack1.back()] <= a[i]){
				lst1 = stack1.back();
				stack1.pop_back();
			}
			if(lst1 != -1) lson1[i] = lst1;
			if(stack1.empty()) root1 = i;
			else rson1[stack1.back()] = i;
			
			while(!stack2.empty() && a[stack2.back()] >= a[i]){
				lst2 = stack2.back();
				stack2.pop_back();
			}
			if(lst2 != -1) lson2[i] = lst2;
			if(stack2.empty()) root2 = i;
			else rson2[stack2.back()] = i;
			
			stack1.push_back(i), stack2.push_back(i);
		}
		ll ans = 0;
		auto dfs1 = [&](auto &&self, int cur) -> void{
			if(lson1[cur]) self(self, lson1[cur]);
			if(rson1[cur]) self(self, rson1[cur]);
			siz1[cur] = siz1[lson1[cur]] + siz1[rson1[cur]] + 1;
			ans += (siz1[lson1[cur]] + 1) * (siz1[rson1[cur]] + 1) * a[cur];
		};
		auto dfs2 = [&](auto &&self, int cur) -> void{
			if(lson2[cur]) self(self, lson2[cur]);
			if(rson2[cur]) self(self, rson2[cur]);
			siz2[cur] = siz2[lson2[cur]] + siz2[rson2[cur]] + 1;
			ans -= (siz2[lson2[cur]] + 1) * (siz2[rson2[cur]] + 1) * a[cur];
		};
		dfs1(dfs1, root1);
		dfs2(dfs2, root2);
		std::cout << ans << '\n';
	}
}

时间复杂度：$O(n)$。