题解：P13981 数列分块入门 6

块状链表模版题......

具体就是对原序列分块，然后每个块都维护一个 vector，把这些整块连成一个链表。这样每次插入时从链表头一直往后找找到指定的块，然后插入到该块的 vector 里，这样 vector 的 insert 就被优化成了

O(\sqrt n)

插入。当插入后这个块的 vector 长度达到

2\sqrt n

时就把 vector 的后

\sqrt n

个元素提取出来放到一个新的块，然后把这个新块插到原来的块后面，由于每个块是链表连起来的所以插入复杂度

O(1)

，分裂复杂度是

O(\sqrt n)

，那么总的修改复杂度就是

O(\sqrt n)

。查询就是从头遍历每个块。时间复杂度

O(n\sqrt n)

。

CPP

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define pb push_back
typedef long long ll;
const int N = 3e5 + 10, B = 547;
vector<int> b[N];
int a[N], nxt[N], tot, n, m;
il void build()
{
	for(int l = 1;l <= n;l += B)
	{
		tot++;
		nxt[tot - 1] = tot;
		b[tot].clear();
		for(int i = l;i <= min(l + B - 1, n);++i) b[tot].pb(a[i]);
	}
}
il void upd(int pos, int x)
{
	int cnt = 0;
	for(int i = 1;i;i = nxt[i])
	{
		int tmp = cnt;
		cnt += b[i].size();
		if(cnt < pos) continue;
		b[i].insert(b[i].begin() + pos - tmp - 1, x);
		if(b[i].size() == 2 * B) // 分裂，大块裂成两个小块
		{
			stack<int> stk;
			for(int j = 1;j <= B;++j)
			{
				stk.push(b[j].back());
				b[j].pop_back();
			}
			b[++tot].clear();
			nxt[tot] = nxt[i];
			nxt[i] = tot;
			while(stk.size()) b[tot].pb(stk.top()), stk.pop();
		}
		break;
	}
}
il int ask(int pos)
{
	int cnt = 0;
	for(int i = 1;i;i = nxt[i])
	{
		int tmp = cnt;
		cnt += b[i].size();
		if(cnt >= pos) return b[i][pos - tmp - 1];
	}
	return -1;
}
int main()
{
	cin >> n;
	for(int i = 1;i <= n;++i) scanf("%d", &a[i]);
	build();
	m = n;
	while(m--)
	{
		int op, x, y;
		scanf("%d%d", &op, &x);
		if(op == 0) scanf("%d", &y), upd(x, y);
		else printf("%d\n", ask(x));
	}
	return 0;
}

题解：P13981 数列分块入门 6

文章操作

相关推荐

评论

题解：P13981 数列分块入门 6