题解：AT_abc441_g [ABC441G] Takoyaki and Flip

anll · 2026-01-20 10:23:01 · 题解

分块做法，赛时没调出来。

对于每个位置，维护：

• 当前位置章鱼烧的个数 ct。
• 当前位置被翻的次数 cl。

对于每块，维护：

• 整块加的 tag tt。
• 整块翻转的 tag tl（也是翻转次数）。
• 当前块正面的数量 nm。
• 当前块的最大值 mx。

当散块操作或查询之前先重构（计算单点的 cl,ct 和整块的 nm），操作或查询之后重算 mx。

重构时：

• 对新的 cl 是偶数（当前是上面）的位置，ct 这么更新：
  • 如果 tl=0 要加上 tt。
  • 如果 tl\ne0 要赋值成 tt。
• 对新的 cl 是奇数的位置要赋值成 0。

void rbld(int x) {
    if(!tl[x]) {
        nm[x]=0;
        for(int i=L[x];i<=R[x];i++) {
            if(!(cl[i]&1)) ct[i]+=tt[x],nm[x]++;
            else ct[i]=0;
        }
        tt[x]=0;
        return;
    }
    nm[x]=0;
    for(int i=L[x];i<=R[x];i++) {
        cl[i]+=tl[x];
        if(!(cl[i]&1)) ct[i]=tt[x],nm[x]++;
        else ct[i]=0;
    }
    tt[x]=tl[x]=0;
}

整块操作直接打 tag 即可。

细节比较多，具体看代码。