经过一下午缝合普通线段树与权值线段树,以及教练对于 pushdown 的指导,写了一个很奇怪的东西:
void pushdown(int p,int l,int r){
int m=(l+r)>>1;
t[lson[p]]+=t[p];
k[lson[p]]+=(m-l+1)*t[p];
t[rson[p]]+=t[p];
k[rson[p]]+=(r-m)*t[p];
t[p]=0;
}
void modify(int &p,int l,int r,int ml,int mr,int v){
if(!p){
tnt++;
p=tnt;
}
if(ml<=l&&r<=mr){
k[p]+=v*(r-l+1);
t[p]+=v;
cout<<k[p]<<","<<t[p]<<","<<l<<","<<r<<endl;
return;
}
int m=(l+r)/2;
if(!lson[p]){
tnt++;
lson[p]=tnt;
}
if(!rson[p]){
tnt++;
rson[p]=tnt;
}
pushdown(p,l,r);
if(ml<=m){
modify(lson[p],l,m,ml,mr,v);
}
if(mr>m){
modify(rson[p],m+1,r,ml,mr,v);
}
k[p]=k[lson[p]]+k[rson[p]];
}
t 是懒标记,k 是值。
请各路聚聚帮我看看哪里死了,现在的问题是修改不对(而且不是完全不对,整体是对的但是整体更小的区间就死了,比如 [1,10] 的更新是对的但是 [1,5] 和 [6,10] 都死了)