题目描述
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。
请为这种高级打字机设计一个程序，支持如下3种操作：
1.T x：在文章末尾打下一个小写字母x。(type操作)
2.U x：撤销最后的x次修改操作。（Undo操作）
（注意Query操作并不算修改操作）
3.Q x：询问当前文章中第x个字母并输出。（Query操作）
文章一开始可以视为空串。
输入输出格式
输入格式：
第1行：一个整数n，表示操作数量。
以下n行，每行一个命令。保证输入的命令合法。
输出格式：
每行输出一个字母，表示Query操作的答案。
输入输出样例
说明
【数据范围】
对于40%的数据 n<=200;
对于100%的数据 n<=100000；保证Undo操作不会撤销Undo操作。
<高级挑战>
对于200%的数据 n<=100000；Undo操作可以撤销Undo操作。
<IOI挑战>
必须使用在线算法完成该题。
生硬的讲解
这题我一看就不会，所以直接运用数组强行模拟栈，轻松拿下50Pts（然后就开始使劲颓废）
那么我们就先来讲一讲50Pts是如何拿下的吧QwQ
首先，看到这个题（前100%的数据点），果断想到了栈（这前100%和栈完全一样啊QwQ）
直接模拟
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<iomanip> #include<string> #include<algorithm> #include<cstdlib> #include<queue> #include<stack> using namespace std; #define maxn 100001 int top,t; char st[maxn]; int main() { freopen("type.in","r",stdin); freopen("type.out","w",stdout); scanf("%d",&t); while(t--) { char c1[2],c2[2]; int x; scanf("%s",c1); if(c1[0]=='T') { scanf("%s",c2); st[++top]=c2[0]; } if(c1[0]=='U') { scanf("%d",&x); top-=x; } if(c1[0]=='Q') { scanf("%d",&x); printf("%c ",st[x]); } } return 0; }
那么就行这样吧
（然而并没有完（Van~））
讲一下wz小姐姐坠强的分块正解吧（能力有限，只能就着代码硬干）
#include <cmath> #include <cstdio> #include <cstring> template <class T> inline void read(T &num) { //这个快读就比较硬核 bool flag = 0; num = 0; char c = getchar(); while ((c < '0' || c > '9') && c != '-') c = getchar(); if (c == '-') { flag = 1; c = getchar(); } num = c - '0'; c = getchar(); while (c >= '0' && c <= '9') num = (num << 3) + (num << 1) + c - '0', c = getchar(); if (flag) num *= -1; } inline void read(char &c) {//读字符专用读取 do { c = getchar(); } while (c == ' ' || c == ' ' || c == ' '); } template <class T> inline void output(T num) { if (num < 0) { putchar('-'); num = -num; } if (num >= 10) output(num / 10); putchar(num % 10 + '0'); } template <class T> inline void outln(T num) { output(num); putchar(' '); } template <class T> inline void outps(T num) { output(num); putchar(' '); } template <class T> inline T max(T a, T b) { return a < b ? b : a; } const int N = 100000; int n, B; struct node { char *s; int now, pc; node *pre; node() { now = pc = 0; s = new char[B]; pre = NULL; } void copy(node *src) { now = src->now; pc = src->pc; pre = src->pre; for (int i = 0; i < now; i++) { s[i] = src->s[i]; } } } * head[N]; int lst; void append(char x) { if (head[lst]->now == B) { head[++lst] = new node; head[lst]->pre = head[lst - 1]; head[lst]->pc = head[lst - 1]->pc + 1; head[lst]->s[head[lst]->now++] = x; } else { head[++lst] = new node; head[lst]->copy(head[lst - 1]); head[lst]->s[head[lst]->now++] = x; } } char query(int x) { int siz = head[lst]->now + head[lst]->pc * B; x = siz - x + 1; if (x <= head[lst]->now) { return head[lst]->s[head[lst]->now - x]; } x -= head[lst]->now; node *now = head[lst]->pre; while (x > B) { now = now->pre; x -= B; } return now->s[B - x]; } int main() { read(n); B = sqrt(n); head[0] = new node; for (int i = 1; i <= n; i++) { char op; read(op); if (op == 'T') { char x; read(x); append(x); } if (op == 'U') { int x; read(x); head[lst + 1] = head[lst - x]; lst += 1; } if (op == 'Q') { int x; read(x); putchar(query(x)); putchar(' '); } } }
大概就是这样，具体的我也不是很清楚，感性理解一下吧