四，可持久化数据结构

概念：可以回退到历史版本，每次操作算一个版本，其实可持久化核心操作就是复制并复用上个版本的内容，降低空间复杂度

可持久化线段树

啊吧啊吧啊吧啊把

题目链接： 第K小数

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1e5 + 10;

struct Tree{
  int l,r;
  int cnt;
}tr[4 * N + N * 17];

int n ,m,idx;
int a[N];
int root[N];
vector<int> nums;

int find(int x){
  return lower_bound(nums.begin() , nums.end() , x) - nums.begin();
}

void pushup(int now){
 tr[now].cnt = tr[tr[now].l].cnt + tr[tr[now].r].cnt; 
}

int build(int l,int r)
{
  int now = ++idx;
  if(l==r)
  {
    return now;
  }
  else
  {
    int mid = l + r >> 1;
    tr[now].l = build(l,mid), tr[now].r = build(mid + 1 , r);
    return now;
  }
}

int insert(int last , int l ,int r, int k){
  int now = ++ idx;
  tr[now] = tr[last];
  if(l == r){
   tr[now].cnt++;
    return now;
  }
  else
  {
    int mid = l + r >> 1;
    if(k <= mid)tr[now].l = insert(tr[last].l ,l ,mid , k);
    else tr[now].r = insert(tr[last].r , mid + 1 , r , k);
    pushup(now);
    return now;
  }

}

int query(int last ,int now ,int l,int r , int k){
  if(l == r)return r;
  else
  {
    int mid = l + r >> 1;
    int cnt = tr[tr[now].l].cnt - tr[tr[last].l].cnt;
    if(cnt < k )return query(tr[last].r , tr[now].r ,mid + 1 , r , k -  cnt);
    else return query(tr[last].l , tr[now].l , l ,mid , k );
  }

}

int main(){

    int l,r,k;
    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());

    int len = nums.size();
    root[0] = build(0 , len - 1);

    for(int i = 1 ; i <= n ; i++)
    {
        root[i] = insert(root[i - 1] , 0 , len - 1 , find(a[i]));
    }

    while(m--){
        cin >> l >> r >> k;
        cout << nums[query(root[l - 1],root[r] , 0 , len - 1 , k)] << endl;

    }

    return 0;
}

可持久化字典树

啊吧啊把啊把啊把啊把

题目链接： 最大异或和

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 6e5 + 10;

int n ,m;
int tr[N * 25][2] , idx;
int  root[N];
int max_id[N * 25];
int s[N];

void insert(int i,int k,int last,int now){

    if(k < 0)
    {
        max_id[now] = i;
        return;
    }
    int v = s[i] >> k & 1;
    if(tr[last][v^1])tr[now][v ^ 1] = tr[last][v ^ 1];
    tr[now][v] = ++idx;
    insert(i,k-1,tr[last][v] , tr[now][v]);
    max_id[now] = max(max_id[tr[now][1]] , max_id[tr[now][0]]);

}

int query(int root,int C,int limit){
    int p = root;
    for(int i = 23 ; i >= 0 ; i--)
    {
        int v = C >> i & 1;
        if(max_id[tr[p][v^1]] >= limit )p = tr[p][v^1];
        else p = tr[p][v];
    }
    return C ^ s[max_id[p]];
}

int main(){
   char op[2];
    int l ,r ,x;

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

    max_id[0] = -1;
    root[0] = ++idx;
    insert(0,23,0,root[0]);

    for(int i = 1 ; i <= n ;i++)
    {
         scanf("%d",&x);
        s[i] = s[i - 1] ^ x;
        root[i] = ++idx;
        insert(i , 23 , root[i - 1] , root[i]);
    }


    while(m --)
    {
         scanf("%s",op);
         if(op[0] == 'A')
         {
             scanf("%d",&x);
             n++;
             s[n] = s[n - 1] ^ x;
             root[n] = ++idx;
             insert(n , 23 , root[n - 1] , root[n]);
         }
         else
         {
             scanf("%d%d%d",&l,&r,&x);
               printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
         }

    }



    return 0;
}

可持久化数组

挖坑

可持久化并查集

挖坑

可持久化栈

题目链接: 模板题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 1e6 + 10;

int read(){
    int x;scanf("%d" ,&x);return x;
}

int lc[N],rc[N],top[N], val[N];
int n;
int root[N];
int now;
int insert(int last , int l ,int r ,int x ,int d){
    int p = ++now;
    lc[p] = lc[last]  ,rc[p] = rc[last];
    if(l == r){val[now] = d;return now;}
    int mid = l + r >> 1;
    if(x <= mid)lc[p] = insert(lc[last] , l , mid , x ,d);
    else rc[p] = insert(rc[last] , mid + 1 ,r ,x ,d);
    return p;
}

int query(int last , int l ,int r ,int x){
    if(l == r)return val[last];

    int mid = l + r >> 1;
    if(x <= mid)return query(lc[last] , l , mid , x);
    else return query(rc[last] , mid + 1 , r ,x);

}

int main(){

    n = read();

    char op[5];
    int x;
   //root[0] = build(1 , )
    for(int i = 1 ; i <= n;i++)
    {
        scanf("%s",op);

        if(op[0] == 'a')
        {
            x = read();
            top[i] = top[i - 1] + 1;
            root[i] = insert(root[i - 1] , 1 , n ,top[i], x);
        }
        else if(op[0] == 's')
        {
            top[i] = top[i - 1];
            root[i] = root[i - 1];
            root[i] = insert(root[i - 1] , 1 , n , top[i] , 0);
            top[i]--;
        }
        else
        {
            x = read();
            root[i] = root[x - 1];
            top[i] = top[x - 1];

        }

        printf("%d\n",top[i] == 0?-1:query(root[i],1,n,top[i]));
    }


    return 0;
}