\(\text{Solution}\)

涉及到插入，分块需要动态维护块内的元素及相对位置

于是妙用 \(\text{vector}\)

学到了 \(insert\) 操作，在某个迭代器前插入元素

这样我们对元数列分块，块长 \(\sqrt n\)

每个块用 \(\text{vector}\) 维护

插入时一块一块地找到合适块的合适位置，用 \(insert\) 插入容器（复杂度与插入位置到末元素长度线性相关）

\(\text{Solution}\)

#include <cstdio>

#include <vector>

#include <cmath>

#define re register

using namespace std;

const int N = 1e5 + 5;

int n, a[N], st[N], ed[N], id[N];

vector<int> Q[N];

inline void prepare()

{

	int num = sqrt(n);

	for(re int i = 1; i <= num; i++)

	{

		st[i] = ed[i - 1] + 1, ed[i] = (i == num ? n : ed[i - 1] + n / num);

		for(re int j = st[i]; j <= ed[i]; j++) id[j] = i;

	}

	for(re int i = 1; i <= n; i++) Q[id[i]].push_back(a[i]);

}

inline void Insert(int x, int v)

{

	int cur = 0, p = 0;

	while (cur < x) cur += Q[++p].size();

	Q[p].insert(Q[p].begin() + Q[p].size() - cur + x - 1, v);

}

inline int Query(int x)

{

	int cur = 0, p = 0;

	while (cur < x) cur += Q[++p].size();

	return Q[p][Q[p].size() - cur + x - 1];

}

int main()

{

	scanf("%d", &n);

	for(re int i = 1; i <= n; i++) scanf("%d", &a[i]);

	prepare();

	for(re int i = 1, op, l, r, c; i <= n; i++)

	{

		scanf("%d%d%d%d", &op, &l, &r, &c);

		if (!op) Insert(l, r);

		else printf("%d\n", Query(r));

	}

}

巴特西

LOJ 数列分块入门 6

\(\text{Solution}\)

\(\text{Solution}\)

最新文章

热门文章