介绍

这次的 NOI Online 可以说是非常难了，可以说入门组的难度已经和提高组持平。不过提高组的三道题都是很有技术含量的，需要长时间的思考才能得出正解，这也体现了提高组应有的风格。

下面我们还是按照入门组研究题目的方法，硬干一下提高组。

由于题面比入门组更简练，所以每道题会加一个“举例/说明”。

T1.序列

题面：
小 D 有一个长度为 $n$ 的整数序列 $a_{1,...,n}$，她想通过若干次操作把它变成序列 $b_i$。

小 D 有 $m$ 种可选的操作，第 $i$ 种操作可使用三元组 $(t_i,u_i,v_i)$ 描述：若 $t_i=1$，则她可以使 $a_{u_i}$ 与 $a_{v_i}$ 都加一或都减一；若 $t_i=2$，则她可以使 $a_{u_i}$ 减一、$a_{v_i}$ 加一，或是 $a_{u_i}$ 加一、$a_{v_i}$ 减一，因此当 $u_i=v_i$ 时，这种操作相当于没有操作。

小 D 可以以任意顺序执行操作，且每种操作都可进行无限次。现在给定序列与所有操作，请你帮她判断是否存在一种方案能将 $a_i$ 变为 $b_i$。题目保证两个序列长度都为 $n$。若方案存在请输出 YES，否则输出 NO。

$n,m\le 10^5$，$a_i,b_i\le 10^9$。

举例/说明：

如果 $a=\{0,0,0\},b=\{1,0,-1\}$，且有操作 1 1 2 和 1 2 3，则可以使 $a_1,a_2$ 同时增加 $1$，让 $a_2,a_3$ 同时减少 $1$ 来达到要求。

题目不保证没有重复的操作，也不保证 $u_i$ 和 $v_i$ 的任何关系。

解答：

$\texttt{Solution 1}$

$\text{60 pts}$

乍一看这道题好像没有太多的思路，但是这道题给了我们充足的部分分。也就是说，$n=2$ 的情况占了 $60$ 分。

注意到不论是操作一还是操作二，所有数的和的奇偶性都是不变的。所以说我们先判断以下 $a_1+a_2$ 和 $b_1+b_2$ 是否模 2 同余，若否直接输出 NO 即可。

接下来，我们判断一下操作：

1）如果存在操作 1 1 2：

如果没有其它操作了，则判断 $b_1-a_1$ 与 $b_2-a_2$ 是否相等。相等则输出 YES，否则输出 NO。

如果还有操作 2 1 2，则输出 YES。

如果还有操作 1 1 1 或者 1 2 2，输出 YES。

2）如果不存在操作 1 1 2，且存在操作 2 1 2：

如果没有其他操作了，则判断 $b_1-a_1$ 与 $a_2-b_2$ 是否相等。相等则输出 YES，否则输出 NO。

如果还有操作 1 1 1 或 1 2 2，则输出 YES。

3）如果不存在操作 1 1 2 和 2 1 2：

如果存在操作 1 1 1且 $a_1-b_1$ 是偶数或者 $a_1=b_1$，并且存在操作 1 2 2 且 $a_2-b_2$ 是偶数或者 $a_2=b_2$，输出 YES；

否则输出 NO。

对于 $n=2$ 的情况我们就分析完毕了，还是相对来说比较好想的。$60$ 分拿到手了。

$\texttt{Solution 2}$

$\text{80 pts}$

既然我们已经搞了 $60$ 分的部分分，我们再来看一看：如何能拿到更多的分数呢？

我们就注意到了：对于 $13-16$ 的测试点，$t_i=2$，也就是说只有操作二。这怎么做呢？容易知道，在只进行操作二的情况下，所有数的和是不变的。而且如果 $u,v$ 之间可以进行二操作，则它们的值就可以互相转换。

所以说就不难想到解法了：我们将 $n$ 个数看作 $n$ 个点，一个二操作相当于一条边，这就构成了一个图。对于这个图，我们可以用 $O(n)$ 的效率寻找连通块。对于每个连通块，它们之间的值都可以互相转换，而对于不在一个连通块的两个点，它们之间就没有联系。所以说我们分别判断每个连通块是否一共需要增加的数为 $0$，如果所有连通块都满足这个性质，就输出 YES；否则输出 NO。

时间复杂度是一维的，足够通过这道题。

回顾一下这种方法，其实我们就将每个连通块看作一个点了，而且这些点之间没有连边了。这就相当于没有操作了，只需要判断每个点的 $a$ 的和 与 $b$ 的和是否相等就行。

$\texttt{Solution 3}$

$\text{100 pts}$

好了，根据上一步的思路，我们对操作二已经有新的看法了。那么我们对于整体的情况也做这样的操作，这样的话就相当于没有操作二了。比如下图，红色的边表示操作二，蓝色边表示操作一：

那么就可以将点 $1,6$ 合并为新点 $1$，将点 $2,3,4,5$ 合并为新点 $2$，则如下图：

好的，现在图中只有操作一了，然后怎么办呢？（以下简称“操作一”为“操作”）

我们考虑如果 $a_x$ 与 $a_y$ 之间有操作，$a_y$ 与 $a_z$ 之间有操作，那么可以将 $a_x$ 和 $a_y$ 增加 $1$，$a_y$ 和 $a_z$ 减少 $1$，那么这样的效果就相当于 $a_x$ 和 $a_z$ 有操作二。所以，对于任意两个点，如果它们之间有长度为 $2$ 的路径，则这两个点之间就有操作二。所以说我们可以再连一次边，最后再进行一次合并点的操作，就相当于彻底消除了操作二。

如何找出这样的点对呢？很简单，枚举每一个点，对于它连接的点任意选出两个都是满足要求的点对。

这时候你可能会问：因为每个满足要求的点对都要进行连边，那么不就是 $O(n^2)$ 的效率了吗？其实不是这样的，你可以用并查集来解决问题，对于每个点连接的点，都和它上一个枚举的点进行合并即可。时间复杂度降为 $O(n+m)$。

再进行缩点之后，图又满足什么性质呢？因为每个点连接的点都被合并成一个点了，所以对于每个点，它的出度不大于 1。这样就更简单了，如果此时还存在非自环操作，那么就直接判断连接的两个点：

• 如果两个点都没有自环，则判断它们需要增加的值是否相等，不相等直接输出 NO；
• 如果两个点有自环，那么判断它们需要增加的值是否奇偶性相等，不相等直接输出 NO。

如果枚举完毕后仍未输出 NO，输出 YES。

到此，我们顺利地解决了第一题。