题意
维护一个字符串，支持以下操作：
- \(\texttt{I x c}\)，在第 \(x\) 个字母后面插入一个 \(c\)。
- \(\texttt{D x}\)，删除第 \(x\) 个字母。
- \(\texttt{R x y}\)，反转当前文本中的区间 \([x,y]\)。
- \(\texttt{P x}\)，输出初始文本中第 \(x\) 个字母在当前文本中的位置。特别地，若不存在，输出 \(0\)。
- \(\texttt{T x}\)，输出当前文本中第 \(x\) 个字母。
- \(\texttt{Q x y}\)，输出当前文本中区间 \([x,y]\) 内出现过的字母的种类数。
分析
序列问题，有插入操作，直接无脑上平衡树。
本题解使用 FHQ Treap。
我们先看这一个操作：
- \(\texttt{P x}\)，输出初始文本中第 \(x\) 个字母在当前文本中的位置。特别地，若不存在，输出 \(0\)。
发现一般的 FHQ Treap 无法维护相关信息。
考虑记录每个节点的父亲节点。
从该节点向根跳，如果该节点是父亲节点的右儿子，那么记录父亲节点及其左子树贡献。
新的问题来了：如何维护父亲节点？
我们可以考虑在 push_up() 操作时维护，将两个子节点的父节点设为当前节点。
对于个别节点（split() 或 merge() 操作后的根节点），在操作完后单独将父节点设为空即可。
该部分代码如下：
void access(node *x)
{
if(!x) return;
access(x->fa);
x->push_down();
}
uint32_t find_pos(node *x)
{
if(x->del||!x) return 0;
access(x);
uint32_t res=siz(x->lc)+1;
while(x->fa)
{
if(x->fa->rc==x)
res+=siz(x->fa->lc)+1;
x=x->fa;
}
return res;
}
然后来看查询操作：
- \(\texttt{Q x y}\)，输出当前文本中区间 \([x,y]\) 内出现过的字母的种类数。
可以维护一个 bitset，记录哪些字母是出现过的。
push_up() 代码如下：
node* push_up()
{
siz=1;
chr.reset();
chr[c-'a']=1;
if(lc) siz+=lc->siz, chr|=lc->chr, lc->fa=this;
if(rc) siz+=rc->siz, chr|=rc->chr, rc->fa=this;
return this;
}
查询本身就很套路了：
int query(int l, int r)
{
node *a, *b, *c;
split(str, l-1, a, b);
split(b, r-l+1, b, c);
int ret=b->chr.count();
str=merge(merge(a, b), c);
str->fa=0;
return ret;
}
其他的都是 FHQ Treap 的基本操作，不多赘述。
Code
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
namespace Treap
{
mt19937 rnd(time(0));
struct node
{
uint64_t id;
int64_t siz=1;
node *lc=0, *rc=0, *fa=0;
char c;
bool del=0, rev=0;
bitset<26> chr;
node(char ch, uint64_t d): c(ch), id(d) {chr.reset(); chr[ch-'a']=1;}
void reverse() {swap(lc, rc); rev^=1;}
void push_down()
{
if(rev)
{
if(lc) lc->reverse();
if(rc) rc->reverse();
rev^=1;
}
}
node* push_up()
{
siz=1;
chr.reset();
chr[c-'a']=1;
if(lc) siz+=lc->siz, chr|=lc->chr, lc->fa=this;
if(rc) siz+=rc->siz, chr|=rc->chr, rc->fa=this;
return this;
}
};
node* new_node(char v) {return new node(v, rnd());}
#define siz(x) (x?x->siz:0)
void split(node *x, int s, node *&l, node *&r)
{
if(!x) return l=r=0, void();
x->push_down();
if(siz(x->lc)<s) l=x, split(x->rc, s-siz(x->lc)-1, x->rc, r);
else r=x, split(x->lc, s, l, x->lc);
x->push_up();
}
node* merge(node *x, node *y)
{
if(!x||!y) return x?x:y;
if(x->id<y->id)
{
x->push_down();
x->rc=merge(x->rc, y);
return x->push_up();
}
else
{
y->push_down();
y->lc=merge(x, y->lc);
return y->push_up();
}
}
void access(node *x)
{
if(!x) return;
access(x->fa);
x->push_down();
}
uint32_t find_pos(node *x)
{
if(x->del||!x) return 0;
access(x);
uint32_t res=siz(x->lc)+1;
while(x->fa)
{
if(x->fa->rc==x)
res+=siz(x->fa->lc)+1;
x=x->fa;
}
return res;
}
node *str;
void insert(int p, char c)
{
node *a, *b;
split(str, p, a, b);
str=merge(merge(a, new_node(c)), b);
str->fa=0;
}
void erase(int p)
{
node *a, *b, *c;
split(str, p-1, a, b);
split(b, 1, b, c);
b->del=1;
str=merge(a, c);
if(str) str->fa=0;
}
void reverse(int l, int r)
{
node *a, *b, *c;
split(str, l-1, a, b);
split(b, r-l+1, b, c);
b->reverse();
str=merge(merge(a, b), c);
str->fa=0;
}
char get(int p)
{
node *a, *b, *c;
split(str, p-1, a, b);
split(b, 1, b, c);
char ret=b->c;
str=merge(merge(a, b), c);
str->fa=0;
return ret;
}
int query(int l, int r)
{
node *a, *b, *c;
split(str, l-1, a, b);
split(b, r-l+1, b, c);
int ret=b->chr.count();
str=merge(merge(a, b), c);
str->fa=0;
return ret;
}
}
Treap::node *rt[maxn];
string s;
int main()
{
int n, m;
cin>>n>>m>>s;
for(int i=1;i<=n;i++)
rt[i]=Treap::new_node(s[i-1]),
Treap::str=merge(Treap::str, rt[i]);
while(m--)
{
char op;
int x, y;
char ch;
cin>>op>>x;
if(op=='I') cin>>ch, Treap::insert(x, ch);
if(op=='D') Treap::erase(x);
if(op=='R') cin>>y, Treap::reverse(x, y);
if(op=='P') cout<<Treap::find_pos(rt[x])<<'\n';
if(op=='T') cout<<Treap::get(x)<<'\n';
if(op=='Q') cin>>y, cout<<Treap::query(x, y)<<'\n';
}
}