@[sz_mane](/user/743373) 复杂度显然不对,不是常数的问题,对 vector 做 insert 操作的最坏时间复杂度大约是 $O(len)$,$len$ 是 vector 的长度。
by icypenguin @ 2024-01-31 15:05:59
@[bj12z_jiasiyuan](/user/751881) 啊啊?写正解去了qwq
by Special_Tony @ 2024-01-31 15:09:01
@[sz_mane](/user/743373) 想偷懒,用 vector 不如用 pbds,写的快跑的也快。
by August_Light @ 2024-01-31 15:13:45
@[August_Light](/user/589916) 蒟蒻没听说过qwq
by Special_Tony @ 2024-01-31 15:17:01
@[sz_mane](/user/743373) pbds AC 代码
```cpp
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 2e5 + 5;
struct SBT {
tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> tr;
int cnt = 0;
void ins(int k) {
tr.insert({k, ++cnt});
}
int kth(int x) {
return tr.find_by_order(x - 1)->first;
}
};
SBT tr;
int m, n;
int a[MAXN], u[MAXN];
int main() { ios::sync_with_stdio(0); cin.tie(0);
cin >> m >> n;
for (int i = 1; i <= m; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> u[i];
int ptr = 1, cnt = 0;
for (int i = 1; i <= m; i++) {
tr.ins(a[i]);
while (u[ptr] == i) {
ptr++;
cout << tr.kth(++cnt) << '\n';
}
}
return 0;
}
```
关于 pbds,平衡树模板题题解区应该有。
by August_Light @ 2024-01-31 15:18:48
@[sz_mane](/user/743373) 平板电视是自带的函数平衡树捏,所以复杂度是对的
by Hoks @ 2024-01-31 15:29:10