@[日奈](/space/show?uid=164323)
$O(n)$吧，毕竟之后每个位置上的数的下标都要往后移一位。
比较快的原因可能是：
1. 数据水；
2. 实际上每次插入，前面的数的下标不用变。
by emptysetvvvv @ 2019-09-24 15:50:11
@[lg_emptyset](/space/show?uid=135658) 那应该是数据比较水吧
by 日奈 @ 2019-09-24 15:55:30
$O(n)$，但是常数非常非常小，所以过十万也不是不可能（讲道理这也不能说数据水了，毕竟这鬼东西常数是在太小了）
by 地狱小鬼366 @ 2019-09-24 16:19:40
vector.insert()跑1e5次在begin()处插入就是能过吧，至少我水平衡树还没有在1e5被卡过（hzw的0.5s时限分块除外）。
by Jason__Zhan @ 2019-09-24 16:33:56
数据不水也能过，vector利用的memcpy操作非常快，但比1e5更大的数据耗时就会急剧增高，在1e5内的数据操作都是堪比log级的速度
by 在想Peach @ 2019-11-14 15:49:54
@[日奈](/user/164323)
vector+insert，亲测以下数据本机只需要0.7s就可以跑完：
```
100000
100000 99999 99998 ... 2 1
```
如果是
```
100000
1 2 3 ... 99999 100000
```
甚至只需要0.2s就可以跑完
by 林聪 @ 2021-02-24 19:33:59
[P4309 [TJOI2013]最长上升子序列](https://www.luogu.com.cn/blog/_post/57557)
Code 2 极限全 0 数据洛谷跑 332 ms
by lcyxds @ 2021-03-15 09:34:05
```cpp
#include <vector>
using namespace std;
int main() {
vector<char> a;
for (register int i = 0; i < 837500; i++) a.insert(a.begin(), '\0');
}
```
这玩意跑5秒整你敢信
by lcyxds @ 2021-03-15 09:47:15
n方过八十万（确信）
by lcyxds @ 2021-03-15 09:47:52