P1383高级打字机

主席树，单点修改，单点查询

写在前面

我，作为一个蒟蒻，前两天刚学完主席树，这是第一道，我用主席树做出来的题（模板题不算），所以我来写篇题解纪念一下~

如果不会线段树的先指路一个线段树教程

再指路一个主席树教程，我觉得写的很好的一篇博客，没有放代码，但是过程讲解的很详细

如果习惯看代码的朋友，可以看这个主席树教程，来自@孤独·粲泽

回归正题！

主要思路：直接针对每次的文章建一个主席树，\(rt[i]\)表示第\(i\)次修改操作做完时，当前文章的状态。

一些可爱的细节：

首先，考虑一下这么做会不会\(MLE\)，\(10w\)的数据，一开始建树会有\(20w\)的节点，每次增加\(log(n)\)个，一共会有大概\(200w\)的节点，绰绰有余~

其次，就要说说这道题目里的……撤销撤销操作。其实就和主要思路里说的一样，就是每次撤销操作都新建立一个新的节点，这个节点就直接导到对应的节点，就像这样 \(rt[i]=rt[i-x-1]\)（\(i\)表示当前是第\(i\)次操作，\(x\)是当前需要撤销的步数）

然后，在撤销撤销操作的时候，可能会出现长度的改变，所以为了方便起见，在\(rt[]\)里，我开了一个\(.len\)来记录当前节点文章的长度。代码中也有标注。

---

代码应该也是比较好懂的了，那就上代码吧~

Code

#include<bits/stdc++.h>
#define writeln putchar('\n')
using namespace std;
int n,m,cnt,i;
char s[10];
struct node
{
	int l,r;char s;
}f[8000010];
struct root
{
	int x,len;
}rt[100010];
//建树，f[u].l为左子树的节点编号，f[u].r为右子树的节点编号
//f[u].s为节点内容 
int build(int l,int r) 
{
	int u=++cnt;
	if (l==r) return u;
	int mid=(l+r)>>1;
	f[u].l=build(l,mid);
	f[u].r=build(mid+1,r);
	return u;
}
//k为当前打入的字母，p为它要去的位置
//一个非常朴素的单点修改 
int add(int u,int l,int r,char k,int p)
{
	int uu=++cnt;
	f[uu].l=f[u].l;f[uu].r=f[u].r;
	if (l==r)
	{
		f[uu].s=k;
		return uu;
	}
	int mid=(l+r)>>1;
	if (p<=mid) f[uu].l=add(f[uu].l,l,mid,k,p);
	else f[uu].r=add(f[uu].r,mid+1,r,k,p);
	return uu;
}
//p为查询位置 
//非常朴素的单点查询 
char find(int u,int l,int r,int p)
{
	int mid=(l+r)>>1;
	if (l==r) return f[u].s;
	if (p<=mid) return find(f[u].l,l,mid,p);
	else return find(f[u].r,mid+1,r,p);
}
int main()
{
	scanf("%d",&n);i=0;//i==>当前是第i次（修改）操作 
	rt[0].x=build(1,n);rt[0].len=0;
	for (int X=1;X<=n;++X)
	{
		scanf("%s",s);++i;
		if (s[0]=='T')
		{
			scanf("%s",s);
			rt[i].len=rt[i-1].len+1;//在上一次的长度上加1
			rt[i].x=add(rt[i-1].x,1,n,s[0],rt[i].len);
            //.len就是为了解决这里的问题，这样就可以很方便的找到当前的字母它
			//应该在的位置 
		}
		if (s[0]=='U')
		{
			int x;
			scanf("%d",&x);
			rt[i]=rt[i-1-x];
			//这里就是撤销操作了，直接继承撤销到的位置的节点 
		}
		if (s[0]=='Q')
		{
			int x;
			scanf("%d",&x);
			//因为每次循环在最上面会增加一个操作数，但是查询操作并不被认为是
			//修改操作，这里本来就要导入rt[i-1]，i也要减一，所以就写在一起了 
			char y=find(rt[--i].x,1,n,x);
			putchar(y);writeln;
		}
	}
	return 0;
}

---

写在最后

我，作为一个平平无奇的女高中生，一不小心被拉入了计算机竞赛的道路……于是，我成了我们机房为数不多的学生里唯一一个女生。

我平时在机房学习，没有老师线下的指导，其实是很苦恼的，每天找博客，学算法，可能思维也没有男生好，基础也不够扎实。但是我还在坚持，因为我知道我并不是低人一等。

既然坚持下来了，就不要放弃了。也不要觉得现在学到的东西，如果没能拿奖，就没什么用了，这也是对理科思维的锻炼，对以后的学习生活也是有帮助的。

这是对我自己的勉励，也是对所有女子\(OIer\)的致敬。