Problem 1 高级打字机(type.cpp/c/pas) 【题目描述】 早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。 请为这种高级打字机设计一个程序，支持如下3种操作： 1.T x：在文章末尾打下一个小写字母x。(type操作) 2.U x：撤销最后的x次修改操作。（Undo操作） （注意Query操作并不算修改操作） 3.Q x：询问当前文章中第x个字母并输出。（Query操作） 文章一开始可以视为空串。
【输入格式】 第1行：一个整数n，表示操作数量。 以下n行，每行一个命令。保证输入的命令合法。
【输出格式】 每行输出一个字母，表示Query操作的答案。
【样例输入】 7 T a T b T c Q 2 U 2 T c Q 2 【样例输出】 b c 【数据范围】 对于40%的数据 n<=200; 对于100%的数据 n<=100000；保证Undo操作不会撤销Undo操作。 高级挑战 对于200%的数据 n<=100000；Undo操作可以撤销Undo操作。 IOI挑战 必须使用在线算法完成该题。 ioi挑战好像就是裸的主席树
#include<bits/stdc++.h> using namespace std; const int maxn = 1000005; int l[3000000],r[3000000],cnt; int root[maxn],len[maxn]; char data[3000000]; char str[100]; void build(int &rt,int _l,int _r){ if(rt==0)rt=++cnt; if(_l==_r){return;} int mid=(_l+_r)>>1; build(l[rt],_l,mid); build(r[rt],mid+1,_r); } void insert(int pr_rt,int &rt,int _l,int _r,int loc,int val){ if(rt==0)rt=++cnt; int rtt=rt; while(_l<=_r){ if(_l==_r){ data[rtt]=val; break; } int mid=(_l+_r)>>1; if(loc>mid){ l[rtt]=l[pr_rt]; r[rtt]=++cnt; pr_rt=r[pr_rt];rtt=r[rtt]; _l=mid+1; } else{ r[rtt]=r[pr_rt]; l[rtt]=++cnt; pr_rt=l[pr_rt];rtt=l[rtt]; _r=mid; } } } char search(int rt,int _l,int _r,int kth){ while(_l<=_r){ if(_l==_r){ return data[rt]; } int mid=(_l+_r)>>1; if(kth > mid){ _l=mid+1; rt=r[rt]; } else{ _r=mid; rt=l[rt]; } } return 0; } int main(){ freopen("type.in","r",stdin); freopen("type.out","w",stdout); int n=0; int nw_rt=0,a=0; int loc=0; scanf("%d",&n); build(root[0],1,n); for(int i=1;i<=n;i++){ scanf("%s",str); if(str[0] == 'T'){ scanf("%s",str); nw_rt++; len[nw_rt]=len[nw_rt-1]+1; insert(root[nw_rt-1],root[nw_rt],1,n,len[nw_rt],str[0]); } else if(str[0] == 'U'){ scanf("%d",&a); nw_rt++; root[nw_rt]=root[nw_rt-a-1]; len[nw_rt]=len[nw_rt-a-1]; } else{ scanf("%d",&a); printf("%c\n",search(root[nw_rt],1,n,a)); } } return 0; }