sulaimu

【模板】单调栈

给定数列$\lbrace a_{n} \rbrace$，求$f(i)=\min\limits_{i<j \leqslant n, a_j > a_i} \{j\}$。$(n \leqslant 3\times 10^6)$

void eachT() {
	int n = read();
	std::vector<int> a(n), ans(n);
	for (auto& i : a) i = read();

	std::stack<int> Q;
	for (int i = 0; i < n; ++i) {
		while (!Q.empty() && a[i] > a[Q.top()])
			ans[Q.top()] = i, Q.pop();
		Q.push(i);
	}

	for (auto& i : ans) printf("%d ", i + 1);
}

两个

某地有 𝑁N 个能量发射站排成一行，每个发射站 𝑖i 都有不相同的高度 𝐻𝑖Hi​，并能向两边（两端的发射站只能向一边）同时发射能量值为 𝑉𝑖Vi​ 的能量，发出的能量只被两边最近的且比它高的发射站接收。显然，每个发射站发来的能量有可能被 00 或 11 或 22 个其他发射站所接受。

请计算出接收最多能量的发射站接收的能量是多少。

void eachT() {
	int n = read();
	std::vector<std::pair<int, int> > a(n);
	std::vector<ll> ans(n);
	for (auto& [f, s] : a) f = read(), s = read();

	{
		std::stack<int> Q;
		for (int i = 0; i < n; ++i) {
			while (!Q.empty() && a[i].first > a[Q.top()].first)
				ans[i] += a[Q.top()].second, Q.pop();
			Q.push(i);
		}
	}

	{
		std::stack<int> Q;
		for (int i = n - 1; i >= 0; --i) {
			while (!Q.empty() && a[i].first > a[Q.top()].first)
				ans[i] += a[Q.top()].second, Q.pop();
			Q.push(i);
		}
	}

	ll mx = 0;
	for (auto& i : ans) mx = max(mx, i);
	printf("%lld", mx);
}

一个

void eachT() {
	int n = read();
	std::vector<std::pair<int, int> > a(n);
	std::vector<ll> ans(n);
	for (auto& [f, Q] : a) f = read(), Q = read();

	std::stack<int> Q;
	for (int i = 0; i < n; ++i) {
		while (!Q.empty() && a[Q.top()].first < a[i].first) {
			ans[i] += a[Q.top()].second;
			Q.pop();
		}
		if (!Q.empty()) ans[Q.top()] += a[i].second;
		Q.push(i);
	}

	ll mx = 0;
	for (auto& i : ans) mx = max(mx, i);
	printf("%lld", mx);
}

正解：单调队列

const int N = 3e6 + 8;
int a[N], s[N];
void eachT() {
	int n = read();
	std::deque<int> q;
	for (int i = 1; i <= n; ++i) a[i] = read();
	for (int i = n + 1; i <= 2 * n - 1; ++i) a[i] = a[i - n];
	for (int i = 1; i <= 2 * n - 1; ++i) s[i] = s[i - 1] + a[i];
	int ans = 0;
	for (int i = 1; i <= 2 * n - 1; ++i) {
		while (!q.empty() && s[i] <= s[q.back()]) q.pop_back();
		while (!q.empty() && q.front() < i - n) q.pop_front();
		q.push_back(i);
		ans += (i > n - 1 && s[q.front()] - s[i - n] >= 0);
	}
	printf("%d\n", ans);
}

显式史莱姆

const int N = 3e6 + 8;
int a[N];
void eachT() {
	int n = read();
	ll sum = 0;
	for (int i = 1; i <= n; ++i) sum += (a[i] = read());
	std::stack<int> s;
	if (sum >= 0) {
		for (int i = 1; i <= n; ++i) {
			while (!s.empty() && a[i] < 0) a[i] += s.top(), s.pop();
			while (s.empty() && a[i] < 0) a[i] += a[n--];
			s.push(a[i]);
		}
	}
	printf("%lld\n", s.size());
}

隐式史莱姆

const int N = 3e6 + 8;
ll s[N], pre[N], suf[N];
void eachT() {
	int n = read();
	for (int i = 1; i <= n; ++i)
		s[i] = s[i - 1] + read();
	pre[0] = suf[n + 1] = 8e18;
	for (int i = 1; i <= n; ++i)
		pre[i] = min(pre[i - 1], s[i]);
	for (int i = n; i >= 1; --i)
		suf[i] = min(suf[i + 1], s[i]);
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		ans += (pre[i - 1] + (s[n] - s[i - 1]) >= 0 && suf[i] - s[i - 1] >= 0);
	printf("%d\n", ans);
}