#include <bits/stdc++.h> #define int long long using namespace std; using LL = long long; constexpr int mod = 1e9 + 7; constexpr int INF = 1e18 + 7; constexpr int N = 1e6 + 10; vector<int> zz_word_hint; int n, m, k; int a[N]; int f[N]; signed main() { cin >> n >> m; vector<int> b(n); for (int i = 1; i <= n; i++) { cin >> a[i]; b[i - 1] = a[i]; } sort(b.begin(), b.end()); k = n / 2; multiset<int, greater<int>> down(b.begin(), b.begin() + k); multiset<int> up(b.begin() + k, b.end()); while (m--) { int p, x; cin >> p >> x; if (a[p] > *down.begin()) { up.erase(up.find(a[p])); up.insert(x); a[p] = x; } else { down.erase(down.find(a[p])); down.insert(x); a[p] = x; } if (*down.begin() > *up.begin()) { int x1 = *down.begin(); int x2 = *up.begin(); up.erase(up.begin()); down.erase(down.begin()); up.insert(x1); down.insert(x2); } cout << *up.begin() << "\n"; } return 0; } 这个代码用到了什么算法？

这段代码使用了贪心算法和堆（multiset）数据结构。

在代码中，首先对数组a进行排序，然后将数组b划分为两个部分，分别存储了较大的一半数值和较小的一半数值。这里的划分依赖于n的值，即数组长度的一半。

然后，通过对down和up两个multiset进行操作，实现了每次替换数组中的元素，并保持down中的元素都小于等于up中的元素。具体操作是，如果要替换的元素大于down中的最大值，则在up中替换，并将该元素插入到down中；反之，如果要替换的元素小于等于down中的最大值，则在down中替换，并将该元素插入到up中。

在每次操作后，输出up中的最小值。

因此，这个代码使用了贪心策略来保持down和up两个集合的有序性，并使用multiset数据结构来维护集合的有序性和元素的插入和删除操作。