自动搬运

查看原文

来自洛谷，原作者为

	LFCode 世界是统一而纯粹的；构造了一切事物的元素只有三件。

搬运于2025-08-24 22:32:21，当前版本为作者最后更新于2021-10-20 21:56:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一些碎碎念

几个月前赛时匆忙写出的代码码量达到了 $\text{3.2K}$，最近对那份代码进行了一些精简，重构之后码量减少了 $\text{1K}$，而且去掉了很多冗余的变量和步骤。

下面介绍一种两枚 $\log$ 的做法。这种做法不仅思维、代码难度都很低（比 std 短得多），而且跑得很快（俩 $\log$ 碾标算）。最重要的是完全不会被卡空间（比如就不用 std 的神必 short 卡空间技巧）。

本场比赛应该只有这个 Subtask 算是卡常的

哈哈。

其实赛时墨染空同志写的就是这种做法（见囧女士题解评论区），但是他惨遭 MLE 打击……或许是没有用指针优化空间的缘故？

解法

不知道大家有没有做过 向量集 这道题目。那道题目同样是强制在线末尾插入、区间查询，我们使用线段树来维护凸包。具体地，当向树上某个节点中插入信息时，我们将该信息暂时搁置。等到一个节点被插满之后，我们使用归并排序思想将其对应的凸包建出。

这种思想完全可以套用至本题中。同样是将某个节点插满之后统计子节点的区间信息，下面我们考虑如何较为完整地记录当前节点的信息，并对来自子区间的信息进行合并。

对于信息的记录，如果去掉高度范围的限制，区间颜色段数是一个经典问题，两个区间信息的合并可以 $O(1)$ 完成。现在加上了高度范围的限制，我们不得不保存将节点中的每一个对象作为限度时的答案。具体地，在经典区间颜色段数问题中，我们对每一个区间维护了三个量：$cnt,lc,rc$，分别表示颜色段数和两端点颜色。在本题中，我们需要对区间 $[l,r]$ 维护 $(r-l+1)$ 个四元组 $\{h,cnt,lc,rc\}$，$h$ 表示限制的最大高度，其他三个量同经典问题。

合并方式类似向量集一题，考虑对子区间维护的所有信息进行归并。归并过程中，不断寻找两个子节点中记录的 $h$ 中较小的一方，并在另一个子节点中找出 $h$ 不高于当前信息的最大四元组，对这两个区间信息进行 $O(1)$ 合并即可。

如何处理查询？同样套用向量集的做法，对于每一次查询，我们在 $O(\log n)$ 个区间中进行二分，并同样用处理经典区间颜色段数问题的方式合并区间信息。

对于信息的保存，用 $\text{vector}$ 当然是可以的，但是听说会卡空间，所以我采用了另一种（可能会更优秀的）存储方式：开一个大数组存下整棵树上所有节点的信息，并用指针存下每个节点信息在大数组上对应的位置。

至此，本题得到完美解决。

代码：

struct ret{
	int mx,cnt,lc,rc;
	ret(){lc=rc=cnt=0;}
	ret(int mm,int cc,int ll,int rr){mx=mm;cnt=cc;lc=ll;rc=rr;}
	ret operator +(const ret b){
		if(!cnt)return b;
		if(!b.cnt)return *this;
		return ret(Max(mx,b.mx),cnt+b.cnt-(rc==b.lc),lc,b.rc);
	}
	bool operator <=(const ret b)const{return mx<=b.mx;}
	bool operator <(const int x)const{return mx<x;}
};
bool operator <(const int x,const ret y){return x<y.mx;}
bool change(int k,int l,int r,int x,int y,int h){
	if(l==r){
		info[k]=inp;inp++;info[k][0]=ret(h,1,y,y);//inp和info为上文提到过的索引指针
		return true;
	}
	int mid=(l+r)>>1;
	if(x<=mid)change(k<<1,l,mid,x,y,h);
	else change(k<<1|1,mid+1,r,x,y,h);
	if(x!=r)return true;
	int l1=mid-l+1,l2=r-mid;int i=0,j=0,np=0;
	info[k]=inp;inp+=(r-l+1);
	while(i<l1||j<l2){
		if((info[k<<1][i]<=info[k<<1|1][j]&&i<l1&&j<l2)||j>=l2){
			info[k][np]=info[k<<1][i]+(j==0?ret():info[k<<1|1][j-1]);
			i++;np++;
		}
		else{
			info[k][np]=(i==0?ret():info[k<<1][i-1])+info[k<<1|1][j];
			j++;np++;
		}
	}
	return true;
}
ret ask(int k,int l,int r,int x,int y,int h){
	if(l>=x&&r<=y){
		if(info[k][0].mx>h)return ret();
		int pos=std::upper_bound(info[k],info[k]+r-l+1,h)-info[k]-1;
		return info[k][pos];
	}
	int mid=(l+r)>>1;
	if(y<=mid)return ask(k<<1,l,mid,x,y,h);
	if(mid<x)return ask(k<<1|1,mid+1,r,x,y,h);
	ret xx=ask(k<<1,l,mid,x,y,h)+ask(k<<1|1,mid+1,r,x,y,h);
	return xx;
}
int main(){
	n=read();m=read();len=n+m;int k=read();inp=ii;//ii为上文提到过的大数组
	for(int i=1;i<=n;i++)ta[i]=read();
	for(int i=1;i<=n;i++)change(1,1,len,i,read(),ta[i]);
	for(int i=1;i<=m;i++){
		int opt=read();
		if(opt&1){
			int l=read()^(k*lans);int r=read()^(k*lans);int x=read()^(k*lans);
			ret ans=ask(1,1,len,l,r,x);
			printf("%d\n",lans=ans.cnt);
		}
		else{
			int h=read()^(k*lans);int y=read()^(k*lans);
			change(1,1,len,++n,y,h);
		}
	}
}