进食后人:如果你过 Hack 和 讨论区数据且 10 分

P2572 [SCOI2010] 序列操作

CLydq @ 2024-12-12 14:57:04

我调这东西调了三天

如果你和我一样:

  1. 下传懒标记的时候先传区间赋值标记再传区间覆盖标记
  2. 翻转时不翻转区间赋值标记

那么请注意,你在下传标记 pushdown 里或者 update 里更新的时候不要删除你的区间赋值标记。

我的 node 定义:

struct node {
  int l, r, sum, change, tl, tr, sl, sr, mx, len, mn, flip;
} t[N << 2];

我 10 pts Code(使用 node 结构体中 swap 函数进行节点翻转):

inline void swap() {
  std::swap(mx, mn);// 交换最多 0/1 个数
  tl ^= 1, tr ^= 1;// 更改左右端点信息
  sum = len - sum;// 更改区间 1 个数
  flip ^= 1;// 更改翻转懒标记
  change=0;// 更改赋值懒标记
}

但是最后一行是错误的,改为:

inline void swap() {
  std::swap(mx, mn);
  tl ^= 1, tr ^= 1;
  sum = len - sum;
  flip ^= 1;
}

10 pts -> 100 pts.

WA TIME

AC TIME

这种怎么通过数据判断:

构造一个数据,使得存在两次修改连续(中间不含任何会对这个区间进行懒标记下方的操作),有相交区间且相交区间使得至少一个节点在两次修改中均被操作。

两次操作前一次为 0~1 中的任意一个,后一个为 2

简短数据:

in:

5 3
0 1 1 0 0
1 0 4
2 0 4
3 2 4

ans:

0

此错误对应的 out:

2

by CLydq @ 2024-12-12 17:19:51

这个类型的错误(懒标记覆盖)有个判法:

如果你每次操作后强制查询每个点但不输出查询值

然后就可以 WA->AC 的话你多半是懒标记更新错误了。


|