1<=n<=1e6,1<=m<=1e5,C/C++ 1秒,其他语言2秒,这样写会爆吗
时间: 2023-11-01 18:44:09 浏览: 44
根据题目给出的限制条件,n最大为1e6,m最大为1e5。每次操作都需要对序列a进行排序,而排序的时间复杂度为O(nlogn)。所以,每次操作的时间复杂度为O(nlogn)。
在最坏情况下,m次操作的时间复杂度为O(m * nlogn)。对于C/C++语言,1秒的时间限制是可以接受的。但对于其他语言,2秒的时间限制可能会超过限制。
为了优化时间复杂度,我们可以使用一种数据结构来维护序列a的有序性,例如平衡二叉搜索树(如红黑树)或堆结构。这样,每次操作的时间复杂度可以降低到O(logn),从而更好地满足时间限制。
以下是使用红黑树(C++中的set容器)进行优化的代码示例:
```cpp
#include <iostream>
#include <set>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
multiset<int> a;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
a.insert(num);
}
for (int i = 0; i < m; i++) {
int p, x;
cin >> p >> x;
auto it = a.find(*next(a.begin(), p));
a.erase(it);
a.insert(x);
auto median_it = next(a.begin(), n / 2);
cout << *median_it << endl;
}
return 0;
}
```
这段代码使用multiset容器来维护有序性。在每次操作中,我们先找到要修改的元素,并将其从multiset中删除,然后插入新的元素。最后,我们找到新的中位数并输出。
这样,每次操作的时间复杂度降低到了O(logn),更好地满足时间限制。
请注意,上述代码仍然没有对输入进行验证,如果需要对输入进行验证,请根据题目要求进行适当的修改。