A

算法一：（）

暴力修改求逆序对即可。

时间复杂度 。

期望得分 40pts。

算法二：（保证对于任意操作都有 ）

发现所有操作都变成了交换相邻两个数。

容易证明，如果交换相邻的两个数，那么逆序对的奇偶性就会改变。

考虑这两个数之外的所有数与他们的相对位置都不变。

因为排列中没有两个数是相同的，这若原来是逆序对，那么交换后就变成了一对逆序对，反之亦然。

故此结论得证。

那么就可以直接维护了。

时间复杂度 。

期望得分 10pts，结合算法一可以拿到 50pts。

算法三：（保证输入中仅存在操作 1）

显然交换两个数 可以通过 次交换相邻两个数得到。

通过算法二可以知道交换相邻两个数奇偶性会改变。

又因为 显然是个奇数。

所以交换任意两个数奇偶性就会改变。

最开始求一遍逆序对即可，对应的模拟即可。

时间复杂度 。

期望得分 10pts，结合算法二可以拿到 60pts。

算法四：

可以发现所有操作都可以通过若干次交换得到。

通过算法三可以知道交换一次奇偶性就会改变。

相应的处理即可。

时间复杂度 。

期望得分 100pts。

B

Subtask 1

爆搜然后模拟。

Subtask 2

考虑什么时候会算错。

对于 位置，当它与后面的 位置交换时， 是交换前 中的最小值，。

因此，如果 中所有数都不相同，那么交换后逆序对总数只会减少 ，是算对的，也就是说排列能算对。

进一步可以发现，只要 中不存在与 相同的数，逆序对数量就只会减少 ，反之肯定会少算。具体地，大于 的数与 的贡献不会变，等于 的数原先与 能构成逆序对，现在全没了。

那么结论就出来了，如果存在 满足 就会少算。

有人可能会提出疑意：如果 在之前就被换到前面去了呢？

这是没有关系的，因为换过来的只可能是更大的数。所以 或 其中的一个肯定在某次越过中间的那个与后面更大的数交换。

把模拟换成 判断即可通过该档部分分。

Subtask 3

看到数据范围，想到状压。

令 表示到第 个位置，填过的数的集合为 ，出现过至少两次的最大的数为 。

转移枚举下一位填什么即可，时间复杂度 。

Subtask 4

给一些奇怪的做法。

Subtask 5

考虑从大到小填。

枚举最后一位填的数 ，于是前面所有大于 的数最多只能填一次。

那就枚举大于 的数填了 个，用组合数计算。发现当前填的数对剩下的位置没有影响。

于是原问题转化成了一个子问题，具体地，令 表示 个位置可以填 的方案数：

预处理阶乘和逆元就做完了，注意初始化 ，用于转移到所有初始状态。

时间复杂度 。

Subtask 6

观察到组合数很难优化，考虑换种方式填数。

不妨从小到大填，这样只有一个数可以不填在末尾。

令 表示 填了 个位置的方案数，枚举 这个数填几次：

和

时间复杂度 。

Subtask 7

发现对于同一个 可以前缀和优化，然后再用滚动数组优化空间即可通过。

时间复杂度 。

C

对于 的数据

怎么做都可以吧

对于 的数据

对于每个位置维护前 大的数，在扫的过程中同时维护这前 大的数。

时间复杂度 。

对于没有 操作

直接在线段树上对于每个区间维护前 大值即可。

对于 操作

所有数都是一直变大，懒标记处理相对简单。

对于 操作

等同于区间最大值。

对于 的数据

也是在区间上维护前 大数，但是在维护懒标记的时候不能只记录当前的加标记，还要同时记录这个懒标记上的那些操作所构成的历史加标记中的前 大值，而这些标记与当前区间中的前 大值合并后可能可以得到新的历史前 大值。直接暴力合并的复杂度是 的，并不能被接受。于是可以转化为一个相对简单的问题：给出两个有序序列 ，要在 中各选一个数，需要求出前 大的数。先把 扔到堆中（ 单调下降），每次取出堆顶的值，如果堆顶的值为 ，那么就把 扔到堆中，这样可以保证复杂度为 。可能需要一定的常数优化。

时间复杂度 。