网站专题设计,网站备案每年审吗,承接工程平台,做本地门户网站题目描述
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能#xff0c;那就是它具备撤销功能#xff0c;厉害吧。
请为这种高级打字机设计一个程序#xff0c;支持如下 33 种操作#xff1a;
T x#xff1a;Type 操作#xff0c;表示在文章末尾打下一个小…题目描述
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能那就是它具备撤销功能厉害吧。
请为这种高级打字机设计一个程序支持如下 33 种操作
T xType 操作表示在文章末尾打下一个小写字母 x。U xUndo 操作表示撤销最后的 x 次修改操作。Q xQuery 操作表示询问当前文章中第 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个区间。
代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;const int N 100005;
#define mid ((lr)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(lr){sum[u] 1;ch[u] c;return;}if(sum[ls[u]] mid - l1) change(ls[u],ls[v],l,mid,c); // 左区间的字母树是否小于 左区间 的 宽度else change(rs[u],rs[v],mid1,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],mid1,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){cinx;coutquery(root[cnt],1,n,x)endl;}} return 0;
} 时间复杂度为:On*longn)
