专栏文章

题解：P11587 [KTSC 2022 R2] 编程测试

FFelix72
P11587题解参与者 4已保存评论 6

文章操作

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

当前评论
6 条
当前快照
1 份
快照标识符
@mipftm6o
此快照首次捕获于
2025/12/03 11:18
3 个月前
此快照最后确认于
2025/12/03 11:18
3 个月前
查看原文
本文默认下标从 11 开始。
考虑这个复杂度很大的算法：先二分答案，检查函数中建网络流判断是否流满。
这个算法显然是正确的，并且它启示我们这个题相当于匹配问题，我们尝试用 Hall 定理分析出充要条件：
  • 对于 [L,R],x[L, R], x，[L,R][L, R] 的答案不小于 xx 当且仅当对于所有 [l,r][l, r] 满足 L≤l≤r≤RL \leq l \leq r \leq R，均有 [l,r][l, r] 区间的平均数不小于 xx。
不难发现这个结论和 Hall 定理是等价的。
于是我们有式子：
(ar−al−1)+(br−bl−2)r−l+1≥x\dfrac{(a_r - a_{l - 1}) + (b_r - b_{l - 2})}{r - l + 1} \geq x
其中 a,ba, b 已做前缀和处理，且 a0=b0=a−1=b−1=0a_0 = b_0 = a_{-1} = b_{-1} = 0。
这个式子中的 l,rl, r 相关性太强了，把它拆开：
(1−l)x+(al−1+bl−2)≤(−r)x+(ar+br)(1 - l)x + (a_{l - 1} + b_{l - 2}) \leq (-r)x + (a_r + b_r)
可以发现每个点作为左端点和右端点时分别对应了一条直线，“[l,r][l, r] 中的平均数不小于 xx”就可以用上面这个式子表示。
我们发现部分分正好有 li=1l_i = 1，可以二分 + 李超线段树解决，现在已经能得 7777 分了，是考场最高分。
进一步受到这个部分分启发，我们发现好像可以套一个分治。具体的，跑一遍猫树，假设当前区间 [L,R][L, R]，中点 midmid，有一个询问 [l,r][l, r] 被 midmid 切开。我们计算下面几个值，就可以得到 [l,r][l, r] 的答案：
  • 对 [L,mid][L, mid] 跑一遍 Subtask4 的算法，得到 [l,mid][l, mid] 的答案；
  • 对 [mid+1,R][mid + 1, R] 跑一遍 Subtask4 的算法，得到 [mid+1,r][mid + 1, r] 的答案；
  • 对 [l,mid][l, mid] 中选左端点，[mid+1,r][mid + 1, r] 中选右端点的情况求出最大的 xx。
这三个值取 min⁡\min 就是答案了。前两个可以直接算，后一个用二分 + 可持久化李超线段树解决。这样复杂度是 O(nlog⁡2n)O(n\log^2 n)。
CPP
 /* NE_Cat 4.15 */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 100010;
const long long INF = 2e16, mx = 400000000;
int n, m; long long a[N], b[N], pr_a[N], pr_b[N];
struct Range {int l, r, id;}; long long res[N];

int rt[N], idx, Root; long long f[N];
inline long long get_r(int p) {return pr_a[p] + pr_b[p];}
inline long long get_l(int p) {return pr_a[p - 1] + ((p == 1) ? 0 : pr_b[p - 2]);}
struct Line
{
	long long k, b;
	inline long long calc(long long x) {return k * x + b;}
};
inline Line get_line_l(int p) {return {1 - p, get_l(p)};}
inline Line get_line_r(int p) {return {-p, get_r(p)};}
struct SGT
{
	int ls, rs; Line maxn, minn; bool tag_mx, tag_mn;
	#define ls(x) tree[x].ls
	#define rs(x) tree[x].rs
	#define maxn(x) tree[x].maxn
	#define minn(x) tree[x].minn
	#define tag_mx(x) tree[x].tag_mx
	#define tag_mn(x) tree[x].tag_mn
} tree[N * 60];
inline void insert_mx(int &now, int his, int l, int r, Line cur)
{
	now = ++idx; tree[now] = tree[his];
	if(!tag_mx(now)) {tag_mx(now) = true; maxn(now) = cur; return ;}
	int mid = (l + r) >> 1;
	if(maxn(now).calc(mid) < cur.calc(mid)) swap(maxn(now), cur);
	if(l == r) return ;
	if(cur.calc(l) > maxn(now).calc(l)) insert_mx(ls(now), ls(his), l, mid, cur);
	if(cur.calc(r) > maxn(now).calc(r)) insert_mx(rs(now), rs(his), mid + 1, r, cur);
}
inline void insert_mn(int &now, int his, int l, int r, Line cur)
{
	now = ++idx; tree[now] = tree[his];
	if(!tag_mn(now)) {tag_mn(now) = true; minn(now) = cur; return ;}
	int mid = (l + r) >> 1;
	if(minn(now).calc(mid) > cur.calc(mid)) swap(minn(now), cur);
	if(l == r) return ;
	if(cur.calc(l) < minn(now).calc(l)) insert_mn(ls(now), ls(his), l, mid, cur);
	if(cur.calc(r) < minn(now).calc(r)) insert_mn(rs(now), rs(his), mid + 1, r, cur);
}
inline long long query_mx(int now, int l, int r, int pos)
{
	if(!now) return -INF;
	long long res = (tag_mx(now) ? maxn(now).calc(pos) : -INF);
	if(l == r) return res;
	int mid = (l + r) >> 1;
	if(pos <= mid) return max(res, query_mx(ls(now), l, mid, pos));
	else return max(res, query_mx(rs(now), mid + 1, r, pos));
}
inline long long query_mn(int now, int l, int r, int pos)
{
	if(!now) return INF;
	long long res = (tag_mn(now) ? minn(now).calc(pos) : INF);
	if(l == r) return res;
	int mid = (l + r) >> 1;
	if(pos <= mid) return min(res, query_mn(ls(now), l, mid, pos));
	else return min(res, query_mn(rs(now), mid + 1, r, pos));
}

