rt

指针主席树被卡到 64 分，看题解说可以不建 0 号版本然后动态开点，写了一发之后只剩 60 了。（剩下都是MLE）

求教是我动态开店写错了吗？

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>

//using namespace std;

//MLE 恭喜
//why 动态开点？

const int maxn=1000005;
#define ll long long

template <typename T>
inline void read(T &x){
  x=0;int fh=1;
  char ch=getchar();
  while(!isdigit(ch)){
		if(ch=='-')
			fh=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
  x*=fh;
}

int n,m,tot;
int seq[maxn];

struct chairman_tree{
  int l,r;
  int value;
  chairman_tree *ls,*rs;
};

struct chairman_tree byte[maxn*20],*pool=byte,*root[maxn];

chairman_tree* New(){
  return ++pool;
}

inline bool outofrange(chairman_tree* &node,const int L,const int R){
  return (node->r<L)||(R<node->l);
}

// chairman_tree* Build(const int L,const int R){
//   chairman_tree *u=New();
//   u->l=L,u->r=R;
//   if(L==R){
//     u->ls=u->rs=NULL;
//     u->value=0;
//   }else{
//     int Mid=(L+R)>>1;
//     u->ls=Build(L,Mid);
//     u->rs=Build(Mid+1,R);
//   }
//   return u;
// }这是原来建 0 号版本用的

chairman_tree* Build(const int L,const int R){
  chairman_tree *u=New();
  u->l=L,u->r=R;
  u->ls=u->rs=NULL;
  return u;
}//这是动态开点用的

void insert(chairman_tree* &pre,chairman_tree* &now,const int p,const int ch){
  *now=*pre;
  if(pre->l==p && pre->r==p){
    now->value=ch;
    return;
  }

  int Mid=(pre->l+pre->r)>>1;
  if(pre->ls==NULL)
    pre->ls=Build(pre->l,Mid);
  if(pre->rs==NULL)
    pre->rs=Build(Mid+1,pre->r);

  if(!outofrange(pre->ls,p,p)){
    now->ls=New();
    insert(pre->ls,now->ls,p,ch);
  }else{
    now->rs=New();
    insert(pre->rs,now->rs,p,ch);
  }
}

int query(chairman_tree* &node,const int p){
  if(node->l==node->r)
    return node->value;
  if(!outofrange(node->ls,p,p))
    return query(node->ls,p);
  else return query(node->rs,p);
}

signed main(){
  // std::ios_base::sync_with_stdio(false);
  // std::cout.tie(NULL);
  // std::cin.tie(NULL);
  //freopen("simple.txt","r",stdin);
  read(n);
  root[0]=Build(1,n);
  for(int i=1,x;i<=n;++i){
    char ch,c;
    std::cin>>ch;
    if(ch=='T'){
      std::cin>>c;
      tot++;
      seq[tot]=seq[tot-1]+1;
      insert(root[tot-1],root[tot]=New(),seq[tot],(int)c);
    }else if(ch=='U'){
      read(x);
      tot++;
      root[tot]=New();
      *root[tot]=*root[(tot-x-1>0)?(tot-x-1):0];
      seq[tot]=seq[(tot-x-1)>0?(tot-x-1):0];
      //printf("QAQ!\n");
    }else{
      read(x);
      std::cout<<(char)query(root[tot],x+1)<<'\n';
    }
    //std::cout<<"tot="<<tot<<" "<<seq[tot]<<'\n';
  }
  return 0;
}