专栏文章

题解：P11733 [集训队互测 2015] 上帝之手

MMeta_Morph
P11733题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min98gyj
此快照首次捕获于
2025/12/01 22:38
3 个月前
此快照最后确认于
2025/12/01 22:38
3 个月前
查看原文

[集训队互测 2015] 上帝之手 题解

博客园：[集训队互测 2015] 上帝之手 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

线段树，分块。

分析

约定

定义更换：li→limi,di→delil_i\to lim_i,d_i\to del_i。
定义查询 F(l,r,x)F(l,r,x)（如果 xx 空缺，默认为 liml−1lim_{l-1}）表示 xx 一直做 →min⁡{x+deli,limi}\to \min\{ x+del_i,lim_i \} 得到的答案。

快速查询

假设给定的是 F(l,r)F(l,r)，那么我们就要求出：
min⁡i=lr+1{limi−1+∑j=irdelj}\min_{i=l}^{r+1} \{ lim_{i-1} + \sum_{j=i}^r del_j\}
设 Deli=∑j=1ideli,Di=limi−DeliDel_i= \sum_{j=1}^i del_i,D_i = lim_i-Del_i，原式化为：
min⁡i=lr+1{limi−1+Delr−Deli−1}=min⁡i=l−1rDi+Delr\min_{i=l}^{r+1} \{ lim_{i-1} + Del_r - Del_{i-1}\} \\ = \min_{i=l-1}^{r} D_{i} + Del_r\\
如果是 F(l,r,x)F(l,r,x) 其实也一样，查询的是：
min⁡{x−Dell−1,min⁡i=lrDi}+Delr\min \{ x - Del_{l-1},\min_{i=l}^{r} D_{i} \} + Del_r \\
线段树维护，单次查询 O(log⁡n)O(\log{n})。

询问 1

给定 l,r,kl,r,k，求 F(j,r),j∈[l,r]F(j,r),j\in[l,r] 中第 kk 大的。
那么很容易看出 F(j,r)F(j,r) 具有单调不减的性质，所以答案就是 F(r−k+1,r)F(r-k+1,r)。

询问 2

给定 l,r,kl,r,k，求 F(j,r,k),j∈[l,r]F(j,r,k),j\in[l,r] 中最大的。
考虑把定义式拉出来，就是：
F(j,r,k)=min⁡{k−Delj−1,min⁡i=jrDi}+DelrF(j,r,k)=\min \{ k - Del_{j-1},\min_{i=j}^{r} D_{i} \} + Del_r \\
设 f(j)=k−Delj−1,g(j)=min⁡i=jrDif(j) = k - Del_{j-1},g(j) = \min_{i=j}^{r} D_{i}，则有 f(j)f(j) 非严格单调递减，g(j)g(j) 非严格单调递增。
拆掉外层的 min⁡\min，二分出边界，分别求出 f(j)≤g(j)f(j)\le g(j) 和 g(j)≤f(j)g(j)\le f(j) 时的答案即可。二分套线段树可以做到 O(log⁡2n)O(\log^2{n})。
考虑满足 g(j)≤f(j)g(j)\le f(j)。则有：
min⁡i=jrDi≤k−Delj−1min⁡i=jrDi+Delj−1≤k\begin{aligned} \min_{i=j}^{r} D_{i} & \le k - Del_{j-1}\\ \min_{i=j}^{r} D_{i} + Del_{j-1} & \le k \\ \end{aligned}
故也可以线段树上二分做到复杂度 O(log⁡n)O(\log{n})（不过其实没有必要）。

询问 3

给定 l,rl,r，求 F(j,r),j∈[l,r]F(j,r),j\in[l,r] 总共有多少种本质不同的值。
我们还是把定义式拉出来看：
F(j,r)=min⁡i=j−1rDi+DelrF(j,r) = \min_{i=j-1}^{r} D_{i} + Del_r\\
发现其实是求 min⁡i=j−1rDi\min_{i=j-1}^{r} D_{i} 本质不同值的个数，也就是 DD 的区间严格后缀最小值个数，变成 P4198 楼房重建 - 洛谷 (luogu.com.cn) 这题了。注意特判一下 DrD_r。
复杂度 O(log⁡2n)O(\log^2{n})。

