CF1375C Element Extermination
题意：给定一个排列(a)，每次操作你可以选定一个(i)，满足(a_i < a_{i+1})，然后删除(a_i)或者(a_{i+1})。问最后能否使排列仅剩下数字1。(sum n leq 3 imes 10^5)。
题解：大胆猜一波结论：存在方案当且仅当：(a_1 < a_n)。事实也确实是这样。为什么呢？
考虑(a_1 >a_n)时，我们肯定不希望排列最后只剩下它们两个数，因此需要将(a_1)变小或将(a_n)变大。但无论我们怎么操作，(a_1)是不会降的，(a_n)也是不会升的（这里的(a_1)和(a_n)指的是序列首位的元素）。
CF1375D Replace by MEX
题意：给一个序列(A)，每次操作可以选定一个位置(p)，令(a_p=)这个序列的(mex)。你需要进行若干次操作，使得这个序列单调不降。操作次数不能超过(2n)。
(n leq 1000,a_i in [0,n])。
题解：为方便起见，我们将序列按(0)到(n-1)编号。考虑能否将序列还原为(0)到(n-1)的序列。
当序列的(mex)小于(n)时，我们令(p=mex)；否则，令(p)为任意一个(a_i eq i)的位置(i)。这样做，操作次数的上界为(1.5n)。下面是一个简单的证明：
考虑当(mex=n)时，整个序列是([0,n-1])的一个排列。我们做完一次操作后，序列的(mex)就变为了(a_p)，令(a_{a_p}=a_p)后，序列的(mex)又变成了原来的(a_{a_p})。那么要使(mex=n)的出现次数最多，显然形如(0,2,1,4,3,cdots)这样有很多"2-cycle"的排列是最毒瘤的，每做2次，序列的(mex)就会变成(n)。
直接模拟即可。
时间复杂度：(O(n^2))。
CF1375E Inversion SwapSort
题意：给定一个序列(A)，长度为(n)。我们记录下序列所有逆序对的下标(u_i,v_i)。你需要给所有的({u_i,v_i})指定一个顺序，每次交换(a_{u_i},a_{v_i})，使得所有操作完成后的序列单调不降。
(n leq 1000,a_i leq 10^9)。
题解：先考虑对于一个排列如何求解。设(p_{a_i}=i)。
我们尝试从后往前逐位确定答案。考虑当前序列的最后一位(n)，它想成为(n)，那么(a_n)必须在与(n)有关的最后一次操作中被换到位置(n)。所以，我们只需要依次进行如下的操作：((p_{a_{i+1}},n))，((p_{a_{i+2}},n))，(cdots)，((p_{n},n))即可。剩下的问题就是一个(n-1)的子问题了。
那么对于序列的情况也就很简单了：将所有元素按(a_i)为第一关键字，(i)为第二关键字排序，化成排列的问题即可。
时间复杂度：(O(n^2))。
CF1375F Integer Game
题意：这是一道交互题。
有三堆石子，个数分别为(a,b,c)。游戏的规则如下：
- 先手每次给定一个数(k)，后手需要给这三堆石子的某一堆的个数加上(k)。
- 后手不能连续对同一堆石子进行操作。
- 当存在两堆石子个数相等时，先手胜；当回合数超过1000时，后手胜。
你可以自行决定当先手还是后手。
(a,b,c leq 10^9,k leq 10^{12})。
题解：考虑什么情况下后手无法操作：
- 设当前石子个数为(a,b,c)，且(a<b<c)，上一次操作的是(c)这堆石子。
- 那么当(a,b,c)形成等差数列时，后手就无法操作了。
因此，这是一个先手必胜的游戏。我们只需要构造一种方案，使它到达这种状态即可。
还是令(a<b<c)，那么我们先强制让操作后的那对石子个数最大。显然令(k=c-a)即可。
现在，上次操作的一定是(c)，那么我们稍微计算一下，令(k=2c-a-b)，就能让得到的(a,b,c)成为一个等差数列。并且由于(a+k>c)，所以操作的那堆石子在操作完成后一定是个数最多的。
CF1375G Tree Modification
题意：给定一棵(n)个点的树，一次操作，你可以选定三个点(a,b,c)，要求(a)与(b)相邻，(b)与(c)相邻，然后进行如下操作：
- 所有与(a)相邻的节点和(c)连边；
- 断掉连接(a)与其所有相邻节点的边；
- (a)与(c)连边。
你需要最小化操作次数，使得这棵树仅存在一个节点度数为(n-1)，其他节点的度数都为(1)。不需要输出方案。
(n leq 2 imes 10^5)。
题解：由于树无环，我们可以将其看做一个二分图，并将其黑白染色。那么目标状态显然是只有一个黑或白点。考虑一次操作对黑白点个数的影响。我们设(c)是黑色的。
对于所有与(a)相邻的节点及其子树内的点，颜色不变；只有节点(a)的颜色改变了。
因此，一次操作只会使黑或白点个数变化1。那么答案显然就是(min(cnt_{white},cnt_{black})-1)。
直接DFS一遍就好了。
CF1375H Set Merging
题意：给定一个长度为(n)的排列(a)，初始的时候存在(n)个集合，第(i)个集合为{(a_i)}如果两个已经存在的集合(X,Y)满足 (X_{max}<Y_{min})，则可以添加一个新的集合(S=Xcup Y)，称这为一次合并操作。
你可以进行若干次合并，但是需要保证总的集合数量不超过(2.2 imes 10^6)。
现在有(q)个限制，每个限制包含一段区间[l,r]，需要保证操作完后的所有集合中存在至少一个集合等于{(a_i|iin [l,r])}。
(n leq 2^{12},qleq 2^{16})。
题解：发现(nsqrt{q} approx 2.2 imes 10^6)，我们考虑往分块的角度想。不愧是Ynoi
我们将值域([1,n])分块。设块大小为(S)。发现一个很优秀的性质：如果我们把([1,n])按值域划分成(frac{n}{S})个子序列，那么对于每个询问([l,r])，我们也将其划分为(frac{n}{S})段，那么每一段都是序列([1,n])划分出来的对应的那个段的连续子序列。比如原序列为(5,3,1,8,9,7,2,4,6)，我们将其划分为{(3,1,2)}，{(5,4,6)}，{(8,9,7)}三段。那么对于询问([2,6])，我们只需要将其划分为{(3,1)}，{}，{(8,9,7)}三段。这三段都是原序列分出来的三个序列的连续子序列。一个块的连续子序列个数是(frac{S imes (S-1)}{2})，那么总个数就是(nsqrt{n})的。我们将这些连续子序列全都求出来，然后对于每个询问，直接merge它对应的这(frac{n}{S})个连续子序列就行了。
那么如何求出一个块内的所有连续子序列呢？我们考虑以权值大小来进行分治。假设我们要求出序列(5,3,1,8,9,7,2,4,6)的所有连续子序列，当前已经求出了(5,3,1,2,4)和(8,9,7,6)的所有连续子序列，合并时，由于这两个序列与原序列的关系依然是子序列的关系，那么我们就只需要类似归并排序那样做就行，只不过因为要求出所有的连续子序列，我们可以枚举整个序列的左右端点，把两个序列的元素的位置信息扔进两个vector里，查一下分别的前驱和后继，然后直接合并即可。比如我们现在要得到(1,8,9,7,2)这一段，我们就分别找出(1,2)和(8,9,7)这两个子序列，然后直接merge。
(cnt=O(nsqrt{q}))，时间复杂度大概是(O((n+q)sqrt{n}))。