可持久化：支持查询历史版本和在历史版本上修改

可持久化数组

主席树做即可。

【模板】可持久化数组（可持久化线段树/平衡树）

可持久化并查集

主席树做即可。

要按秩合并。（路径压缩每次建logn条链，会卡爆空间MLE）

主席树节点，维护father（是一个真实下标），维护dep（集合的最大深度），

一个关键函数是query，找到代表实际位置为pos的节点的编号

对于一个版本，

合并：先找到这个两个位置的集合的根节点。

不在同一个集合里的话，就合并。

合并的时候，新建一条链，并且更新father，dep还是原来节点的dep

如果和连向的father的dep相同的话，那就把father的点的dep++，象征这个新连上的集合深度是最深深度。

（++deep的时候，可以不建立新节点。因为只是影响一些按秩合并效率，但是基本没有影响）

（upda：2019.3.5 不会影响的。因为是对新节点的deep++，和之前版本没有任何关系）

查询：直接查询即可。

【模板】可持久化并查集

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

#define mid ((l+r)>>1)

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=1e5+;

struct node{

    int ls,rs;

    int fa,dep;

}t[N*];

int tot;

int n,m;

int las;

int rt[*N];

void build(int &x,int l,int r){

    x=++tot;

    if(l==r) {

        t[x].fa=l,t[x].dep=;

        return ;

    }

    build(t[x].ls,l,mid);

    build(t[x].rs,mid+,r);

}

int query(int x,int l,int r,int to){

    if(l==r) return x;

    if(to<=mid) return query(t[x].ls,l,mid,to);

    else return query(t[x].rs,mid+,r,to);

}

void merge(int &x,int y,int l,int r,int to,int ff){

    x=++tot;

    t[x].ls=t[y].ls;t[x].rs=t[y].rs;

    if(l==r) {

        t[x].fa=ff,t[x].dep=t[y].dep;return;

    }

    if(to<=mid) merge(t[x].ls,t[y].ls,l,mid,to,ff);

    else merge(t[x].rs,t[y].rs,mid+,r,to,ff);

}

int find(int o,int to){

//    cout<<" o "<<o<<" to "<<to<<endl;

    int now=query(rt[o],,n,to);

    if(t[now].fa==to) return now;

    return find(o,t[now].fa);

}

int main(){

    scanf("%d%d",&n,&m);

    build(rt[],,n);

//    cout<<" tot tot tot "<<tot<<endl;

//        for(reg i=1;i<=tot;++i){

//            cout<<i<<" : "<<t[i].fa<<" "<<t[i].dep<<endl;

//        }

    int op,k,x,y;las=;

    int o=;

    while(m--){

        rd(op);

        if(op==){

            ++o;

            rt[o]=rt[las];

            rd(x);rd(y);

            x=find(las,x);

            y=find(las,y);

            if(t[x].fa!=t[y].fa){

                if(t[x].dep>t[y].dep) swap(x,y);

                merge(rt[o],rt[las],,n,t[x].fa,t[y].fa);

                if(t[x].dep==t[y].dep) {

                //    cout<<" dep equal "<<t[y].fa<<endl;

                    int lp=query(rt[o],,n,t[y].fa);

                //    cout<<" lplplp "<<lp<<endl;

                    t[lp].dep++;

                }

            }

            las=o;

        }else if(op==){

            ++o;

            rd(k);

            rt[o]=rt[k];

            las=k;

        }else{

            ++o;

            //cout<<" las "<<las<<endl;

            rt[o]=rt[las];

            rd(x);rd(y);

            //cout<<" x "<<" y "<<x<<" "<<y<<endl;

            x=find(las,x);

            y=find(las,y);

            //cout<<" xx "<<" yy "<<x<<" "<<y<<endl;

            if(t[x].fa==t[y].fa){

                puts("");

            }else puts("");

            las=o;

        }

//        cout<<" tot tot tot "<<tot<<endl;

//        for(reg i=1;i<=tot;++i){

//            cout<<i<<" : "<<t[i].fa<<" "<<t[i].dep<<endl;

//        }

    }

    return ;

}

}

int main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2018/11/23 7:48:57

*/

可持久化并查集

