问一个线段树最基础的问题(mx一枚

P2572 [SCOI2010] 序列操作

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 20:26:37

本质上就是有结合律但是没交换律的运算。


by Rosaya @ 2023-09-03 20:27:13

@qi136 先覆盖后翻转你就直接打上覆盖和翻转的标记不就行了吗。

任意一种操作序列最终都能表示成先覆盖后翻转(或不翻转)的方式,这样的话下传标记就是确定的顺序关系了。

你想想线段树模板的加法乘法,都是把他处理成先乘上一个数再加上一个数的操作。

这个题你甚至可以把赋值 0 当成乘 0,赋值 1 当成乘 0 再加 1,反转当成乘 -1 再加 1,你想想是不是完全一样的。


by Kniqht @ 2023-09-03 20:29:03

@Rosaya 草好像是这样的,我是什么傻逼啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊两位大佬都关注了感谢


by Kniqht @ 2023-09-03 20:29:35

所以高级运算(比如乘法相对于加法和覆盖相对于翻转)先运算就一定没问题


by _l_l_ @ 2023-09-05 13:12:55

@qi136 其实标记这个东西是说不清楚的,你写的时候先在纸上写好所有的转移与形式对了再写。


by Kniqht @ 2023-09-05 17:59:02

@_ll 嗯嗯,我现在明白了,感觉很巧妙


上一页 |