可持久化数据结构

思想

• 适用范围：拓扑序不会发生改变的，如trie，线段树
• 对于一棵树来讲，要建立一个新的路径
  • 若新节点在原来的版本中已经有了，则把原来版本的这个点复制过来；
  • 原来版本有的点但不在该路径上的点，就不需要新加一个点，直接将指针指向原来版本的点即可

    trie树

    P4735 最大异或和

    题意：
    给定一个非负数的序列长度为N,有M个操作

• A x添加x到序列末尾,长度加1
• Q l r x从[l,r]选择一个数p,使得 $ a_p \oplus a_{p+1} \oplus…\oplus a_n \oplus x $最大

思路：

• 假定已经选择了一个p,则用前缀异或和可以优化成 $ S_{p-1} \oplus S_n \oplus x $
• 很明显S[n]^x为定值，此时只需看S[p-1]
• 再考虑一个问题：求最大异或对时，我们是将每个值都插入到01trie中，然后对于每一位每次寻找相反的路径
• 假设没有左边界，我们只需用S[n]^x去找最大值即可
• 考虑有左边界，我们可以对每棵树记录当前子树中的最大节点的标号，如果有最大标号>=l说明可以继续走，否则不能走
• 注意：trie的一般写法不需要使用深搜，但是此题需要从子节点更新父节点，因此插入需要写深搜

  const int N=600010,M=25*N;//每次新建一条路经(对应一个新的值)就会产生最多25个节点
  int tr[M][2],max_id[M],idx,n,m,root[N],s[N];
  void insert(int p,int q,int k,int i){//上一个版本，当前版本，二进制的第k位,在数组的第i位
    if(k<0){//边界
        max_id[q]=i;
        return;
    }
    int v=s[i]>>k&1;//当前位
    if(p)tr[q][v^1]=tr[p][v^1];
    tr[q][v]=++idx;
    insert(tr[p][v],tr[q][v],k-1,i);
    max_id[q]=max(max_id[tr[q][0]],max_id[tr[q][1]]);
  }
  int find(int p,int val,int l){
    for(int i=23;i>=0;i--){
        int v=val>>i&1;
        if(max_id[tr[p][v^1]]>=l)p=tr[p][v^1];
        else p=tr[p][v];
    }
    return val^s[max_id[p]];
  }
  void solve(){   
    cin>>n>>m;
    root[0]=++idx;
    max_id[0]=-1;
    insert(0,root[0],23,0);
    for(int i=1,x;i<=n;i++){
        cin>>x;
        s[i]=s[i-1]^x;
        root[i]=++idx;
        insert(root[i-1],root[i],23,i);
    }
    while(m--){
        char op;
        int l,r,x;
        cin>>op;
        if(op=='A'){
            cin>>x;
            n++;
            s[n]=s[n-1]^x;
            root[n]=++idx;
            insert(root[n-1],root[n],23,n);
        }
        else{
            cin>>l>>r>>x;
            cout<<find(root[r-1],s[n]^x,l-1)<<"\n";
        }
    }
  }
  

  主席树(可持久化线段树)

• 节点的l,r不再存边界而是用来存编号，查询和更改时边界作为参数下传
• 由于线段树是一段的，每次修改的那一段在原版本都必定存在，因此可以直接将信息复制过来，只需要将要修改的点所在的区间(l,r其中一个)赋值一个新节点即可(即l,r总是一个变一个不变)
• 因此每次修改只会增加logn个节点
• 缺点：由于有多个版本，懒标记很难下传

  MKTHNUM - K-th Number

  给定一个序列，每次操作询问l,r内的第k大数

• 离散化按值建树
• 从左到右插入一个新值，建新版本
• 每次询问[l,r]可以发现利用前缀和的思想,当前值域中，[l,r]的数量为版本r的数量-版本l-1的数量，因此可以两个版本同时下传计算

  struct Node{
    int l,r,cnt;
  } t[N<<5];
  int idx;
  vector<int> nums;
  int find(int x){
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
  }
  void pushup(int p){
    t[p].cnt=t[t[p].l].cnt+t[t[p].r].cnt;
  }
  int build(int l,int r){
    int p=++idx;
    if(l==r)return p;
    int mid=l+r>>1;
    t[p].l=build(l,mid),t[p].r=build(mid+1,r);
    pushup(p);
    return p;
  }
  int insert(int p,int l,int r,int x){
    int q=++idx;
    t[q]=t[p];
    if(l==r){
        t[q].cnt++;
        return q;
    }
    int mid=l+r>>1;
    if(x<=mid)t[q].l=insert(t[p].l,l,mid,x);
    else t[q].r=insert(t[p].r,mid+1,r,x);
    pushup(q);
    return q;
  }
  int query(int p,int q,int l,int r,int k){
    if(l==r)return l;
    int mid=l+r>>1;
    int cnt=t[t[q].l].cnt-t[t[p].l].cnt;
    if(k<=cnt)return query(t[p].l,t[q].l,l,mid,k);
    return query(t[p].r,t[q].r,mid+1,r,k-cnt);
  }
  int n,m,a[N],root[N];
  void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        nums.push_back(a[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    root[0]=build(0,nums.size()-1);
    for(int i=1;i<=n;i++){
        root[i]=insert(root[i-1],0,nums.size()-1,find(a[i]));
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<nums[query(root[l-1],root[r],0,nums.size()-1,k)]<<"\n";
    }
  }