不能在历史版本上更改的可持久化并查集。（也就是，历史版本形成的树是一条链）

（可持久化并茶几O(logn)：（NOI2018D1T1）每个点记录每时每刻在哪个集合里用vector记录pair 合并的时候，启发式合并，然后暴力修改最多O(n)个集合，每个集合记录点权最大值查询的时候二分找到这个时间段查询集合点权最大值即可）

可以做到：空间O(nlogn)时间O(nlogn)

%%ImmortalCO

可持久化平衡树：

1.还是主席树做即可。

权值暴力开到-1e9~1e9（我脑残了一下，还加了偏移量。。。）因为动态开点。。空间限制1GB

然后做就好了。

注意前驱后继的写法；

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define mid (((ll)l+r)>>1)

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=5e5+;

const int U=2e9+;

const int P=1e9+;

const int inf=;

int n;

struct node{

    int ls,rs,sz;

}t[*N];

int rt[N];

int tot;

void pushup(int x){

    t[x].sz=t[t[x].ls].sz+t[t[x].rs].sz;

}

void ins(int &x,int y,int l,int r,int to){

    //

    x=++tot;

    t[x].ls=t[y].ls,t[x].rs=t[y].rs;

    t[x].sz=t[y].sz+;

    if(l==r) return;

    if(to<=mid) ins(t[x].ls,t[y].ls,l,mid,to);

    else ins(t[x].rs,t[y].rs,mid+,r,to);

}

void dele(int &x,int y,int l,int r,int to){

//    cout<<" deleting "<<to<<endl;

    x=++tot;

    t[x].ls=t[y].ls,t[x].rs=t[y].rs;

    t[x].sz=t[y].sz;

    if(l==r){

        if(t[x].sz>=) t[x].sz--;

        return;

    }

    if(to<=mid) dele(t[x].ls,t[y].ls,l,mid,to);

    else dele(t[x].rs,t[y].rs,mid+,r,to);

    pushup(x);

}

int rk(int x,int l,int r,int c){

    if(l==r){

        return (l<c)*t[x].sz;

    }

    if(c<=mid) return rk(t[x].ls,l,mid,c);

    else return t[t[x].ls].sz+rk(t[x].rs,mid+,r,c);

}

int kth(int x,int l,int r,int k){

    //cout<<l<<" "<<r<<" "<<mid<<" kkk "<<k<<" "<<t[x].sz<<endl;

    if(l==r)return l;

    int d=k-t[t[x].ls].sz;

    if(d<=) return kth(t[x].ls,l,mid,k);

    else return kth(t[x].rs,mid+,r,d);

}

int pre(int x,int l,int r,int c){

    if(l>=c||t[x].sz==) return -inf;

    else if(l==r) return l;

    else{

        int ret=pre(t[x].rs,mid+,r,c);

        if(ret!=-inf) return ret;

        return pre(t[x].ls,l,mid,c);

    }

}

int bac(int x,int l,int r,int c){

    //cout<<l<<" "<<r<<" "<<" : "<<t[x].sz<<endl;

    if(r<=c||t[x].sz==) return inf;

    else if(l==r) return l;

    else{

        int ret=bac(t[x].ls,l,mid,c);

        if(ret!=inf) return ret;

        return bac(t[x].rs,mid+,r,c);

    }

}

int main(){

    scanf("%d",&n);

    int st,op,x;

    int o=;

    while(n--){

        rd(st),rd(op);rd(x);

        x+=P;

        ++o;

        rt[o]=rt[st];

        switch(op){

            case :ins(rt[o],rt[st],,U,x);break;

            case :dele(rt[o],rt[st],,U,x);break;

            case :printf("%d\n",rk(rt[o],,U,x)+);break;

            case :{

                int tmp=kth(rt[o],,U,x-P);

                //cout<<" tmp "<<tmp<<" "<<tmp-1e9<<" "<<tmp-1e9-1<<endl;

                printf("%d\n",tmp-P);

                break;

            }

            case :{

                int tmp=pre(rt[o],,U,x);

                if(tmp>=&&tmp<=U){

                    printf("%d\n",tmp-P);

                }

                else printf("%d\n",tmp);//not find

                break;

            }

            case :{

                int tmp=bac(rt[o],,U,x);

                if(tmp>=&&tmp<=U){

                    printf("%d\n",tmp-P);

                }

                else printf("%d\n",tmp);//not find

                break;

            }

        }

        //cout<<" num "<<o<<" : "<<" tot "<<tot<<" sz "<<rt[o]<<" "<<t[rt[o]].sz<<endl;

    }

    return ;

}

}