inline void solve(int l, int r, vector < Range > q)
{
	int mid = (l + r) >> 1;
	
	Root = idx = 0;
	for(int i = mid + 1; i <= r; ++i)
	{
		insert_mx(Root, Root, 0, mx, {1 - i, get_l(i)});
		long long l = 0, r = 4e8; f[i] = 0;
		while(l <= r)
		{
			long long mid = (l + r) >> 1;
			if((-i) * mid + get_r(i) >= query_mx(Root, 0, mx, mid)) f[i] = mid, l = mid + 1;
			else r = mid - 1;
		}
		if(i > mid + 1) f[i] = min(f[i], f[i - 1]);
	}
	Root = idx = 0;
	for(int i = mid; i >= l; --i)
	{
		insert_mn(Root, Root, 0, mx, {-i, get_r(i)});
		long long l = 0, r = 4e8; f[i] = 0;
		while(l <= r)
		{
			long long mid = (l + r) >> 1;
			if((1 - i) * mid + get_l(i) <= query_mn(Root, 0, mx, mid)) f[i] = mid, l = mid + 1;
			else r = mid - 1;
		}
		if(i < mid) f[i] = min(f[i], f[i + 1]);
	}
	
	idx = 0;
	for(int i = l; i <= r; ++i) rt[i] = 0;
	insert_mn(rt[mid + 1], rt[mid + 1], 0, mx, get_line_r(mid + 1));
	for(int i = mid + 2; i <= r; ++i)
		insert_mn(rt[i], rt[i - 1], 0, mx, get_line_r(i));
	insert_mx(rt[mid], rt[mid], 0, mx, get_line_l(mid));
	for(int i = mid - 1; i >= l; --i)
		insert_mx(rt[i], rt[i + 1], 0, mx, get_line_l(i));
	for(Range qy : q)
	{
		if(qy.l <= mid && qy.r > mid)
		{
			res[qy.id] = min(f[qy.l], f[qy.r]);
			long long l = 0, r = 4e8, cur = 0;
			while(l <= r)
			{
				long long mid = (l + r) >> 1;
				if(query_mx(rt[qy.l], 0, mx, mid) <= query_mn(rt[qy.r], 0, mx, mid)) cur = mid, l = mid + 1;
				else r = mid - 1;
			}
			res[qy.id] = min(res[qy.id], cur);
		}
	}
	
	if(l == r) return ;
	vector < Range > qL, qR;
	for(Range qy : q)
	{
		if(qy.r <= mid) qL.push_back(qy);
		if(qy.l > mid) qR.push_back(qy);
	}
	q.clear(); q.shrink_to_fit();
	solve(l, mid, qL), solve(mid + 1, r, qR);
}

std::vector<int> testset(std::vector<int> A, std::vector<int> B, std::vector<int> L, std::vector<int> U)
{
	n = A.size(); m = L.size();
	for(int i = 1; i <= n; ++i) a[i] = A[i - 1];
	for(int i = 1; i < n; ++i) b[i] = B[i - 1];
	for(int i = 1; i <= n; ++i)
	{
		pr_a[i] = pr_a[i - 1] + a[i];
		pr_b[i] = pr_b[i - 1] + b[i];
	}
	memset(res, 0x3f, sizeof(res));
	vector < Range > q;
	for(int i = 1; i <= m; ++i)
	{
		int l = L[i - 1], r = U[i - 1]; ++l, ++r;
		if(l == r) res[i] = a[l] + b[l] + b[l - 1];
		q.push_back({l, r, i});
	}
	solve(1, n, q);
	vector < int > rec;
	for(int i = 1; i <= m; ++i) rec.push_back(res[i]);
	return rec;
}
/*
3 1
3 0 3 
4 4 
0 2
*/

评论

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

正在加载评论...