高级打字机 (Tries）

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挑战>
必须使用在线算法完成该题。

这题要用字典树（Tries)
还有msm（倍增算法）

另外补充一点
char s[0] 或者 char
scanf("%s",s)
这句会存不下"\0"
因此会把正在循环的自变量i 变成 0

[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<vector>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
#define LOGMAXN (16+10)
int n,tot=0;
struct Tnode
{
    int deep,f[LOGMAXN];
    char edge;
    Tnode()
    {
        memset(f,0,sizeof(f));
        deep=-1;
        edge='\0';
    }
    Tnode(char _edge,int _fa,int _deep)
    {
        memset(f,0,sizeof(f));
        f[0]=_fa;
        edge=_edge;
        deep=_deep;
    }
    int logdeep()
    {
        return int(trunc(log(deep)/log(2)));
    }
}node[MAXN];
int log2(int a)
{
    return int(trunc(log(a)/log(2)));
}
void msm(Tnode &a)
{
    int n=a.logdeep();
// if (n==1) return;
    for (int i=1;i<=n;i++)
    {
        a.f[i]=node[a.f[i-1]].f[i-1];
    }
}
void type()
{
    char c;
    scanf("%s",&c);
    tot++;
    node[tot]=Tnode(c,tot-1,node[tot-1].deep+1);
    msm(node[tot]);
}

void quere()
{
    int p;
    scanf("%d",&p);
    Tnode now=node[tot];
    p=now.deep+1-p; //第i's 祖先
    while (p)
    {
        int i=log2(p);
        p-=(1<<i);
        now=node[now.f[i]];

    }
    printf("%c\n",now.edge);

}
void undo()
{
    int p;
    scanf("%d",&p);
    tot++;
    node[tot]=node[tot-1-p];
}
int main()
{
    freopen("type.in","r",stdin);
    freopen("type.out","w",stdout);
    scanf("%d",&n);
    node[0]=Tnode();
    for (int ii=1;ii<=n;ii++)
    {
//      printf("%d\n",ii);
        char s[10];
//      printf("%d\n",ii);
        scanf("%s",s);
//      printf("%d\n",ii);
//      while(1);
        switch(s[0])
        {
            case 'T':type();break;
            case 'U':undo();break;
            case 'Q':quere();break;
        }


    }
// while (1);
    return 0;
}

补充：综合编程 , 其他综合 ,