上述算法时间复杂度过大，请优化

对于每次操作，我们使用了排序算法对序列进行排序，时间复杂度为O(nlogn)。这导致总体的时间复杂度为O(m * nlogn)，在n和m较大时可能会超过1秒的时间限制。

为了优化时间复杂度，我们可以使用一个平衡二叉搜索树（例如红黑树）来存储序列a。平衡二叉搜索树可以在O(logn)的时间内完成插入和删除操作，并且可以在O(1)的时间内获取中位数。

下面是优化后的代码：

#include <iostream>
#include <set>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::multiset<int> sorted_a(a.begin(), a.end());
    auto median_it = sorted_a.begin();
    std::advance(median_it, n / 2);

    std::cout << *median_it << std::endl;

    for (int i = 0; i < m; i++) {
        int p, x;
        std::cin >> p >> x;
        p--;

        sorted_a.erase(sorted_a.find(a[p]));
        sorted_a.insert(x);

        if (x < *median_it) {
            if (n % 2 == 0) {
                median_it--;
            }
        } else {
            if (n % 2 == 1) {
                median_it++;
            }
        }

        std::cout << *median_it << std::endl;
        a[p] = x;
    }

    return 0;
}

在优化后的代码中，我们使用了`multiset`来存储序列a，并使用迭代器`median_it`来指向中位数。在每次操作中，我们从`sorted_a`中删除原来的值，插入新的值，并根据新的值的大小调整`median_it`的位置。最后，输出`*median_it`作为中位数。

通过使用平衡二叉搜索树，我们将时间复杂度降低到O(mlogn)，能够在给定的时间限制内完成计算。

希望对你有帮助！如果还有其他问题，请随时提问。