题解：P13981 数列分块入门 6

A7F3jK9pR0xf_ · 2025-09-07 17:37:53 · 题解

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

具体就是对原序列分块，然后每个块都维护一个 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)。

#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;
}