题目描述
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。
请为这种高级打字机设计一个程序，支持如下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[],c2[];
int x;
scanf("%s",c1);
if(c1[]=='T')
{
scanf("%s",c2);
st[++top]=c2[];
}
if(c1[]=='U')
{
scanf("%d",&x);
top-=x;
}
if(c1[]=='Q')
{
scanf("%d",&x);
printf("%c\n",st[x]);
}
}
return ;
}
那么就行这样吧
（然而并没有完（Van~））
讲一下wz小姐姐坠强的分块正解吧（能力有限，只能就着代码硬干）
#include <cmath>
#include <cstdio>
#include <cstring>
template <class T>
inline void read(T &num) { //这个快读就比较硬核
bool flag = ;
num = ;
char c = getchar();
while ((c < '' || c > '') && c != '-')
c = getchar();
if (c == '-') {
flag = ;
c = getchar();
}
num = c - '';
c = getchar();
while (c >= '' && c <= '')
num = (num << ) + (num << ) + c - '', c = getchar();
if (flag)
num *= -;
}
inline void read(char &c) {//读字符专用读取
do {
c = getchar();
} while (c == ' ' || c == '\n' || c == '\r');
}
template <class T>
inline void output(T num) {
if (num < ) {
putchar('-');
num = -num;
}
if (num >= )
output(num / );
putchar(num % + '');
}
template <class T>
inline void outln(T num) {
output(num);
putchar('\n');
}
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 = ;
int n, B;
struct node {
char *s;
int now, pc;
node *pre;
node() {
now = pc = ;
s = new char[B];
pre = NULL;
}
void copy(node *src) {
now = src->now;
pc = src->pc;
pre = src->pre;
for (int i = ; 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 - ];
head[lst]->pc = head[lst - ]->pc + ;
head[lst]->s[head[lst]->now++] = x;
} else {
head[++lst] = new node;
head[lst]->copy(head[lst - ]);
head[lst]->s[head[lst]->now++] = x;
}
}
char query(int x) {
int siz = head[lst]->now + head[lst]->pc * B;
x = siz - x + ;
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[] = new node;
for (int i = ; 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 + ] = head[lst - x];
lst += ;
}
if (op == 'Q') {
int x;
read(x);
putchar(query(x));
putchar('\n');
}
}
}
大概就是这样，具体的我也不是很清楚，感性理解一下吧