前言

我写完这道题之后用这道题的代码去套 P5278 算术天才⑨与等差数列，然后卡了将近一周才过。

在此期间发现一大堆弱智错误，然而，这一大堆弱智错误可以通过这一道题目的数据，令我大开眼界，也充分说明了这一道题目的数据有多水。

正文

Hack 自己

做法是维护后继判重。

其他一小部分 Hash 做法后面有 Hack。

先来看一段代码：

以下一段代码是我在第一次 AC 本题时提交的代码，这一段是单点修改的部分，里面有两个严重错误。

if(tb==b[ta])
{
	continue;
}
pl=rrv[ta];
pr=nnt[ta];
rrv[pr]=pl;
nnt[pl]=pr;
if(b[i]<=n)
{
	nxt[b[i]].erase(nxt[b[i]].find(i));
}
qr=*nxt[tb].upper_bound(ta);
ql=rrv[qr];
nnt[ql]=rrv[qr]=ta;
nxt[tb].insert(ta);
b[ta]=tb;
if(pl!=0)
{
	inc(1,pl,b[pl]);
}
if(ql!=0)
{
	inc(1,ql,b[ql]);
}
inc(1,ta,b[ta]);

完整代码。

$rrv_p$ 指向最大的，小于 $p$ 的满足 $a_x=a_p$ 的下标 $x$，$nnt_p$ 指向最小的，大于 $p$ 的满足 $a_x=a_p$ 的下标 $x$，$nxt$ 是一个集合，$nxt_p$ 存储了所有满足 $a_x=p$ 的下标 $x$。

而在这一份代码中，$i$ 是操作次数。

每一次 $a_{ta}\leftarrow tb$ 的操作在正确的情况下都会修改 $rrv_{ta},nnt_{ta},nxt_{a_{ta}},nxt_{tb}$ 的状态，对吧？

这份代码并没有这么做，但是取得了 AC。

让我们看看这份代码的问题有多弱智：

1. 删除 nxt 部分

nxt[b[i]].erase(nxt[b[i]].find(i));

修改 $nxt_{a_{ta}}$ 的状态写成了修改 $nxt_{a_{i}}$ 的状态都能通过？合着数据操作 $1$ 的 $x$ 与操作次数正相关？

Hack:

6 6
6 1 6 5 6 6
1 2 2
1 2 3
1 2 4
1 2 6
1 2 4
2 3 4

Answer:

damushen

Output:

yuanxing

2. 维护前后缀部分

不难发现这份代码并没有修改 $rrv_{ta},nnt_{ta}$，也就是修改完全不会维护 $ta$ 的后继位置。

Hack:

3 2
3 4 2
1 1 4
2 1 3

Answer:

yuanxing

Output:

damushen

---

而这两个很明显且严重的错误都没有被这道题的数据 Hack 掉，而在 P5278 算术天才⑨与等差数列 中有两个数据点都 Hack 了这两个错误。

Hack 别人

我看到讨论区一种 Hash 做法如下：

维护区间和，区间乘积，区间最大最小值。

Hack:

5 1
0 2 2 2 4
2 1 5

Answer:

yuanxing

Output:

damushen

另外一种做法在题解区很常见：

维护区间和，区间平方和，区间最大最小值。

Hack:

9 1
1 9 3 4 4 6 6 3 9
2 1 9

Answer:

yuanxing

Output:

damushen

补充：我惊喜的发现这一个 Hack 同样可以 Hack 掉维护区间平方和，区间异或和，区间和的题解。

---

这两个 Hack 可以 Hack 掉以下题解：

• https://www.luogu.com.cn/article/kjip8mf0（区间平方和）
• https://www.luogu.com.cn/article/4ovxgwai（区间平方和，异或和）
• https://www.luogu.com.cn/article/yeizdesh（区间平方和）
• https://www.luogu.com.cn/article/v5s1vhlp（区间平方和）

上述数据不能 Hack 掉一篇离散化的题解，但是加强后的 Hack 数据可以 Hack 掉离散化的题解。

Hack:

18 1
1 9 3 4 4 6 6 3 9 1 2 3 4 5 6 7 8 9
2 1 9

Answer:

yuanxing

Output:

damushen

被 Hack 掉的题解：

• https://www.luogu.com.cn/article/9r57ifo9（区间平方和，离散化）

希望出题人加强数据，添加 Hack，以及将这道题降蓝。

以上。