题解 P5848 【[IOI2005]mou】
题目要求你维护一段序列，支持操作包括：
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了。希望对读者有帮助吧。