一道非常基础的可持久化数据结构题.

前置芝士

1. 可持久化线段树:实现的方法主要是主席树.

具体做法

这个基本就是一个模板题了,记录一下每一个版本的字符串的长度,在修改的时候就只要在上一个版本后面加上一个字符,撤销操作就之久回到x个版本前就好了.用主席树维护,每次修改和查询都是\(\log_2N\)的,且可以做到在线.

代码

#include<bits/stdc++.h>
#define RAP(i,first,last) for(int i=first;i<=last;++i)
//主席树标准define
#define LSON tree[now].lson
#define RSON tree[now].rson
#define MIDDLE ((left+right)>>1)
#define LEFT LSON,left,MIDDLE
#define RIGHT RSON,MIDDLE+1,right
#define NOW now_left,now_right
#define NEW_LSON tree[new_tree].lson
#define NEW_RSON tree[new_tree].rson
using namespace std;
const int maxM=1e5+7;
int N=1e5,M;
int arr[maxM],sor[maxM];
struct Tree
{
    int sum,lson,rson;//动态开点,因为是单点查询,所以不需要合并
    //习惯性得用来sum,问题不大
}tree[maxM*32];
int cnt=0;
void UpData(int &new_tree,int num,int ch,int now,int left=1,int right=N)//在now这颗树中修改,修改后的树存在new_tree中
{
    if(num<left||right<num)//如果不在范围内就直接用原来树的值
    {
        new_tree=now;
        return;
    }
    new_tree=++cnt;//新建一个节点
    if(left==right)//叶节点直接修改
    {
        tree[new_tree].sum=ch;
        return;
    }
    //修改左右子树
    UpData(NEW_LSON,num,ch,LEFT);
    UpData(NEW_RSON,num,ch,RIGHT);
}
int Query(int k,int now,int left=1,int right=N)//查询和普通的线段树差不多
{
    if(k<left||right<k)return 0;//不在范围内返回0
    if(left==right)//到叶节点就直接返回字母
    {
        return tree[now].sum;
    }
    return Query(k,LEFT)+Query(k,RIGHT);
}
int root[maxM];//记录每个版本的根节点
int len[maxM];//记录每个版本中的字符串长度
int main()
{
    cin>>M;
    char ch;
    int x;
    char add;
    int tot=0;//记录当前的版本编号
    RAP(i,1,M)
    {
        cin>>ch;
        if(ch=='T')
        {
            ++tot;
            cin>>add;
            len[tot]=len[tot-1]+1;
            UpData(root[tot],len[tot],add,root[tot-1]);//在上一个版本后面加上一个字母
        }
        if(ch=='U')
        {
            ++tot;
            cin>>x;
            root[tot]=root[tot-x-1];//返回到x个版本前,信息只要直接赋值
            len[tot]=len[tot-x-1];
        }
        if(ch=='Q')
        {
            cin>>x;
            printf("%c\n",Query(x,root[tot]));//查询字母
        }
    }
    return 0;//完结撒花
}

P1383 高级打字机

原文：https://www.cnblogs.com/Sxy_Limit/p/12245695.html