T1

题意简述：给定一个序列 \(a\)，每次将 \(a\) 的第一个元素加入 \(b\) 的末尾然后翻转 \(b\)，求最后的 \(b\) 是什么。\(n\le 10^6\)。

考虑模拟一下这个过程，发现就是奇数次次向最后添加，偶数次次向开头添加，最后再翻转 \(n\bmod 2\) 次。

T2

题意简述：定义两点的距离为 \(|x_i-x_j|^3+|y_i-y_j|^3\)。现在给定 \(n\) 个点，保证坐标两两不同。接下来添加 \(q\) 条边，每条边连接 \(a,b\) 长度为 \(c\)。现在求初始状态和添加每条边后图的最小生成树。\(n\le 3000,q\le 5000,-50000\le x_i,y_i\le 50000\)，保证添加的边合法且不会构成自环。

首先发现带个 \(\log\) 复杂度会很危险。于是我们先使用朴素 \(prim\) 求出原图最小生成树并找出最小生成树上的边。接下来对于每条添加的边，用 \(bfs\) 找出两点间的边权的最大值，并看加上这条新边断掉这条最长的边是否更优，如果是就把原来的那条边替换掉，否则维持原状。这样做的复杂度是 \(O(n^2+nq)\)。

T3

题意简述：定义两个序列 \(a,b\) 的权值为 \(\displaystyle\sum_{i=1}^{n}(a_i-b_i)^2\)。现在可以任意次数交换 \(a\) 中的两个元素。求 \(a,b\) 的最小权值以及达到最小权值的最小交换次数。\(n<=3\times 10^5,1\le a_i，b_i\le 10^9\)，保证 \(a\) 中元素两两不同，\(b\) 中元素不同。

考虑一对 \((i,j)\) 满足 \(a_i>a_j\) 且 \(b_i<b_j\)，考虑交换前后的贡献分别为 \(a_i^2+b_i^2-2a_ib_i+a_j^2+b_j^2-2a_jb_j\)，\(a_i^2+b_j^2-2a_ib_j+a_j^2+b_i^2-2a_jb_i\)，做差得到：\(2a_i(b_j-b_i)-2a_j(b_j-b_i)=2(a_i-a_j)(b_j-b_i)>0\)，故交换后更优，于是把 \(a\) 按照 \(b\) 的顺序放置即可。接下来我们把要交换的数分成两类：一个是两个数放反，另一个是不满足第一类的。显然后一类的每次交换至多归位 \(1\) 个。于是我们按照顺序尝试交换，如果这个数正好跟交换对象是反的，那么交换了 \(2\) 个，显然优；否则每次归位了 \(1\) 个，达到了上界，也是优的。于是我们直接按顺序交换就是对的。