Kniqht @ 2023-09-03 19:40:41
小粉兔的题解里面这里是懒标记下传同时用懒标记更新子节点的信息，为什么顺序不会影响呢？
或者说跟代码都无关系了，就是为什么懒标记下传将一个区间都覆盖为0/1 和 将区间翻转(0变为1，1变为0) 的两个懒标记顺序无影响呢（同时还更新了子节点）？
如先覆盖为1再翻转(0变为1，1变为0) 0101->1111->0000
先翻转再覆盖 0101->1010->1111
这就不一样啊？
inline void P(int i,int typ){
d&t=dat[i];//dat就是线段树tr数组
if(typ==0) tg2[i]= 0, tg1[i]=0, t=d(0,len[i],0,len[i],0,len[i],0,len[i]);
if(typ==1) tg2[i]= 0, tg1[i]=1, t=d(len[i],0,len[i],0,len[i],0,len[i],0);
if(typ==2) tg2[i]^=1, swap(t.w,t.b), swap(t.lw,t.lb), swap(t.rw,t.rb), swap(t.mw,t.mb);
}
inline void pd(int i){
if(~tg1[i]) P(i<<1,tg1[i]), P(i<<1|1,tg1[i]);
if(tg2[i]) P(i<<1,2), P(i<<1|1,2);
tg1[i]=-1, tg2[i]=0;
}by FerventTemp0 @ 2023-09-03 19:41:46
因为从上往下更新，每次都能保证是旧信息被新信息更新……
线段树的懒标记是不用支持交换律的。
by Rosaya @ 2023-09-03 19:42:16
因为覆盖操作的时候把翻转标记强制清 0 了。
by Kniqht @ 2023-09-03 19:56:47
呃我好像有点明白了，似乎是我脑瘫了，我先思考一下。谢谢两位大佬
by Kniqht @ 2023-09-03 20:01:27
@FerventTempo 子节点本身的懒标记会被父节点传下来的覆盖没毛病，但是如果父节点传下来了两个懒标记，翻转和覆盖，那顺序不会有影响吗？
by Kniqht @ 2023-09-03 20:13:16
@Rosaya @ferventtempo
大佬们，比如我先将u节点的翻转tag标记上了，同时更新了u节点信息。然后另一次modify的时候我又标记了tag1让u节点中l~r都覆盖为1。之后理论上子节点也应该是这个顺序，但是下传的时候根据pushdown代码先覆盖了后翻转，就可能出现问题呀。
比如1010->0101->1111 和1010->1111->0000是不一样的啊
真的没太想明白，如能解惑感激不尽！
by Rosaya @ 2023-09-03 20:16:49
先区间翻转再覆盖为 1 等价于直接覆盖为 1 但是不翻转。
by Kniqht @ 2023-09-03 20:19:35
@Rosaya 但如果应该先覆盖后翻转呢
by FerventTemp0 @ 2023-09-03 20:23:13
@qi136 你可以学一下矩阵乘法，这个和那个类似。同时传两个叠一起的放下去和分开传下去是一样的。
by FerventTemp0 @ 2023-09-03 20:23:28
另外别一下艾特我好几次。
by Kniqht @ 2023-09-03 20:26:33
好的，我不@您了