NOI Online 提高组 Day1

A 序列

给出长度为$n$的序列$a$和$b$，有$m$个操作方式，表示为三元组形如$(t_i,u_i,v_i)$：

1. 若$t_i=1$，则可以使$a_{u_i}$和$a_{v_i}$同时加 1 或减 1（如果$u_i=v_i$，相当于把$a_{u_i}$加 2 或减 2）；
2. 若$t_i=2$，则可以使$a_{u_i}$和$a_{v_i}$一个加 1，一个减 1。

你可以使用每种方法无数次。问能否把$a$变成$b$（yes or no）。

$n,m\le 10^5,a_i,b_i\le 10^9,t_i\in\{1,2\},1\le u_i,v_i\le n$。

摘要：挖掘性质，缩点，判二分图。

设点权$c_i=b_i-a_i$，则我们的目标变成：让每个点点权变成$0$。

操作 2 可以改变点权，但点权和不变。

把操作当作连边。我们考虑操作 2 的边构成的连通块。那么我们在这个连通块上进行操作的时候，点权和是始终不变的。

因此我们把操作 2 的连通块缩点。剩下的就只有操作 1 的边。

由于两个操作 1 可以构成一个操作 2，因此对于新的图上，考虑操作 1 的边构成的连通块：

1. 如果是一个二分图，那么左部（右部）在点权和不变的情况下可以任意变换点权。因此要让左部和右部的点权都变成$0$，等价于，左部和右部的点权和变成$0$。由于操作 1 只能同加同减，因此等价于，坐标和右部点权和相等。
2. 如果不是二分图，那么我们可以把这个连通块点权和加 2 或者减 2。因此要把点权都变成$0$，等价于把点权和变成$0$，等价于，点权是$2$的倍数。

综上，缩点后 DFS 即可。时间复杂度$O(n\log_2n)$或者$O(n\alpha(n))$。

代码

B 冒泡排序

对$p$进行一次冒泡排序的伪代码为

$$\begin{array}{r|l} \hline 1 & \textbf{for }i=1\textbf{ to }n-1\\ 2 & \qquad \textbf{if }p_i>p_{i+1}\\ 3 & \qquad \qquad \text{swap}(p_i,p_{i+1}) \\ \hline \end{array}$$

给出一个排列$p$，有$m$次操作：

1. 交换$p_x$和$p_{x+1}$；
2. 询问当前排列经过$k$次冒泡排序后的逆序对数。

$n,m\le 10^5,1\le x<n,0\le k<2^{31}$。

摘要：挖掘性质，树状数组。

首先要发现冒泡排序的性质。

我们称二元组$(x,y)$满足$x<y,p_x>p_y$是关于$y$的逆序对，记其集合为$S_y$。

性质 1：进行一次冒泡排序，则$\forall y$，与$y$有关的逆序对数最多减少$1$个。

性质 2：进行一次冒泡排序，若存在$x(x<y)$使得$p_x>p_y$，与$y$有关的逆序对数一定减少$1$个。

推论：进行$k$次冒泡排序，对于任意$y\in[1,n]$，关于$y$的逆序对会减少$\min(|S_y|,k)$个。

因此我们维护$b_y=|S_y|$。则一次交换操作最多影响两个数的$b_y$。对于询问$k$，我们要求的就是

$$\sum_{i=1}^n\min(b_i,k)$$

使用几个树状数组维护即可。

时间复杂度$O((n+m)\log_2n)$。

代码

C 最小环

给定⻓度为$n$的序列$a_i$，我们将该序列视为⼀个⾸尾相邻的环，更具体地，对于下标为$i,j(i \le j)$的两个数$a_i,a_j$，它们的距离为$\min(j-i,i+n-j)$。

现在再给定$m$个整数$k_1,k_2,\cdots,k_m$，对每个$k_i$，你需要将上⾯的序列$a_i$重新排列，使得环上任意两个距离为$k_i$的数字的乘积之和最⼤（二元环的乘积之和要算成$a_1a_2+a_2a_1=2a_1a_2$）。求出最大的乘积之和。

$n,m\le 2\times 10^5,1\le a_i\le 10^5,k\le \frac{n}{2}$。

摘要：结论题。

考虑四个数$a,b,c,d$，交换$b,c$，则代价的变化是$ac+bc+bd-(ab+bc+cd)=(a-d)(c-b)$。

因此我们得到，当$[a\ge d]=[b\ge c]$时$ab+bc+cd$是最优的。

于是我们的最优方案一定满足，对于环上任意四个相邻的数$a,b,c,d$，$[a\ge d]=[b\ge c]$。

考虑$k=1$的情况。全排列打表发现：

1. 对于长度为$2x$的序列$c$，且满足$c_i\le c_{i+1}$，则最优方案（环）是$c_2,c_4,\cdots,c_{2x},c_{2x-1},c_{2x-3},\cdots,c_5,c_3,c_1$。
2. 对于长度为$2x+1$的序列且$c_i\le c_{i+1}$，最优方案是$c_2,c_4,\cdots,c_{2x},c_{2x+1},c_{2x-1},\cdots,c_5,c_3,c_1$。

另一方面，对于一次询问，我们把距离为$k$的点连边（这是真的环），则会构成$\gcd(n,k)$个真环，环长$L=\frac{n}{\gcd(n,k)}$。易证（可以通过交换证明，或者打表发现），用$a[1,L]$序列构造第一个真环，$a[L+1,2L]$构造第二个真环，$a[(x-1)L+1,xL]$构造第$x$个真环，这样的总和的最大的。真环的构造方法就是$k=1$的情况。

那么对于$n$的每个约数$d$计算$\gcd(n,k)=d$时的答案即可。

时间复杂度$O(n\sqrt{n}+m\log_2n)$。

代码