普通线段树
核心在于上传标记（pushup）和下传标记（pushdown）以及懒标记的设计。
维护一个加法标记和乘法标记。
下传标记时，将乘法标记更新加法标记。
标记下传实现
void pushdown(int u,int l,int r){
int mid=l+r>>1;
tr[u<<1].val=(tr[u<<1].val*tr[u].mul+tr[u].add*(mid-l+1))%P;
tr[u<<1|1].val=(tr[u<<1|1].val*tr[u].mul+tr[u].add*(r-mid))%P;
tr[u<<1].mul=(tr[u<<1].mul*tr[u].mul)%P;
tr[u<<1|1].mul=(tr[u<<1|1].mul*tr[u].mul)%P;
tr[u<<1].add=(tr[u<<1].add*tr[u].mul+tr[u].add)%P;
tr[u<<1|1].add=(tr[u<<1|1].add*tr[u].mul+tr[u].add)%P;
tr[u].add=0;tr[u].mul=1;
}
维护懒标记 \(f(i)\) 和 \(g(i)\) 表示该区间的背包，在容量不超过 \(i\) 时，最大的价值、物品个数。
乘法操作时，我们直接将 \(f(i)\)（\(0\le i\le m\)） 全变成 \(f(i/w)\)，\(g(i)\) 全变成 \(g(i/w)\)。区间覆盖操作，我们就将 \(f(i)\) 变成 \(g(i)\times v\)。
下传懒标记的操作与这些相似。
注意乘法标记要每次更新后与 \(m+1\) 取较小值，因为 \(m+1\) 等价于比 \(m\) 大的所有数。
标记下传与上传实现
void pushup(int u){
for(int i=0;i<=m;i++){
tr[u].f[i]=0;tr[u].g[i]=0;
for(int j=0;j<=i;j++){
tr[u].f[i]=max(tr[u].f[i],tr[u<<1].f[j]+tr[u<<1|1].f[i-j]);
tr[u].g[i]=max(tr[u].g[i],tr[u<<1].g[j]+tr[u<<1|1].g[i-j]);
}
}
}
void pushdown(int u){
if(tr[u].lazy1>1){
for(int i=m;i>=0;i--)
tr[u<<1].f[i]=tr[u<<1].f[i/tr[u].lazy1],tr[u<<1|1].f[i]=tr[u<<1|1].f[i/tr[u].lazy1],
tr[u<<1].g[i]=tr[u<<1].g[i/tr[u].lazy1],tr[u<<1|1].g[i]=tr[u<<1|1].g[i/tr[u].lazy1];
tr[u<<1].lazy1=min(tr[u<<1].lazy1*tr[u].lazy1,(ll)m+1);
tr[u<<1|1].lazy1=min(tr[u<<1|1].lazy1*tr[u].lazy1,(ll)m+1);
}
if(tr[u].lazy2){
for(int i=0;i<=m;i++)
tr[u<<1].f[i]=(ll)tr[u<<1].g[i]*tr[u].lazy2,tr[u<<1|1].f[i]=(ll)tr[u<<1|1].g[i]*tr[u].lazy2;
tr[u<<1].lazy2=tr[u<<1|1].lazy2=tr[u].lazy2;
}
tr[u].lazy1=1;tr[u].lazy2=0;
}