int main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2018/11/23 9:19:03

*/

可持久化平衡树

2.fhq-Treap？

留坑

[学习笔记]FHQ-Treap及其可持久化

例题：bzoj3946: 无聊的游戏

可持久化0/1Trie

其实就类似于主席树。（哪里都是主席树啊。。。）

维护一个序列前缀的信息。

每次加入一个点，在前一个的基础上，加入的是一个log(val)的链。

额外维护一个sz，表示，前i个位置，走到这个位置，往下还有多少个数。（就类似于主席树）

然后，给一个x，如果要找区间最大异或值，直接sz差分，判断有无，然后贪心走即可。

例题：模板：最大异或和

变一下形，就可以当“给一个x，找区间一个值异或，使得值最大”

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=+;

const int U=;

int n,m;

struct trie{

    int ch[];

    int sz;

}t[*N];

int tot;

int s;

int rt[N+N];

void ins(int id,int v){

    rt[id]=++tot;

    int x=rt[id],y=rt[id-];

    for(reg i=U;i>=;--i){

        int c=(v>>i)&;

        t[x].ch[!c]=t[y].ch[!c];

        t[x].ch[c]=++tot;

        x=t[x].ch[c];

        y=t[y].ch[c];

        t[x].sz=t[y].sz+;

    }

}

int query(int l,int r,int v){

    int y=l->=?rt[l-]:rt[],x=rt[r];

    int ret=;

    for(reg i=U;i>=;--i){

        int c=(v>>i)&;

        int d=t[t[x].ch[!c]].sz-t[t[y].ch[!c]].sz;

        if(d){

            ret+=(<<i);

            x=t[x].ch[!c];y=t[y].ch[!c];

        }

        else{

            x=t[x].ch[c];y=t[y].ch[c];

        }

    }

    //cout<<l<<" "<<r<<" "<<x<<endl;

    if(l==) ret=max(ret,v);

    return ret;

}

int main(){

    scanf("%d%d",&n,&m);

    int x;

    for(reg i=;i<=n;++i){

        rd(x),s^=x,ins(i,s);

    }

    char ch[];int l,r;

    int now=n;

    while(m--){

        scanf("%s",ch+);

        //cout<<"ss "<<s<<endl;

        switch(ch[]){

            case 'A':rd(x);s^=x;ins(++now,s);break;

            case 'Q':{

                rd(l);rd(r);rd(x);

                --l,--r;

                x=s^x;

                printf("%d\n",query(l,r,x));

                break;

            }

        }

        //cout<<" mmm "<<m<<endl;

    }

    return ;

}

}

int main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2018/11/23 14:22:23

*/

最大异或和

[TJOI2018]异或

维护两个可持久化Trie，一个dfn序，处理子树。一个维护到树根的信息。

子树，dfn序直接查询

路径，拆成x到lca，y到lca分别差分查询。

注意数组大小，根节点还有2*N个空间。。。。。

31*N*2+2*N

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=+;

struct trie{

    int ch[];

    int sz;

}t[*N*+*N];

int tot;

int df,dfn[N],fdfn[N],dfn2[N];

int fa[N][];

int dep[N];

int a[N];

int n,m;

struct node{

    int nxt,to;

}e[*N];

int hd[N],cnt;

void add(int x,int y){

    e[++cnt].nxt=hd[x];

    e[cnt].to=y;

    hd[x]=cnt;

}

int rt1[N];

int lca(int x,int y){

    if(dep[x]<dep[y]) swap(x,y);

    for(reg j=;j>=;--j){

        if(dep[fa[x][j]]>=dep[y]) x=fa[x][j];

    }

    if(x==y) return x;

    for(reg j=;j>=;--j){

        if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];

    }

    return fa[x][];

}

