CSP-J 2021测试源文件

#include <iostream> #include <cstdio> using namespace std; const int N = 10010; //p[i]表示排序后i位置的数在原数组p[i]位置 //np[i]表示原数组i位置的数在排序后的数组np[i] int a[N], p[N], np[N]; int n, q; //向前调整 void forward(int k) { for(int i = k; i > 1 && a[i] <= a[i - 1]; i --) { //如果相等，需要判断原来位置的前后关系，从而保证插入排序的稳定性，即原来在前的还是在前 if(a[i] == a[i - 1] && p[i] > p[i - 1]) continue; swap(a[i], a[i - 1]); np[p[i]] = i - 1; np[p[i - 1]] = i; swap(p[i], p[i - 1]); } } //向后调整 void backward(int k) { for(int i = k; i < n && a[i] >= a[i + 1]; i ++) { //如果相等，需要判断原来位置的前后关系，从而保证插入排序的稳定性，即原来在后面的还是在后面 if(a[i] == a[i + 1] && p[i] < p[i + 1]) continue; swap(a[i], a[i + 1]); np[p[i]] = i + 1; np[p[i + 1]] = i; swap(p[i], p[i + 1]); } } int main() { freopen("sort.in", "r", stdin); freopen("sort.out", "w", stdout); cin >> n >> q; for(int i = 1; i <= n; i ++) { scanf("%d", &a[i]); np[i] = p[i] = i; } //插入排序 for(int i = 2; i <= n; i ++) forward(i); while(q --) { int op, x, v; scanf("%d%d", &op, &x); if(op == 1) { scanf("%d", &v); int k = np[x]; a[k] = v; //更新后，向前或向后进行调整 forward(k); backward(k); } else printf("%d\n", np[x]); } }