题解：P13981 数列分块入门 6

Defy_HeavenS · 2025-09-07 14:40:42 · 题解

可以参考我的分块合集分块。

#6282. 数列分块入门 6 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及单点插入，单点询问，~~数据随机生成~~。Loj 上的数据最后三个点不是随机的。

技巧

与数列分块入门 3一样，技巧是可以在块里维护数据结构，这里维护 vector。每次先找到要插入或查询的块，插入就直接暴力插入，时间复杂度问题后面分析；查询也直接暴力找。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n)。因为随机，所以每个块被插入的元素个数在理论上相等。修改 \mathcal{O}(T+\frac{n}{T})，查询 \mathcal{O}(T+\frac{n}{T})。最优块长为 \sqrt{n}。

可是~~出题人跑数据跑了一辈子，跑出一个每次只加在第一个位置的数据……~~数据没有随机怎么办？需要引入一个操作：重新分块（重构），重构有很多种：

把整个序列重新分块（好写）；
- 定期重构，一般是 \sqrt{m} 次插入后重构（这里的 m 是重构次数），如果 m 与 n 同阶那么复杂度不会受影响；
- 有块超出范围后重构，范围一般是 2 到 5 倍的 \sqrt{n}。
把超出范围的块分成多份，一般为两份（难写）。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n)，修改 \mathcal{O}(T+\frac{n}{T})，查询 \mathcal{O}(T+\frac{n}{T})，重构 \mathcal{O}(n)，由于最多重构 \sqrt{n} 次，所以不影响复杂度。最优块长为 \sqrt{n}。

代码

#include<bits/stdc++.h>
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define tmax(a,b) (a)=max((a),(b))
#define tmin(a,b) (a)=min((a),(b))

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N=3e5+5,B=705;
int n,m,a[N],T,tot;
vector<int>b[B],tmp;

void init(){
    T=sqrt(n),tot=n/T;
    if(n%T) tot++;
    for(int i=1,be,en=0;i<=tot;i++){
        be=en+1,en=i*T;
        if(i==tot) en=n;
        for(int j=be;j<=en;j++){
            b[i].pb(a[j]);
        }
    }
}
void rebuild(){
    tmp.clear();
    for(int i=1;i<=tot;i++){
        for(auto val:b[i]){
            tmp.pb(val);
        }
        b[i].clear();
    }
    T=sqrt(tmp.size()),tot=tmp.size()/T;
    if(tmp.size()%T) tot++;
    for(int i=1,be,en=0;i<=tot;i++){
        be=en+1,en=i*T;
        if(i==tot) en=tmp.size();
        for(int j=be;j<=en;j++){
            b[i].pb(tmp[j-1]);
        }
    }
}
void update(int pos,int val){
    for(int i=1,sum=0;i<=tot;i++){
        sum+=b[i].size();
        if(sum>=pos){
            sum-=b[i].size();
            int k=0;
            for(int j=0;j<b[i].size();j++){
                if(sum+j+1==pos){
                    k=j;
                    break;
                }
            }
            b[i].pb(val);
            for(int j=b[i].size()-2;j>=k;j--){
                swap(b[i][j],b[i][j+1]);
            }
            break;
        }
    }
}
int query(int pos){
    for(int i=1,sum=0;i<=tot;i++){
        sum+=b[i].size();
        if(sum>=pos){
            sum-=b[i].size();
            for(int j=0;j<b[i].size();j++){
                if(sum+j+1==pos){
                    return b[i][j];
                }
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    m=n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    for(int i=1,j=1,op,l,r;i<=n;i++,j++){
        cin>>op>>l;
        if(op){
            cout<<query(l)<<"\n";
        }else{
            cin>>r;
            m++;
            update(l,r);
        }
        if((int)sqrt(n)==j){
            rebuild();
            j=0;
        }
    }
    return 0;
}