P1383 高级打字机

打印机

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
const int N=100005;
int tot,cnt,root[N];
int ls[N*20],rs[N*20],sum[N*20];//区间内字母数
char ch[N*20];
void pushup(int u)
{sum[u]=sum[ls[u]]+sum[rs[u]];
}
void change(int &u,int v,int l,int r,char c)
{u=++tot;ls[u]=ls[v];rs[u]=rs[v];sum[u]=sum[v];if(l==r){sum[u]=1;ch[u]=c;return;}if(sum[ls[u]]<mid-l+1) change(ls[u],ls[v],l,mid,c);else change(rs[u],rs[v],mid+1,r,c);pushup(u);
}
char query(int u,int l,int r,int x)
{if(l==r) return ch[u];if(x<=sum[ls[u]]) return query(ls[u],l,mid,x);else return query(rs[u],mid+1,r,x-sum[ls[u]]);
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){char o,c;int x;cin>>o;if(o=='T'){cin>>c;++cnt;change(root[cnt],root[cnt-1],1,n,c);}if(o=='U'){cin>>x;++cnt;root[cnt]=root[cnt-x-1];}if(o=='Q'){cin>>x;cout<<query(root[cnt],1,n,x)<<endl;}}return 0;
}

1. 用到的还是可持久线段树，只不过这道题是字母的，所以和原本的模板不太一样。原本change函数里面的if(p<=mid) change(ls[u],ls[v],l,mid,p,x); else change(rs[u],rs[v],mid+1,r,p,x);

   条件是p<=mid，但是这里因为是字符，所以就不太一样。我们开一个sum数组来存储区间字母 数，这样，通过if(sum[ls[u]]<mid-l+1)的二分判断，依旧可以进行有效的判断。

2. 在query函数里面，当x应该在右半部分的时候，执行的是query(rs[u],mid+1,r,x-sum[ls[u]]);这是因为第 x 个字符在右子树中。但由于左子树已经占用了 sum[ls[u]] 个字符，右子树中的第一个字符对应整个序列的第 sum[ls[u]] + 1 个字符。因此，在递归查询右子树时，需要调整查询位置：从 x 中减去左子树的字符数，即使用 x - sum[ls[u]] 作为右子树中的查询索引。
   董晓