自动搬运

查看原文

来自洛谷，原作者为

	Saliеri 镜影倒倾，错的人陪着错的你

搬运于2025-08-24 22:04:59，当前版本为作者最后更新于2021-03-12 10:36:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

@chen_qian 先写了这一种做法，这篇题解权当是一个对他的题解的补充。

其实主要是感觉他写的太长了

考虑每一种操作对所有数组造成的影响。

• 对于 0 操作，因为只会改大，并且 C 数组也递增，所以相当于区间 $[x,p)$ 上的一个区间 cover。（p 指第一个大于 y 的 C 数组值所在的下标）

• 对于 1 操作，单点修改，不再赘述。

出现了区间 cover，单点修改，线段树没得跑了。

由于线段树上维护的都是 C 数组，所以下面的 A 就代指 题面中的 C 数组了。

接下来来看答案的维护。

我们发现，每一次如果要用 naive 的方式正确维护所有区间，那么必然需要递归到叶子来暴力修改。而这是我们所不能接受的。

之前有一些题，也是需要暴力递归到叶子，我们的优化方式是什么？

参考操作本身的性质，通过一定的剪枝，使得区间可以被合并处理，达到降低复杂度的目的。

那就来看看这个题什么时候区间能够合并处理吧。（对于区间 cover 操作）

• $A_{\min} \geq B_{\max}$ , 这样因为只会改大，所以不会对区间的答案造成任何影响。打上区间 cover 的 tag 后就可以直接返回。

• $v \leq B_{\min}$ , 这样一整个区间的答案数组都将会是改为的值，打上区间 cover 的 tag，更新区间的答案，返回。

• 其他情况我们没有办法。只能递归到叶子暴力更新。

考虑这样做的时间复杂度的级别。

如果我们将 $A_i < B_i$ 的个数看做总势能的话，每一次递归到叶子的操作都会使得总势能 -1。

而唯一能够增加势能的方式就是对于 B 的 单点修改。每一次最多使得总势能 +1。

由于总势能在 $O(n+q)$ 级别，所以递归到叶子的操作最多执行这么多次。

其余的操作都可以看做是递归到叶子路上的长度为 1 的小分支，无足轻重。

所以这么做的总时间复杂度就被证明了是 $O(n\log^2 n$)的（认为 n,q 等价）。

关于实现：（这才是万恶之源）

其实根本不用像 @chen_qian 的题解那样维护这么多东西 /lh

对于每个节点，维护 $Amx,Amn,Bmx,Bmn,tag,tagty,ans$ 即可。

注释：

• tag : 区间cover tag。

• tagty ： 因为要考虑这一次的区间cover是否要更新子区间的答案（讨论中情况 1&2 的区别），所以加一个这个标记。

• 其他：就比较显然。

关于如何找到区间 cover 的右端点：线段树上二分即可。我的实现比较丑，将就着看吧。

其他都是线段树基本操作，不再赘述。

代码：

#include <cstdio>
#include <cstring>
const int maxn = 1e5+5,mod = 1e9+7;
inline int min(int a,int b) {return a<b?a:b;}
inline int max(int a,int b) {return a>b?a:b;}
inline int ksm(int a,int x) {
	int base=a,ans=1;
	while(x) {
		if(x&1)ans = 1ll*ans*base%mod;
		base = 1ll*base*base%mod;
		x >>= 1;
	}
	return ans;
}
int n,m,tmp,a[maxn],b[maxn],amn[maxn<<2],amx[maxn<<2],bmn[maxn<<2],bmx[maxn<<2],ans[maxn<<2],tag[maxn<<2],ty[maxn<<2];
void pushup(int k) {
	ans[k] = 1ll*ans[k<<1]*ans[k<<1|1]%mod;
	amx[k] = max(amx[k<<1],amx[k<<1|1]),bmx[k] = max(bmx[k<<1],bmx[k<<1|1]);
	amn[k] = min(amn[k<<1],amn[k<<1|1]),bmn[k] = min(bmn[k<<1],bmn[k<<1|1]);
}
void build(int k,int l,int r) {
	if(l == r)return amn[k]=amx[k]=a[l],bmx[k]=bmn[k]=b[l],ans[k]=min(a[l],b[l]),void();
	int mid = l+r>>1;
	build(k<<1,l,mid),build(k<<1|1,mid+1,r),pushup(k);
}
void gtag(int k,int l,int r,int v,int typ) {
	tag[k] = v,ty[k] = typ,amn[k] = amx[k] = v;
	if(typ&1)ans[k] = ksm(v,r-l+1);
}
void pushdown(int k,int l,int r,int mid) {if(~tag[k])gtag(k<<1,l,mid,tag[k],ty[k]),gtag(k<<1|1,mid+1,r,tag[k],ty[k]),tag[k] = -1,ty[k] = 0;}
int getpos(int k,int l,int r,int v) {
	if(amx[k]<=v)return n+1;
	if(l==r)return l;
	int mid = l+r>>1;
	pushdown(k,l,r,mid);
	if((tmp=getpos(k<<1,l,mid,v)) != n+1)return tmp;
	return getpos(k<<1|1,mid+1,r,v);
}
void cover(int k,int l,int r,int x,int y,int v) {
	if(l>y||r<x)return ;
	if(l>=x&&r<=y) {
		if(amn[k] >= bmx[k])return gtag(k,l,r,v,2);
		if(max(amx[k],v) <= bmn[k])return gtag(k,l,r,v,1);
		if(l == r)return amn[k]=amx[k]=v,ans[k]=bmn[k],void();
	}
	int mid = l+r>>1;
	pushdown(k,l,r,mid);
	cover(k<<1,l,mid,x,y,v),cover(k<<1|1,mid+1,r,x,y,v),pushup(k);
}
void update(int k,int l,int r,int p,int v) {
	if(l == r)return bmn[k] = bmx[k] = v,ans[k] = min(amn[k],bmn[k]),void();
	int mid = l+r>>1;
	pushdown(k,l,r,mid);
	p<=mid?update(k<<1,l,mid,p,v):update(k<<1|1,mid+1,r,p,v);
	pushup(k);
}
int main() {
	memset(tag,-1,sizeof(tag));
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; ++i)scanf("%d",&a[i]),a[i] = max(a[i],a[i-1]);
	for(int i=1; i<=n; ++i)scanf("%d",&b[i]);
	build(1,1,n);
	while(m--) {
		int ty,x,y;
		scanf("%d %d %d",&ty,&x,&y);
		if(ty == 0) {
			int pos = getpos(1,1,n,y);
			if(x<=pos-1)cover(1,1,n,x,pos-1,y);
		}
		if(ty == 1)update(1,1,n,x,y);
		printf("%d\n",ans[1]);
	}
	return 0;
}

upd: 修复了部分笔误以及代码缩进问题。