526互联

CodeForces 1827 B Range Sorting

发布时间 2023-05-16 18:43:35作者: zltzlt

洛谷传送门

CF 传送门

考虑拆贡献 \(i - 1 \sim i\)，发现当 \([1, i - 1]\) 的最大值大于 \([i, n]\) 的最小值时 \(i - 1 \sim i\) 产生 \(1\) 的贡献。

考虑枚举左端点 \(j\)，设 \(x = \max\limits_{k=j}^{i-1} a_k\)。设 \(i\) 及 \(i\) 以后第一个 \(< x\) 的数位置是 \(p\)，那么右端点 \(\in [p, n]\)，贡献系数为 \(n - p + 1\)。

这个容易用单调栈优化至 \(O(n \log n)\)，当弹栈时计算贡献即可。

code 
// Problem: B2. Range Sorting (Hard Version)
// Contest: Codeforces - Codeforces Round 873 (Div. 1)
// URL: https://codeforces.com/contest/1827/problem/B2
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 300100;
const int logn = 22;

ll n, a[maxn], stk[maxn], top, lg[maxn], f[maxn][logn];

inline ll qmin(int l, int r) {
	int k = lg[r - l + 1];
	return min(f[l][k], f[r - (1 << k) + 1][k]);
}

inline int ask(int i, int x) {
	int l = i + 1, r = n, p = n + 1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (qmin(i + 1, mid) < x) {
			p = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return p;
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		f[i][0] = a[i];
	}
	for (int j = 1; (1 << j) <= n; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
			f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
		}
	}
	for (int i = 2; i <= n; ++i) {
		lg[i] = lg[i >> 1] + 1;
	}
	ll ans = 0;
	top = 0;
	for (int i = 1; i <= n; ++i) {
		while (top && a[stk[top]] < a[i]) {
			ans += (stk[top] - stk[top - 1]) * (n - ask(i, a[stk[top]]) + 1);
			--top;
		}
		ans += stk[top] * (n - i + 1);
		stk[++top] = i;
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}