网站建设分享文章,天津网站建设系统,门户网站的意义,宿迁市建设局投诉网站首页因为Undo操作只能撤销Type操作#xff0c;所以Undo x 实际上就是删除文章末尾x个字母。用一个栈即可解决#xff08;每个字母最多进出一次#xff09;。 这种情况下只需要设计一个合理的数据结构依次执行操作即可。
版本树#xff1a;Undo x撤销最近的x次修改操作#xf…
因为Undo操作只能撤销Type操作所以Undo x 实际上就是删除文章末尾x个字母。用一个栈即可解决每个字母最多进出一次。 这种情况下只需要设计一个合理的数据结构依次执行操作即可。
版本树Undo x撤销最近的x次修改操作实际上就是当前版本还原为x次操作前的版本换句话说版本i 版本i-x-1。 如图所示所有版本呈树状排列版本0为根。 读入所有操作并建树对这颗版本树按欧拉序求出所有版本。上图中就是按0-1-4…4-1-0-2-3-2-0的顺序遍历同样使用栈就能计算出所有的版本然后在对应的版本上解决询问即可。 到此就得到了时空复杂度均为O(n)的离线算法。 能解决这类题目的条件是 1.允许使用离线算法进而求出版本树并允许把询问挂到树的节点上。 2.所有操作都是可逆的。只有所有操作都是可逆的才能按欧拉序依次求出各版本。如本题的Type操作的逆操作就是弹出栈顶Undo操作则根本不需要修改Undo前后2个版本相同。
#includecstdio
using namespace std;
const int R1e5,N(R1)*20;
int n,m,now,sz,root[R1],ls[N],rs[N],len[N];
char s[N];
inline int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}
void insert(int k,int last,int l,int r,int pos,int c){ksz;if(lr){s[k]c;return ;}ls[k]ls[last];rs[k]rs[last];int midlr1;if(posmid) insert(ls[k],ls[last],l,mid,pos,c);else insert(rs[k],rs[last],mid1,r,pos,c);
}
void query(int k,int last,int l,int r,int pos){if(lr){putchar(s[k]);putchar(\n);return ;}int midlr1;if(posmid) query(ls[k],ls[last],l,mid,pos);else query(rs[k],rs[last],mid1,r,pos);
}
int main(){nread();for(int i1,x;in;i){char op0,ch0;for(;opA||opZ;opgetchar());if(opT){for(;cha||chz;chgetchar());now;len[now]len[now-1]1;insert(root[now],root[now-1],1,R,len[now],ch);}else if(opU){xread();now;root[now]root[now-x-1];len[now]len[now-x-1];}else xread(),query(root[now],root[now-1],1,R,x);}return 0;
}
