专栏文章

题解：CF338E Optimize!

封封禁用户
CF338E题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mipxwqzt
此快照首次捕获于
2025/12/03 19:45
3 个月前
此快照最后确认于
2025/12/03 19:45
3 个月前
查看原文
一种不基于值域的做法，不知道和 hall 定理有啥关系。
我们需要 Ai+Bi≥H⇒Ai≥H−BiA_i+B_i\ge H\Rightarrow A_i\ge H-B_i，把所有的 Bi←H−BiB_i\leftarrow H-B_i，直接就转化为判断对于每一个长度为 lenlen 的 AA 的连续子序列里面排两者都排序之后是不是 ∀i∈[1,M],Ai≥Bi\forall i\in [1,M],A_i\ge B_i。
考虑把 BB 排序，二分出 AA 的合法区间，相当于我们需要实时判断 ∀i∈[1,N],prei≤i\forall i\in [1, N], pre_i \le i，对于 preipre_i 的修改是单点的。
发现这个东西没那么好维护，因为是单点的修改，所以把每一个点的贡献覆盖上去（区间 +1+1）就可以了（其实这里区间覆盖也是可以的，就是序列上覆盖一段然后另一段加等差数列），我们只需要维护区间 add，全局 min 的线段树即可。
CPP
#include <bits/stdc++.h>
#define lb(x) (x&-x)
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)

using namespace std;
using i64 = long long;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
void chmin(int &x, int c) {x = min(x, c);}
void chmax(int &x, int c) {x = max(x, c);}

const int maxn = 15e4 + 10, mod = 998244353;
int N, M, K;
int A[maxn], B[maxn], pos[maxn];
namespace segt {
int mn[maxn << 1], tag[maxn << 1];
void pushdown (int u) {
	if (tag[u]) {
		mn[u << 1] += tag[u]; tag[u << 1] += tag[u];
		mn[u << 1 | 1] += tag[u]; tag[u << 1 | 1] += tag[u];
		tag[u] = 0;
	}
}
void pushup (int u) {
	mn[u] = min (mn[u << 1], mn[u << 1 | 1]);
}
void build (int u, int l, int r) {
	if (l == r) {
		mn[u] = -(M - l + 1); tag[u] = 0; return;
	}
	int mid = (l + r) >> 1;
	build (u << 1, l, mid), build (u << 1 | 1, mid + 1, r), pushup (u); 
}
void upd (int u, int l, int r, int ql, int qr, int x) {
	if (ql > qr) return;
	if (ql <= l && qr >= r) {
		mn[u] += x; tag[u] += x;
		return;
	}
	int mid = (l + r) >> 1;
	pushdown (u);
	if (ql <= mid) upd (u << 1, l, mid, ql, qr, x);
	if (qr > mid) upd (u << 1 | 1, mid + 1, r, ql, qr, x);
	pushup (u); 
}
}

void solve() {
	cin >> N >> M >> K;
	L (i, 1, M) cin >> B[i], B[i] = K - B[i];
	L (i, 1, N) cin >> A[i];
	sort (B + 1, B + 1 + M);
	L (i, 1, N) {
		int l = 0, r = M, res = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			(A[i] >= B[mid] ? res = mid, l = mid + 1 : r = mid - 1);
		}
		pos[i] = res;
	}
	segt::build (1, 1, M);
	int res = 0;
	L (i, 1, N) {
		segt::upd (1, 1, M, 1, pos[i], 1);
		if (i >= M) {
			res += segt::mn[1] >= 0;
			segt::upd (1, 1, M, 1, pos[i - M + 1], -1);
		}
	}
	cout << res << '\n';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1;
  while (T--)solve();
  return 0;
}

评论

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

正在加载评论...