代码

总复杂度 O(nlog⁡n+mlog⁡2n)O(n\log{n}+m\log^2{n})。
CPP
constexpr int N(1e5+10);

int n,Q;
int del[N],lim[N];
struct SEG {
	struct node {
		int D,C;
		node(int D=0,int C=0):D(D),C(C) {}
	} tr[N<<2];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
	void Up(int p,int l,int r) { tr[p].D=min(tr[ls].D,tr[rs].D),tr[p].C=Count(tr[rs].D,ls,l,mid); }

	void Build(int p=1,int l=0,int r=n) {
		if(l==r)return tr[p]=node(lim[l]-del[l],0),void();
		Build(ls,l,mid),Build(rs,mid+1,r),Up(p,l,r);
	}

	void Update(int x,int p=1,int l=0,int r=n) {
		if(l==r)return tr[p]=node(lim[l]-del[l],0),void();
		return x<=mid?Update(x,ls,l,mid):Update(x,rs,mid+1,r),Up(p,l,r);
	}

	int Min(int L,int R,int p=1,int l=0,int r=n) {
		if(L<=l&&r<=R)return tr[p].D;
		if(R<=mid)return Min(L,R,ls,l,mid);
		if(mid<L)return Min(L,R,rs,mid+1,r);
		return min(Min(L,R,ls,l,mid),Min(L,R,rs,mid+1,r));
	}

	int Count(int k,int p=1,int l=0,int r=n) {
		if(tr[p].D>=k)return 0;
		if(l==r)return tr[p].D<k;
		return tr[rs].D>=k?Count(k,ls,l,mid):tr[p].C+Count(k,rs,mid+1,r);
	}

	int Query(int L,int R,int &k,int p=1,int l=0,int r=n) {
		if(L<=l&&r<=R) {
			int res(Count(k,p,l,r));
			return tomin(k,tr[p].D),res;
		}
		if(mid<L)return Query(L,R,k,rs,mid+1,r);
		if(R<=mid)return Query(L,R,k,ls,l,mid);
		return Query(L,R,k,rs,mid+1,r)+Query(L,R,k,ls,l,mid);
	}
#undef ls
#undef rs
#undef mid
} seg;

void Change(int x,int d) { lim[x]=d,seg.Update(x); }

int Query1(int r,int k) { return seg.Min(r-k,r)+del[r]; }

int Query2(int l,int r,int k) {
	auto f=[&](int j) { return k-del[j-1]; };
	auto g=[&](int j) { return seg.Min(j,r); };
	int res(l-1);
	for(int L(l),R(r),mid((L+R)>>1); L<=R; mid=(L+R)>>1)g(mid)<=f(mid)?res=mid,L=mid+1:R=mid-1;
	int ans(0);
	if(res>=l)tomax(ans,g(res)+del[r]);
	if(res<r)tomax(ans,f(res+1)+del[r]);
	return ans;
}

int Query3(int l,int r) {
	if(l==r)return 1;
	int k(INF),res(seg.Query(l-1,r,k));
	if(lim[r]-del[r]>lim[r-1]-del[r-1])--res;
	return res;
}

signed main() {
	/*DE("Input");*/
	I(n,Q);
	FOR(i,1,n)I(del[i]);
	FOR(i,0,n)I(lim[i]);
	/*DE("Init");*/
	FOR(i,1,n)del[i]+=del[i-1];
	seg.Build();
	/*DE("Query");*/
	while(Q--) {
		int ty;
		I(ty);
		if(!ty) {
			int x,d;
			I(x,d),Change(x,d);
		} else if(ty==1) {
			int l,r,k;
			I(l,r,k),printf("%d\n",Query1(r,k));
		} else if(ty==2) {
			int l,r,k;
			I(l,r,k),printf("%d\n",Query2(l,r,k));
		} else {
			int l,r;
			I(l,r),printf("%d\n",Query3(l,r));
		}
	}
	return 0;
}

评论

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

正在加载评论...