RT，这玩意儿理论上是 $O(n)$ 的，但实际表现非常好。

例如下面这份代码在 P3850 [TJOI2007]书架 的表现就特别好，在极限数据下也能做到 $1.1s$ 跑完，总时间甚至吊打一些平衡树。

#include <bits/stdc++.h>
#define rep1(i, l, r) for (register int i(l); i <= r; ++i)
#define rep2(i, l, r) for (register int i(l); i >= r; --i)
using namespace std;
const int Buffer_Size = 1 << 10;
namespace {
	char buffer[Buffer_Size], *ihead = buffer + Buffer_Size, *itail = ihead;
	inline char Next_Char() {
		if (ihead == itail) fread(buffer, 1, Buffer_Size, stdin), ihead = buffer;
		return *ihead++;
	}
	template <typename T>
	inline void read(T &x) {
		x = 0; char ch = Next_Char(); T f = 1;
		while (!isdigit(ch)) f -= (ch == '-') << 1, ch = Next_Char();
		while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = Next_Char();
		x *= f;
	}
	template <typename T, typename ...L> inline void read(T &x, L &...y) {read(x), read(y...);}
	inline void readstr(string &s) {
		s = ""; char ch = Next_Char();
		while (ch == ' ' || ch == '\n') ch = Next_Char();
		while (ch ^ ' ' && ch ^ '\n') s += ch, ch = Next_Char();
	}
}
const int N = 1e5 + 1e3 + 5;
vector <int> l; string book[N]; 
int n, tot, m, q;
signed main(void) {
	freopen("hack.txt","r",stdin);
	freopen("faking.txt","w",stdout);
	ios::sync_with_stdio(false); cin >> n;
	rep1(i, 1, n) {
		string s; cin >> s;
		book[++tot] = s;
		l.push_back(tot);
	}
	cin >> m; rep1(i, 1, m) { int x; 
		string s; cin >> s >> x;
		book[++tot] = s;
		l.insert(l.begin() + x, tot);
	}
	cin >> q;
	while (q--) {
		int x; cin >> x;
		cout << book[l[x]] << endl;
	}
}

vector.insert() 操作的使用复杂度可以做到多少？它的底层实现如何？