关于懒标记下传顺序问题

P2572 [SCOI2010] 序列操作

焚魂 @ 2024-12-19 21:22:17

在我的代码里pushdown操作是先下传了翻转操作的懒标记再下传覆盖操作的懒标记,这样是正确的,如果反过来就只有10pts。

然而我看题解中似乎是先下传覆盖的懒标记再下传翻转的,这是为什么呢?

此外,这种懒标记之间互相有影响的情况下,下传的顺序到底应该怎么考虑?

我的pushdown:

void pushdown(int k,int l,int r,int mid) {
    while(rev[k]) {                         //翻转
        Rev(k*2,l,mid);
        Rev(k*2+1,mid+1,r);
        rev[k]--;
    }
    if(mod[k] != -1) {                      //覆盖
        Mod(k*2,l,mid,mod[k]);
        Mod(k*2+1,mid+1,r,mod[k]);
    }
    mod[k] = -1;
    rev[k] = 0;
}

by TH911 @ 2024-12-21 15:31:30

@焚魂下传顺序其实谁先谁后都无所谓,重要的是要分析清楚顺序对值的影响

比如我在这个帖子中说的,推平(覆盖)后不应当再次翻转,这就是因为之前翻转后已经被推平,因此再次翻转就会导致错误


|