void ins1(int x,int y,int v){

    rt1[x]=++tot;

    x=rt1[x];

    for(reg i=;i>=;--i){

        int c=(v>>i)&;

        t[x].ch[!c]=t[y].ch[!c];

        t[x].ch[c]=++tot;

        x=t[x].ch[c];

        y=t[y].ch[c];

        t[x].sz=t[y].sz+;

    }

}

void dfs(int x,int d){

    dep[x]=d;

    dfn[x]=++df;fdfn[df]=x;

    ins1(x,rt1[fa[x][]],a[x]);

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa[x][]) continue;

        fa[y][]=x;

        dfs(y,d+);

    }

    dfn2[x]=df;

}

int query1(int y,int x,int v){

    x=rt1[x];y=rt1[y];

    int ret=;

    for(reg i=;i>=;--i){

        int c=(v>>i)&;

        int d=t[t[x].ch[!c]].sz-t[t[y].ch[!c]].sz;

        if(d){

            ret+=(<<i);

            x=t[x].ch[!c];y=t[y].ch[!c];

        }

        else {

            x=t[x].ch[c];y=t[y].ch[c];

        }

    }

    return ret;

}

int rt2[N];

void ins2(int x,int v){

    int y=rt2[x-];

    rt2[x]=++tot;

    x=rt2[x];

    for(reg i=;i>=;--i){

        int c=(v>>i)&;

        t[x].ch[!c]=t[y].ch[!c];

        t[x].ch[c]=++tot;

        x=t[x].ch[c];

        y=t[y].ch[c];

        t[x].sz=t[y].sz+;

    }

}

int query2(int y,int x,int v){

    x=rt2[x];y=rt2[y];

    int ret=;

    for(reg i=;i>=;--i){

        int c=(v>>i)&;

        int d=t[t[x].ch[!c]].sz-t[t[y].ch[!c]].sz;

        if(d){

            ret+=(<<i);

            x=t[x].ch[!c];y=t[y].ch[!c];

        }

        else {

            x=t[x].ch[c];y=t[y].ch[c];

        }

    }

    return ret;

}

int main(){

    scanf("%d%d",&n,&m);

    for(reg i=;i<=n;++i){

        rd(a[i]);

    }

    int x,y;

    for(reg i=;i<=n-;++i){

        rd(x);rd(y);add(x,y);add(y,x);

    }

    dep[]=-;

    dfs(,);

    for(reg j=;j<=;++j){

        for(reg i=;i<=n;++i){

            fa[i][j]=fa[fa[i][j-]][j-];

        }

    }

    for(reg i=;i<=n;++i){

        ins2(i,a[fdfn[i]]);

    }

    int op;

    int z;

    while(m--){

        scanf("%d",&op);

        if(op==){

            rd(x);rd(y);

            printf("%d\n",query2(dfn[x]-,dfn2[x],y));

        }

        else{

            rd(x);rd(y);rd(z);

            int anc=lca(x,y);

            printf("%d\n",max(query1(fa[anc][],x,z),query1(fa[anc][],y,z)));

        }

    }

    return ;

}

}

int main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2018/11/23 16:08:01

*/

异或

可持久化用途

可持久化目的主要就是充分利用不会动的信息，减少时空的浪费

1.历史值查询：模板，以及可持久化trie和主席树的差分

2.路径压缩，任意字符集AC自动机

3.当做标记：bzoj3946: 无聊的游戏

[学习笔记]可持久化数据结构——数组、并查集、平衡树、Trie树的更多相关文章

