本文主要是介绍P1383 高级打字机（可持续化线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。
请为这种高级打字机设计一个程序，支持如下 33 种操作：
T x：Type 操作，表示在文章末尾打下一个小写字母 x。U x：Undo 操作，表示撤销最后的 x 次修改操作。Q x：Query 操作，表示询问当前文章中第 x 个字母并输出。请注意 Query 操作并不算修改操作。
文章一开始可以视为空串。
输入格式
第 11 行：一个整数 n，表示操作数量。
以下 n 行，每行一个命令。保证输入的命令合法。
输出格式
每行输出一个字母，表示 Query 操作的答案。
输入输出样例
输入 #1复制
7 T a T b T c Q 2 U 2 T c Q 2
输出 #1复制
b c 解析：
用可持续化线段树，每次操作的区间的最后一个没有记录的为1个区间。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 100005;
#define mid ((l+r)>>1)
int root[N],tot = 0,cnt = 0;
int ls[N*20],rs[N*20],sum[N*20];
char ch[N*20];void pushup(int u)
{sum[u] = sum[ls[u]] + sum[rs[u]];
} void change(int &u,int v,int l,int r,char c)
{u =++tot;ls[u] = ls[v];rs[u] = rs[v];sum[u] = sum[v];if(l==r){sum[u] = 1;ch[u] = c;return;}if(sum[ls[u]] < mid - l+1) change(ls[u],ls[v],l,mid,c); // 左区间的字母树是否小于 左区间 的 宽度else change(rs[u],rs[v],mid+1,r,c);pushup(u);
}char query(int u,int l,int r,int x)//查询第x个字母
{if(l == r) return ch[u];if(x <= sum[ls[u]]) return query(ls[u],l,mid,x);else return query(rs[u],mid+1,r,x-sum[ls[u]]);
}int main()
{int n;cin >> n;for(int i = 1;i <= n;i++){char o,c;int x;cin >> o;if(o == 'T'){cin >> c;++cnt;change(root[cnt],root[cnt-1],1,n,c);}if(o == 'U'){cin >> x;++cnt;root[cnt] = root[cnt-x-1];}if(o == 'Q'){cin>>x;cout<<query(root[cnt],1,n,x)<<endl;}} return 0;
}时间复杂度为:O（n*longn)
这篇关于P1383 高级打字机（可持续化线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
