超级记事本([IOI2012]龙虾抄写器-字典树)

#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
#include<cmath>  
#include<cctype>  
#include<cassert>  
#include<climits>  
using namespace std;  
#define For(i,n) for(int i=1;i<=n;i++)  
#define Rep(i,n) for(int i=0;i<n;i++)  
#define Fork(i,k,n) for(int i=k;i<=n;i++)  
#define ForD(i,n) for(int i=n;i;i--)  
#define Forp(x) for(int p=pre[x];p;p=next[p])  
#define RepD(i,n) for(int i=n;i>=0;i--)  
#define MEM(a) memset(a,0,sizeof(a));  
#define MEMI(a) memset(a,127,sizeof(a));  
#define MEMi(a) memset(a,128,sizeof(a));  
#define INF (2139062143)  
#define F (1000000009)  
#define MAXN (100000+10)  
#define LogMAXN (20+10)  
typedef long long ll;  
struct Tnode  
{  
   char c;  
   int fa[LogMAXN],deep;  
   Tnode():deep(0){MEM(fa) }  
   Tnode(char _c,int _fa,int _deep):c(_c),deep(_deep){MEM(fa) fa[0]=_fa;}  
}a[MAXN];  
int n,tot=1;  
void msm(int t)  
{  
   for(int i=1;a[t].fa[i-1];i++)  
      a[t].fa[i]=a[a[t].fa[i-1]].fa[i-1];  
}  
void type(char c)  
{  
   tot++;  
   a[tot]=Tnode(c,tot-1,a[tot-1].deep+1);msm(tot);  
}  
void query(int p)  
{  
   p=a[tot].deep-p;  
   int now=tot;  
   while(p)  
   {  
      int t=(int)(trunc(log2(p)));  
      now=a[now].fa[t];  
      p-=1<<t;  
   }  
   printf("%c\n",a[now].c);  
}  
void undo(int p)  
{  
   tot++;  
   a[tot]=a[tot-1-p];  
}  
int main()  
{  
   freopen("spnp.in","r",stdin);  
   freopen("spnp.out","w",stdout);  
   scanf("%d",&n);  
   For(i,n)  
   {  
      char s[2],c;int p;  
      scanf("%s",s);  
      switch(s[0])  
      {  
         case'T':scanf(" %c",&c);type(c);break;  
         case'Q':scanf(" %d",&p);query(p);break;  
         default:scanf(" %d",&p);undo(p);break;  
      }  
   }  
     
// while(1);  
   return 0;  
}