自动搬运

查看原文

来自洛谷，原作者为

	xzx34 但就是因为你能这样思考，才意味着你拥有着，能让你越来越强大的力量

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

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

以下是正文

题目要求你维护一段序列，支持操作包括：

1 区间修改为同一个数

2 令s[i] 表示当前前缀和，最小的i使得h<=s[i]并输出i-1；

大概思考一下，我们能想到用线段树解决这一问题。

首先是区间修改，线段树基本操作，不谈。

然后是怎么处理操作2，我们可以在每个线段树上的每个节点上存上

sum 表示这个节点下数值和

lsum 表示这个节点对应的区间从左开始的最大值

然后就可以处理了。。。

设计一个“爬”函数，根节点开始爬。

如果lson的lsum大于h，则爬向lson；否则爬向rson，h-=lson的sum。

这里的正确性真的是很显然的，建议手玩。

但是普通的线段树过不了这题。有n=1e9的瓶颈，空间会炸。

有两种方法解决这一限制，动态开点线段树和离散化。我使用的是前者，相对好打一点。

然后有很温柔的小哥哥让我教怎么打动态开点线段树。其实动态开点线段树真的很好打好想。我们进行的是区间修改，因为有懒标记的存在，几乎所有的操作都不会访问到叶节点。因此，我们很多提前开出来的节点几乎从来不会被访问！这就很亏，很烦。

考虑一个暴力的想法：随着我的访问去开点。对于每一个节点，如果我是第一次访问它，我就把它设为++tot，不然它的存在与否就不重要。

这就是动态开点线段树的思路，实际上通过这种操作，你的空间复杂度就不再与序列长度挂钩，而是与操作次数挂钩。非常的舒服。

代码如下：

#include <bits/stdc++.h>
#define re register int 
#define il inline
#define ll int
#define ls t[k].lson
#define rs t[k].rson
using namespace std;
const int inf=1e9;
il int read(){
	char c=getchar();int z=0,f=1;
	while(c!='-'&&(c>'9'||c<'0')) c=getchar();
	if(c=='-') f=-1,c=getchar();
	while(c>='0'&&c<='9') z=(z<<1)+(z<<3)+c-'0',c=getchar();
	return z*f;
}
int tot=1;
struct TREE{
	int l,r,lson,rson;
	ll lsum,sum,add;
	bool book;
}t[4500005];
il void check(int k){//动态开点 
	int mid=t[k].l+t[k].r>>1;
	if(!ls){ls=++tot;t[ls].l=t[k].l,t[ls].r=mid;}
	if(!rs){rs=++tot;t[rs].r=t[k].r,t[rs].l=mid+1;}
}
il void spread(int k){//基本操作下传信息 
	if(!t[k].book) return ;t[k].book=0;
	t[ls].add=t[rs].add=t[k].add;t[ls].book=t[rs].book=1;
	t[ls].sum=(t[ls].r-t[ls].l+1)*t[k].add;
	t[rs].sum=(t[rs].r-t[rs].l+1)*t[k].add;
	if(t[ls].sum>0) t[ls].lsum=t[ls].sum;
	else t[ls].lsum=t[k].add;
	if(t[rs].sum>0) t[rs].lsum=t[rs].sum;
	else t[rs].lsum=t[k].add;
}
il void change(int k,int l,int r,ll d){//基本操作修改 
	if(t[k].r<l||t[k].l>r) return;
	if(t[k].l>=l&&t[k].r<=r){
		t[k].add=d;t[k].sum=d*(t[k].r-t[k].l+1);t[k].book=1;
		if(t[k].sum>0) t[k].lsum=t[k].sum;
		else t[k].lsum=t[k].add;
		return ;
	}
	check(k);//防止越界动态开点 
	spread(k);
	change(ls,l,r,d);change(rs,l,r,d);
	t[k].sum=t[ls].sum+t[rs].sum;//更新关键信息 
	t[k].lsum=max(t[ls].sum+t[rs].lsum,t[ls].lsum);//更新关键信息 
}
int ans;
il void pa(int k,ll h){//爬 
	if(t[k].l==t[k].r){
		if(h>=t[k].lsum) ans=t[k].l;
		else ans=t[k].l-1;
		return ;
	}
	check(k);spread(k);
	if(h>=t[ls].lsum) pa(rs,h-t[ls].sum);
	else pa(ls,h);
}
int n;char c;
int main (){
	n=read();t[1].l=1,t[1].r=n;
	while(1){
		cin>>c;if(c=='E') return 0;
		if(c=='Q'){
			ll h=read();pa(1,h);
			cout<<ans<<'\n';
		}
		if(c=='I'){
			int l=read(),r=read(),d=read();
			change(1,l,r,d);
		}
	}
	return 0;
} 

这篇代码可以拿下96分，不能AC，还是会被卡空间。

这篇代码的空间复杂度还能继续优化。

为了便于初学者理解，我存了每个节点的l，r。

这个空间开销是多余的，可以在函数中保留l，r信息，不需要存下来。

把这一点优化了以后就可以愉快的AC了。希望对读者有帮助吧。