如果你 only AC on test 11,可以看看你的区间改值(Cover 操作)懒标记逻辑有没有写对,你必须得把处理的边界整个子树清空:
WA Code:
inline void change(int p,int l,int r,int v){
if (l<=t[p].l&&r>=t[p].r){
t[p].add=0;
t[p].ma=v;
return ;
}pushdown(p);
int mid=t[p].l+t[p].r>>1;
if (l<=mid) change(p<<1,l,r,v);
if (r>mid) change(p<<1|1,l,r,v);
t[p].ma=max(t[p<<1].ma,t[p<<1|1].ma);
}
AC Code:
inline void clear(int p,int v){
t[p].add=0;
t[p].ma=v;
if (t[p].l==t[p].r) return ;
int mid=t[p].l+t[p].r>>1;
clear(p<<1,v);
clear(p<<1|1,v);
}
inline void change(int p,int l,int r,int v){
if (l<=t[p].l&&r>=t[p].r){
clear(p,v);
return ;
}pushdown(p);
int mid=t[p].l+t[p].r>>1;
if (l<=mid) change(p<<1,l,r,v);
if (r>mid) change(p<<1|1,l,r,v);
t[p].ma=max(t[p<<1].ma,t[p<<1|1].ma);
}