2025-6-15模拟测验
自我评价：Tang 完了。题解
题解中包含题面描述，但不包含大样例。
T1 怎么又是先增后减(why)
描述
青蛙又给了周欣一个长为 \(N\) 的正整数序列 \(A_i\)，周欣可以进行若干次操作，每次可以选择一个位置 \(i\)，满足 \(1 \leq i \leq N - 1\)，将 \(A_i\) 的值和 \(A_{i+1}\) 的值进行交换。
设经过这若干次操作后的序列为 \(B_i\)，那么需要存在一个整数 \(k \in \)，满足：
[*]区间 \(\) 构成的子序列 \(\) 是一个非严格单调递增的序列，即相邻两项允许相等，但是左边元素不能大于右边元素。
[*]区间 \(\) 构成的子序列 \(\) 是一个非严格单调递减的序列，即相邻两项允许相等，但是左边元素不能小于右边元素。
周欣想知道至少需要对序列进行多少次上述操作后，这个要求才能得以满足，他把这个问题交给了你来解决。
输入
第一行一个整数 \(N\)，表示序列长度。
第二行 \(N\) 个整数表示 \(A_1,A_2,\cdots,A_N\)。
输出
输出一个整数，表示答案，即最少的操作次数。
样例
共 \(3\) 组。
数据范围
对于 \(20\%\) 的数据，满足 \(N \leq 10\)。
对于 \(50\%\) 的数据，满足 \(N \leq 5000\)。
对于 \(100\%\) 的数据，满足 \(1 \leq N \leq 10^5, 1 \leq A_i \leq 10^5\)。
题解
我们令 \(x\) 为当前序列中最小的数字。
以样例 3 1 4 1 5 9 2 为例子，\(x=1\)（假设为第一个 \(1\)）。
我们知道，\(x\) 必须被移动到最左边或最右边。样例中，往左移动需要 \(1\) 步，但往右移动需要 \(4\) 步（不是 \(5\) 步，因为相同的 \(1\) 不需要交换）。
于是我们得到一个解题思路：
对于每个数，计算出左边严格比他大的有多少个，记为 \(l\)；再计算出右边严格比他大的有多少个，记为 \(r\)。然后将 \(ans\) 累加 \(\min(l,r)\) 即可。
暴力统计的复杂度为 \(\mathcal{O}(n^2)\)，可以得到 \(50\%\) 的分数。
使用树状数组优化，复杂度为 \(\mathcal{O}(n \log n)\)，可以得到 \(100\%\) 的分数。
#includeusing namespace std;inline int read(){ int x = 0, f = 1; char ch = getchar(); while(!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)){ x = (x
页:
[1]