可持久化分块学习笔记

看到网上似乎没这方面的资料，填个坑,QwQ。
考虑如下一个问题：
给定一个序列，在线查询前i个数小于等于j的有多少个。（权值位于1~n）
如果没有在线操作，我们离线，对i排好序
于是我们很明显可以把所有权值分成 $\sqrt n$ 个大块和 $n$ 个小块(以下块从０开始编号)。
第i个大块表示当前位于 $[0,(i+1)*\lfloor \sqrt n \rfloor)$ 的权值有多少个
设 $k*\lfloor \sqrt n \rfloor \leqslant i < (k+1)*\lfloor \sqrt n \rfloor$
则第i个小块表示当前位于 $[k*\lfloor \sqrt n \rfloor,i]$ 的权值有多少个
每次查询我们可以拆成一个大块和一个小块的和，因此我们做到了 $O(1)$ 查询。
注意到一个位置上的权值影响到了 $\sqrt n$ 个块，所以加入一个数的复杂度为 $O(\sqrt n)$
总时间复杂度为 $O(n\sqrt n)$
如果要在线操作，我们需要实现可持久化。
对于大块，因为只有 $\sqrt n$ 个，所以我们可以对每个大块维护一个前缀和。
小块的可持久化?
注意到，每个大块"包含"（形象理解）了 $\sqrt n$ 个小块，而我们一次操作有且仅会影响一个大块中的"后缀小块"。它们的个数也是 $\sqrt n$ 级别的。我们将大块视为一个“小块集合”。那么一次操作有且仅会影响一个小块集合。
参考可持久化线段树的经验，我们尝试建一棵树。
但这颗数不是线段树！而且层数很少！就算算上根节点也就只有３层！除叶子节点外，每个点有 $\sqrt n$ 个儿子！
可持久化分块学习笔记
每次更新我们会影响到一个小块集合，于是我们将该小块集和它的子节点合暴力重建。
由于一个小块集合里面的小块个数是 $\sqrt n$ 的，所以这里复杂度为 $O(n\sqrt n)$
没有改变的小块集合我们就连到上一个版本的该小块集合。
该版本更新的小块集合对应的边也要连上去。由于一个版本的小块集合个数是 $\sqrt n$ 级别的，故这里的复杂度为 $O(n\sqrt n)$
eg:如图，第i+1次操作更新了小块集合２,它的小块集合1和i的小块集合１一样，故连同一个即可。
而小块集合２在此被更新，我们暴力重建，再将i+1版本的小块集合2连过来即可。
这样我们实现了可持久化分块！
时空复杂度: $O(n\sqrt n)$
~~有什么用！空间爆炸！~~
~~分块大法好！~~
网上这样的题不多，目前只做过一道:bzoj 5125，里面还要用到决策单调性dp。
模板如下:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,size;
#define Maxn 40005
int a[Maxn];
int *block[Maxn];
int *tree[Maxn];
int Quai[205][205];
int sum[205][Maxn];
inline int Query(int x,int y){
    if(y<=0)return 0;
    int ans=0;
    if(y>=size)ans+=sum[y/size-1][x];
    ans+=block[tree[x][y/size]][y%size];
    return ans;
}
inline void rd(int &x){
    x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
}

int main(){
    rd(n);
    size=sqrt(n);;
    for(register int i=1;i<=n;++i)rd(a[i]);
    for(register int i=0;i<=(n/size);++i){
        int up=(i+1)*size-1;
        for(register int j=1;j<=n;++j){
            sum[i][j]=sum[i][j-1];
            if(a[j]<=up)sum[i][j]++;
        }
    }
    block[0]=new int[size];
    tree[0]=new int[n/size+1];
    for(register int i=1;i<=n;++i){
        int at=a[i]/size;
        for(register int j=a[i]%size;j<size;++j)Quai[at][j]++;
        block[i]=new int[size];
        for(register int j=0;j<size;++j)block[i][j]=Quai[at][j];
        tree[i]=new int[n/size+1];
        for(register int j=0;j<=n/size;++j)tree[i][j]=tree[i-1][j];
        tree[i][at]=i;
    }
    /*
    use Query to do something
    */
    return 0;
}

可持久化分块学习笔记

相关推荐