冒泡排序 题目描述 冒泡排序是一种非常常见且简单的排序算法。假设比较两个元素的时间为 O ( 1 ) O(1)，则冒泡排序可以以 O ( n 2 ) O(n 2 ) 的时间复杂度完成长度为 n n 的数组的排序。不妨假设这 n n 个数字分别存储在 a 1 , a 2 , … , a n a 1 ​ ,a 2 ​ ,…,a n ​ 之中，则如下伪代码给出了冒泡排序算法的一种最简单的实现方式：

输入：一个长度为 n 的数组 a[1...n] 输出：a 排序后的结果。 for i = 1 to n do for j = 1 to n - 1 do if (a[j] > a[j + 1]) 交换 a[j] 与 a[j + 1] 的值 冒泡排序的交换次数被定义为上述排序过程中，交换操作的执行次数。

现在有个长度为 n n 的数组 a a，数组下标从 1 1 开始。需要支持数组 a a 上的 q q 次操作，操作共两种，参数分别如下：

1 v：这是第一种操作，会在 a a 数组的末尾添加一个新元素 v v，也就是让 a a 数组的长度 n n 增加 1 1，并且让新的 a n a n ​ 的值设置为 v v。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。

2 x v：每次操作包含两个参数 x x 和 v v，表示询问将 a a 的第 x x 个元素（也就是 a x a x ​ ）修改为 v v 的情况下，数组 a a 执行冒泡排序的交换次数。注意这种操作修改元素与排序的效果均不会保留，不会影响后续的操作。

输入格式 输入的第一行，包括两个整数 n n 和 q q。

输入的第二行，包括 n n 个整数，表示 a i a i ​ 。

接下来 q q 行，每行 2 ∼ 3 2∼3 个整数，表示一次操作，操作格式见【题目描述】。

输出格式 对于每一次类型为 2 2 的操作，输出一行一个正整数表示答案。

样例 #1 样例输入 #1 1 5 1 1 2 1 3 1 4 1 5 2 1 6 样例输出 #1 4 样例输入 #2 1 9 1 2 1 100 1 2 2 2 1 1 3 2 3 1 1 4 2 4 1 1 5 2 5 1 样例输出 #2 0 0 1 2 3 样例输入 #3 5 10 0 0 0 0 0 1 5 2 1 1 1 4 2 2 2 1 3 2 3 3 1 2 2 4 4 1 1 2 5 5 样例输出 #3 4 4 5 9 14 样例输入 #4 5 11 1 2 3 4 5 1 5 2 1 6 1 4 2 2 7 1 3 2 3 8 1 2 2 4 9 1 1 2 5 5 2 5 10 样例输出 #4 5 7 11 15 20 21 提示 本题共 2 0 20 个测试点。

测试点 1 ∼ 2 1∼2 满足： n

2 , 1 ≤ q ≤ 3 0 0 n=2,1≤q≤300，没有类型为 1 1 的操作；

测试点 3 ∼ 4 3∼4 满足： 1 ≤ n , q ≤ 3 0 0 1≤n,q≤300，没有类型为 1 1 的操作；

测试点 5 ∼ 8 5∼8 满足： 1 ≤ n , q ≤ 3 0 0 1≤n,q≤300；

测试点 9 ∼ 1 2 9∼12 满足： 1 ≤ n , q ≤ 5 × 1 0 3 1≤n,q≤5×10 3 ；

测试点 1 3 ∼ 1 6 13∼16 满足： 0 ≤ a i , v ≤ 1 0≤a i ​ ,v≤1；

对于所有测试点均满足： 1 ≤ n ≤ 3 × 1 0 5 , 1 ≤ q ≤ 3 × 1 0 5 , 0 ≤ a i , v ≤ 1 0 2 , 1 ≤ x ≤ n 1≤n≤3×10 5 ,1≤q≤3×10 5 ,0≤a i ​ ,v≤10 2 ,1≤x≤n。```cpp #include <bits/stdc++.h> using namespace std; vectorv; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n,q; cin >> n >> q; int c=1e9; v.push_back(c); for(int i=1;i<=n;i++){ int a; cin >> a; v.push_back(a); } int op; for(int i=1;i<=q;i++){ cin >> op; if(op==1){ int a; cin >> a; v.push_back(a); }else{ int x,vv; cin >> x >> vv; int ans=0; vectorb; for(int i=0;i<=v.size()-1;i++){ b.push_back(v[i]); } b[x]=vv; for(int i=1;i<=b.size()-1;i++){ bool nn=0; for(int j=1;j<=b.size()-2;j++){ if(b[j]>b[j+1]){ nn=1; swap(b[j],b[j+1]); ans++; } } if(nn==0){ break; } } cout << ans << '\n'; } } return 0; }

调到O（n）谢谢