POJ2513 【并查集+欧拉路径+trie树】
题目链接:http://poj.org/problem?id=2513 Colored Sticks Time Limit: 5000MS Memory Limit: 128000K Total ...
[学习笔记]我们追过的神奇异或（Trie树系列）
引言刚学了\(Trie\)树,写篇博客巩固一下. 题目首先安利一发\(Trie\)树模板 1.Phone List 2.The XOR largest pair 3.The xor-longest ...
UVALive - 5031 Graph and Queries (并查集+平衡树/线段树)
给定一个图,支持三种操作: 1.删除一条边 2.查询与x结点相连的第k大的结点 3.修改x结点的权值解法:离线倒序操作,平衡树or线段树维护连通块中的所有结点信息,加个合并操作就行了. 感觉线段树要 ...
matlab学习笔记(一）单元数组
matlab学习笔记(一)单元数组 1.floor(x) :取最小的整数 floor(3.18)=3,floor(3.98)=3 ceil(x) :取最大的整数 ceil(3.18)=4,ceil( ...
python3&period;4学习笔记(十一) 列表、数组实例
python3.4学习笔记(十一) 列表.数组实例 #python列表,数组类型要相同,python不需要指定数据类型,可以把各种类型打包进去#python列表可以包含整数,浮点数,字符串,对象#创建 ...
Java学习笔记之---方法和数组
Java学习笔记之---方法与数组 (一)方法 (1)什么是方法? 方法是解决一类问题的步骤的有序组合方法包含于类或对象中方法在程序中被创建,在其他地方被引用 (2)方法的优点使程序变得更简短而 ...
JavaSE学习笔记（7）---数组
JavaSE学习笔记(7)---数组 1.什么是数组数组是相同类型数据的有序集合.数组描述的是相同类型的若干个数据,按照一定的先后次序排列组合而成.其中,每一个数据称作一个元素,每个元素可以通过一个 ...
[BZOJ3038]上帝造题的七分钟2 树状数组+并查集
考试的时候用了两个树状数组去优化,暴力修改,树状数组维护修改后区间差值还有最终求和,最后骗了40分.. 这道题有好多种做法,求和好说,最主要的是开方.这道题过的关键就是掌握一点:在数据范围内,最多开方 ...
BZOJ 4566 JZYZOJ 1547 [haoi2016T5]找相同子串后缀数组并查集
http://172.20.6.3/Problem_Show.asp?id=1547 http://www.lydsy.com/JudgeOnline/problem.php?id=4566 单纯后缀 ...

随机推荐

我的面板我做主 -- 淘宝UWP中自定义Panel的实现
在Windows10 UWP开发平台上内置的XMAL布局面板包括RelativePanel.StackPanel.Grid.VariableSizedWrapGrid 和 Canvas.在开发淘宝UW ...
overflow&colon;hidden清楚浮动的影响
在网页布局中有时会遇到这种情况: 如果左边用<dt>,右边用<dd>,放在一行显示,<dt>要设置float:left,这个应该都知道,问题是,第一行这样做没有问题 ...
malloc/free和new/delete的区别
转自:http://blog.csdn.net/chance_wang/article/details/1609081 malloc与free是C++/C语言的标准库函数,new/delete是C++ ...
android- Auto Monitor Logcat
启动模拟器的时候弹出窗体: 它实在询问你是否显示logcat视图以便显示此工作空间中的程序信息. 因为如何程序错误,可以从logcat中看到错误的原因,建议选择yes. 单击确定,你会发现多了一个Lo ...
android开发之国际化
国际化,听起来高大上,做起来很简单. 我们来实现一个简单的效果,让应用根据系统的语言来做不同的显示,假如android系统默认是英语,应用就以英文的形式显示,如果android系统默认是中文,则应用就 ...
web3 - BOM&amp&semi;DOM
一.BOM (浏览器对象模型) 浏览器对象模型 (BOM) 使 JavaScript 有能力与浏览器"对话". Window 对象 1.window.onresize // 1 w ...
【BZOJ4504】K个串
题解: 这题跟超级noi钢琴思路大致相同不同之处在于如何寻找最大值这道题里出现了每个数都只能被算一次这个限制我们考虑一下如果还要使用主席树和前缀和该怎么做我们每次操作一个数时,可以让这个数上一 ...
NC 6系后台调用接口保存单据
IPFBusiAction ipf = (IPFBusiAction)NCLocator.getInstance().lookup(IPFBusiAction.class); ipf.processA ...
net&period;sf&period;json&period;JSONException&colon; &amp&semi;&num;39&semi;object&amp&semi;&num;39&semi; is an array&period; Use JSONArray instead
list集合转换JSON出错误意思是:对象"是一个数组. 使用jsonarray取代. 解决方法: 将JSONObject替换为JSONArray 代码: JsonConfig jsonC ...
tensorboard-sklearn数据-loss
记录sklearn数据训练时的loss值,用tensorboard可视化三步骤:红字处 import tensorflow as tf from sklearn.datasets import lo ...