专栏文章

题解：P10169 [DTCPC 2024] mex,min,max

TT0mle
P10169题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min94wuu
此快照首次捕获于
2025/12/01 22:35
3 个月前
此快照最后确认于
2025/12/01 22:35
3 个月前
查看原文
首先这个 min⁡\min 和 mex⁡\operatorname{mex} 在一块就很涩啊，他们中一定有一个 00。
先假设 mex⁡=0\operatorname{mex}=0，此时可以看成序列被 00 分成若干块，每块分别求解即可。此时的条件为 max⁡−min⁡≤k\max-\min\le k。然后对于固定右端点 rr，左端点是满足单调性的，二分加 st 表即可。
然后是 min⁡=0\min=0。这部分考虑容斥：先假装 min⁡\min 就是 00，用整个序列的答案减去被 00 分开的块的答案。正确性显然。
此时的条件为 mex⁡≥max⁡−k\operatorname{mex}\ge\max-k。max⁡\max 的处理就套路了，搞个笛卡尔树或者直接算贡献区间。
我这里直接算的贡献区间。假如 ii 贡献区间为 [l,r][l,r]，若 ai≤ka_i\le k 那么包含 ii 的 [l,r][l,r] 子区间都满足条件。
否则我们考虑笛卡尔树上遍历轻子树，也就是遍历 [l,i][l,i] 和 [i,r][i,r] 长度较小的那一个。假设 i−l<r−ii-l<r-i，枚举 j∈[l,i]j\in[l,i]。此时考虑 mex⁡≥ai−k\operatorname{mex}\ge a_i-k 的意义是 [0,ai−k)[0,a_i-k) 的数都出现，于是我们考虑持久化权值线段树，每个位置建版本，第 ii 个位置为数 ii 的最后出现位置，支持区间最大值即可。
然后再持久化线段树上查位置 jj 的版本 [0,ai−k)[0,a_i-k) 的最大值为，然后简单分讨即可。
对于 r−i<i−lr-i<i-l 是类似的。
复杂度 O(nlog⁡2n)O(n\log^2n)。
比较考验码力。
CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
// const int V = ;
// const int mod = ;
typedef unsigned us;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vl;
template <class T> using pq = priority_queue <T>;
template <class T> using pqg = priority_queue <T, vector <T>, greater <T> >;

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define repr(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define perr(i, a, b) for (int i = (a); i > (b); --i)

#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back

template <class T1, class T2> inline void ckmn(T1 &a, T2 b) { (a > b) && (a = b, 0); }
template <class T1, class T2> inline void ckmx(T1 &a, T2 b) { (a < b) && (a = b, 0); }

namespace IO {
	// char buf[1 << 23], *p1 = buf, *p2 = buf;
	// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
	template <class T> void rd(T &a, unsigned c = 0) {
		while (c = getchar(), c < 48 || c > 57);
		for (a = 0; c >= 48 && c <= 57; c = getchar()) a = (a << 3) + (a << 1) + (c ^ 48);
	}
	template <class T> void wrt(T x) { if (x > 9) wrt(x / 10); putchar(x % 10 ^ 48); }
} using IO::rd; using IO::wrt;

int n, k, a[N];
int st1[N][20], st2[N][20], lg2[N];

int stq1(int l, int r) {
	int k = lg2[r - l + 1];
	return min(st1[l][k], st1[r - (1 << k) + 1][k]);
}
int stq2(int l, int r) {
	int k = lg2[r - l + 1];
	return max(st2[l][k], st2[r - (1 << k) + 1][k]);
}

namespace smt1 {
	struct Seg {
		int ls, rs, mx;
		#define ls(p) tr[p].ls
		#define rs(p) tr[p].rs
		#define mx(p) tr[p].mx
	} tr[N * 25];
	#define M (L + R >> 1)
	int tot;

	int build(int L, int R) {
		if (L == R) {
			int p = ++tot;
			mx(p) = n + 1;
			return p;
		}
		int p = ++tot;
		mx(p) = n + 1;
		ls(p) = build(L, M), rs(p) = build(M + 1, R);
		return p;
	}
	int update(int p, int x, int k, int L, int R) {
		if (L == R) {
			int q = ++tot; tr[q] = tr[p];
			mx(q) = k;
			return q;
		}
		int q = ++tot; tr[q] = tr[p];
		if (x <= M) ls(q) = update(ls(p), x, k, L, M);
		else rs(q) = update(rs(p), x, k, M + 1, R);
		mx(q) = max(mx(ls(q)), mx(rs(q)));
		return q;
	}
	int query(int p, int l, int r, int L, int R) {
		if (l <= L && r >= R) return mx(p);
		if (r <= M) return query(ls(p), l, r, L, M);
		if (l > M)  return query(rs(p), l, r, M + 1, R);
		return max(query(ls(p), l, r, L, M), query(rs(p), l, r, M + 1, R));
	}
}

namespace smt2 {
	struct Seg {
		int ls, rs, mn;
		#define mn(p) tr[p].mn
	} tr[N * 25];
	int tot;

	int build(int L, int R) {
		if (L == R) {
			int p = ++tot;
			mn(p) = 0;
			return p;
		}
		int p = ++tot;
		mn(p) = 0;
		ls(p) = build(L, M), rs(p) = build(M + 1, R);
		return p;
	}
	int update(int p, int x, int k, int L, int R) {
		if (L == R) {
			int q = ++tot; tr[q] = tr[p];
			mn(q) = k;
			return q;
		}
		int q = ++tot; tr[q] = tr[p];
		if (x <= M) ls(q) = update(ls(p), x, k, L, M);
		else rs(q) = update(rs(p), x, k, M + 1, R);
		mn(q) = min(mn(ls(q)), mn(rs(q)));
		return q;
	}
	int query(int p, int l, int r, int L, int R) {
		if (l <= L && r >= R) return mn(p);
		if (r <= M) return query(ls(p), l, r, L, M);
		if (l > M)  return query(rs(p), l, r, M + 1, R);
		return min(query(ls(p), l, r, L, M), query(rs(p), l, r, M + 1, R));
	}
}

int rt1[N], rt2[N];

int f[N], g[N];
stack <int> stk;

ll play(int s, int t) {
	while (stk.size()) stk.pop();
	rep(i, s, t) f[i] = s - 1, g[i] = t + 1;
	rep(i, s, t) {
		while (stk.size() && a[i] > a[stk.top()]) g[stk.top()] = i, stk.pop();
		if (stk.size()) f[i] = stk.top();
		stk.push(i);
	}
	ll R = 0;
	rep(i, s, t) {
		int l = f[i] + 1, r = g[i] - 1;
		if (a[i] <= k) { R += 1ll * (i - l + 1) * (r - i + 1); continue; }
		if (i - l < r - i) {
			rep(j, l, i) {
				int pos = max(smt1::query(rt1[j], 0, a[i] - k - 1, 0, n), i);
				if (pos > r) continue;
				R += r - pos + 1;
			}
		} else {
			rep(j, i, r) {
				int pos = min(smt2::query(rt2[j], 0, a[i] - k - 1, 0, n), i);
				if (pos < l) continue;
				R += pos - l + 1;
			}
		}
	}
	return R;
}
void solve() {
	rd(n), rd(k);
	rep(i, 1, n) rd(a[i]), st1[i][0] = st2[i][0] = a[i];
	rep(i, 2, n) lg2[i] = lg2[i >> 1] + 1;
	rep(j, 1, 19) {
		rep(i, 1, n - (1 << j) + 1) {
			st1[i][j] = min(st1[i][j - 1], st1[i + (1 << j - 1)][j - 1]);
			st2[i][j] = max(st2[i][j - 1], st2[i + (1 << j - 1)][j - 1]);
		}
	}
	rt1[n + 1] = smt1::build(0, n);
	rt2[0] = smt2::build(0, n);
	per(i, n, 1) rt1[i] = smt1::update(rt1[i + 1], a[i], i, 0, n);
	rep(i, 1, n) rt2[i] = smt2::update(rt2[i - 1], a[i], i, 0, n);

	ll ans = play(1, n);
	int lst = 0;
	rep(i, 1, n) {
		if (!a[i]) {
			if (i != lst + 1) ans -= play(lst + 1, i - 1);
			lst = i;
			continue;
		}
		int l = lst + 1, r = i;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (stq2(mid, i) - stq1(mid, i) <= k) r = mid;
			else l = mid + 1;
		}
		ans += i - l + 1;
	}
	if (lst != n) ans -= play(lst + 1, n);
	wrt(ans);
}
int main() {
	int T = 1;
	if (0) rd(T);
	while (T--) solve();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...