浅谈 vector 处理插入

· · 科技·工程

感谢 Nz 老师的拷打。

vector 的插入时间复杂度是 \mathcal O(n)，实际上它在很多题目中跑得飞快，可以撵过。

原理是什么？因为 vector 访问地址写得很优秀，所以常数是 \dfrac 1 8 左右的。

可以看一下这篇题解。

当然这个可能可以 Hack，欢迎大家 Hack，我也不想这个东西活着。

下面我们思考怎么 Hack 它。

首先插入在开头是最慢的，我们拉满。

然后我们看看效率，考虑以下代码：

#include<bits/stdc++.h>
#define LL int
using namespace std;
const LL N=;
vector<LL>v;
int main()
{
    for(int i=1;i<=N;i++)v.insert(v.begin(),1);
    return 0;
}
//RP++

首先考虑 \text{O2} 优化，符合赛场环境。

当 n=10^5，跑了 0.3\text{s}，long long 慢了一倍。

当 n=2\times 10^5，跑了 1.1\text{s}，long long 慢了一倍。

当 n=3\times 10^5，Luogu IDE 显示 TLE，本地测出 2.6\text{s}。

（测试以 Luogu IDE 为准）

所以到这里结论很明显了，如果一道题不依赖常数的做法（也就是不考虑 bitset 等），那么只需要考虑把 n 开到 2\times 10^5 或者 3\times 10^5 就能卡掉。

正经做法显然不会变得很慢。

不过，在此基础上，我们考虑 vector 在 n\leq 10^5 的环境下不失为一种很好的简短实现。

本人在模拟赛中写这个狠狠地 win 了，希望大家可以在分辨好数据规模的情况下，善用 vector，具体使用请熟悉自己校内 OJ 的数据规模。

最后我们思考有没有什么东西可以替代这个插入。

使用 FHQ Treap 等数据结构可以将插入做到 \mathcal O(n\log n)，这是好的。

如果懒得写，可以 rope 容器，时间复杂度是 \mathcal O(n\log n) 的。

这里原来写的是 \mathcal O(n\sqrt n)，感谢 robinyqc,HangHang 老师的指正。

如果有啥好的 STL 可以解决这个问题，欢迎大家分享一手，帮我偷懒。