线段树动态开点
cpp
struct SegmentTree{
int ls[N],rs[N],sum[N],tag[N];
int tot=0;
SegmentTree(){
init();
}
void init(){
tot=0;
}
void pushup(int p){
sum[p]=sum[ls[p]]+sum[rs[p]];
}
void pushdown(int p,int l,int r){
if(tag[p]!=-1){
if(!ls[p])ls[p]=++tot;
if(!rs[p])rs[p]=++tot;
int mid=l+r>>1;
sum[ls[p]]=tag[p]*(mid-l+1);
sum[rs[p]]=tag[p]*(r-mid);
tag[ls[p]]=tag[rs[p]]=tag[p];
tag[p]=-1;
}
}
void modify(int &p,int l,int r,int L,int R,int x){
if(!p)p=++tot;
if(l<=L&&r>=R){
sum[p]=x*(R-L+1);
tag[p]=x;
return;
}
pushdown(p,L,R);
int mid=L+R>>1;
if(l<=mid)modify(ls[p],l,r,L,mid,x);
if(r>mid)modify(rs[p],l,r,mid+1,R,x);
pushup(p);
}
} seg;