自动搬运

查看原文

来自洛谷，原作者为

	George1123 **

搬运于2025-08-24 22:08:21，当前版本为作者最后更新于2020-05-16 11:38:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\Huge \texttt{My Cnblogs}$

---

洛谷P5217 贫穷

给定长度为 $n$ 的初始文本 $s$，有 $m$ 个如下操作：

1. $\texttt{I x c}$，在第 $x$ 个字母后面插入一个 $c$。
2. $\texttt{D x}$，删除第 $x$ 个字母。
3. $\texttt{R x y}$，反转当前文本中的区间 $[x,y]$。
4. $\texttt{P x}$，输出初始文本中第 $x$ 个字母在当前文本中的位置。特别地，若不存在，输出 $0$。
5. $\texttt{T x}$，输出当前文本中第 $x$ 个字母。
6. $\texttt{Q x y}$，输出当前文本中区间 $[x,y]$ 内出现过的字母的种类数。

数据范围：$1\le n,m\le 10^5$。

---

初学平衡树的蒟蒻太蒟蒻了，这题做了 $5$ 个小时。

蒟蒻是用 $\tt fhqTreap$ 做的，虽然对付这题 $\tt Splay$ 更自然，但是 $\tt fhqTreap$ 代码短。

---

• 维护节点信息：

const int N=1e5,T=2e5;
// N为初始文本长度，T为平衡树节点最大个数
int o[N+7];
// 记录每个初始文本字母对应的平衡树节点
int sz[T+7],fa[T+7],ls[T+7],rs[T+7],v[T+7],sm[T+7],p[T+7],mk[T+7];
// sz：节点的子树大小
// fa：节点的父亲节点，用于4操作中求rank
// ls/rs：左右儿子节点
// v：该节点对应的字母（-'a'）
// sm：子树的字母总集状压（0<=sm[x]<(1<<26)）
// p：fhqTreap精华随机数权值（用于维护堆）
// mk：翻转标记，用于解决3操作

---

• $\tt fhqTreap$ 基本操作：

void up(int x){
	if(ls[x]) fa[ls[x]]=x;
	if(rs[x]) fa[rs[x]]=x;
	sz[x]=sz[ls[x]]+sz[rs[x]]+1;
	sm[x]=sm[ls[x]]|sm[rs[x]]|1<<v[x];
}
void down(int x){if(mk[x]) swap(ls[x],rs[x]),mk[ls[x]]^=1,mk[rs[x]]^=1,mk[x]=0;} 
int wen(int x,int y=rand()){return v[++cnt]=x,p[cnt]=y,up(cnt),cnt;}
int merge(int x,int y){
	if(!x||!y) return x^y;
	if(p[x]<p[y]) return down(x),rs[x]=merge(rs[x],y),up(x),x;
	return down(y),ls[y]=merge(x,ls[y]),up(y),y;
}
void split(int u,int k,int&x,int&y){
	if(!u) return void(x=y=0);
	down(u); //这东西一定要写在这里，要不然不知道ls[u]是不是真的ls[u]
	if(k<=sz[ls[u]]) y=u,split(ls[y],k,x,ls[y]),fa[x]=0;
	else x=u,split(rs[x],k-sz[ls[u]]-1,rs[x],y),fa[y]=0;
	up(u);
}

---

• 题目中的操作：

$\color{#44a897}{\texttt{[0]}}$ 插入文本： 野蛮 $\tt merge$。

for(int i=1;i<=n;i++) rt=merge(rt,o[i]=wen(s[i]-'a'));

$\color{#44a897}{\texttt{[1]}}$ 插入字符： 套路 $\tt split$，套路 $\tt merge$。

scanf("%d %s",&a,&c[1]);
split(rt,a,L,R);
rt=merge(merge(L,wen(c[1]-'a')),R);

$\color{#44a897}{\texttt{[2]}}$ 删除字符： 先把节点分裂出来，然后把两边合并。为了操作 $4$ 可以看出一个点是否被删，在被删节点权值上做标记。

scanf("%d",&a);
split(rt,a,L,R),split(L,a-1,L,M);
v[M]=-1,rt=merge(L,R);

$\color{#44a897}{\texttt{[3]}}$ 翻转区间： 先把区间分裂出来，然后打翻转标记，最后不忘把树合回去。

scanf("%d%d",&a,&b);
split(rt,b,L,R),split(L,a-1,L,M);
mk[M]^=1,rt=merge(merge(L,M),R);

$\color{#44a897}{\texttt{[4]}}$ 查询排名： 如果节点权值有删除标记输出 $0$。否则先把节点到根的路径从上到下下放标记，然后从下向上求该节点前面的节点数。

void updown(int x){if(fa[x]) updown(fa[x]);down(x);}
int frank(int x){
	updown(x);
	int res=sz[ls[x]]+1;
	for(int i=x;fa[i];i=fa[i])if(rs[fa[i]]==i) res+=sz[ls[fa[i]]]+1;
	return res;
}

scanf("%d",&a);
if(v[o[a]]==-1) puts("0");
else printf("%d\n",frank(o[a]));

$\color{#44a897}{\texttt{[5]}}$ 输出位置字母： 相当于求个 $\tt kth$，可以套路 $\tt split$ 求。

scanf("%d",&a);
split(rt,a,L,R),split(L,a-1,L,M);
printf("%c\n",'a'+v[M]);
rt=merge(merge(L,M),R);

$\color{#44a897}{\texttt{[6]}}$ 区间字母种类： 先把区间分裂出来，答案即分裂出的根节点的子树字母集状压中的 $1$ 的个数。

scanf("%d%d",&a,&b);
split(rt,b,L,R),split(L,a-1,L,M);
printf("%d\n",bit(sm[M])),rt=merge(merge(L,M),R);

---

• 调试与解释

$\color{#efca55}{\texttt{[1]}}$ 输出当前字符串： 求平衡树的中序遍历，写个 $\tt Dfs$。

void Print(int x){
	down(x);
	if(ls[x]) Print(ls[x]);
//	printf("[%d<-%d->%d] (sz%d,v[%c],p%d,fa%d)\n",ls[x],x,rs[x],sz[x],v[x]+'a',p[x],fa[x]);
	printf("%c",v[x]+'a');
	if(rs[x]) Print(rs[x]);
}

$\color{#efca55}{\texttt{[2]}}$ 为什么有些时候写了 $\tt Print$ 就对了，注释掉就挂了： $\tt Print$ 函数帮你把整棵树的翻转标记下放了，如果出现这种情况说明你的操作过程中标记下放不完全。如果要验证你的代码除了标记下放都是正确的，可以把 $\tt Print$ 中的输出去掉，每次操作完都 $\tt Print$，然后交一发，如果 $\tt ac$ 两个点，$\tt tle$ 八个点，说明你的代码除了标记下放都是正确的。

---

好了结束了，蒟蒻又写了一篇无意义题解，放代码吧：

#include <bits/stdc++.h>
using namespace std;

//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair(a,b)
#define x(a) a.first
#define y(a) a.second
#define b(a) a.begin()
#define e(a) a.end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

//Data
const int N=1e5,T=2e5;
int n,m,o[N+7];
char s[N+7],c[3];
int bit(int x){return x?bit(x-(x&-x))+1:0;}

//Fhqtreap
int rt,cnt,sz[T+7],fa[T+7],ls[T+7],rs[T+7],v[T+7],sm[T+7],p[T+7],mk[T+7];
void up(int x){
	if(ls[x]) fa[ls[x]]=x;
	if(rs[x]) fa[rs[x]]=x;
	sz[x]=sz[ls[x]]+sz[rs[x]]+1;
	sm[x]=sm[ls[x]]|sm[rs[x]]|1<<v[x];
}
void down(int x){if(mk[x]) swap(ls[x],rs[x]),mk[ls[x]]^=1,mk[rs[x]]^=1,mk[x]=0;}
int wen(int x,int y=rand()){return v[++cnt]=x,p[cnt]=y,up(cnt),cnt;}
int merge(int x,int y){
	if(!x||!y) return x^y;
	if(p[x]<p[y]) return down(x),rs[x]=merge(rs[x],y),up(x),x;
	return down(y),ls[y]=merge(x,ls[y]),up(y),y;
}
void split(int u,int k,int&x,int&y){
	if(!u) return void(x=y=0);
	down(u);
	if(k<=sz[ls[u]]) y=u,split(ls[y],k,x,ls[y]),fa[x]=0;
	else x=u,split(rs[x],k-sz[ls[u]]-1,rs[x],y),fa[y]=0;
	up(u);
}
void updown(int x){if(fa[x]) updown(fa[x]);down(x);}
int frank(int x){
	updown(x);
	int res=sz[ls[x]]+1;
	for(int i=x;fa[i];i=fa[i])if(rs[fa[i]]==i) res+=sz[ls[fa[i]]]+1;
	return res;
}
void Print(int x){
	down(x);
	if(ls[x]) Print(ls[x]);
//	printf("[%d<-%d->%d] (sz%d,v[%c],p%d,fa%d)\n",ls[x],x,rs[x],sz[x],v[x]+'a',p[x],fa[x]);
	printf("%c",v[x]+'a');
	if(rs[x]) Print(rs[x]);
}

//Main
int main(){
	scanf("%d%d\n%s",&n,&m,&s[1]);
	for(int i=1;i<=n;i++) rt=merge(rt,o[i]=wen(s[i]-'a'));
//	puts("now---");
//	Print(rt); puts("");
//	puts("++++++");
	for(int i=1,a,b,L,M,R;i<=m;i++){
		scanf("\n%s ",&c[1]);
		if(c[1]=='I'){
			scanf("%d %s",&a,&c[1]);
			split(rt,a,L,R);
			rt=merge(merge(L,wen(c[1]-'a')),R);
		} else if(c[1]=='D'){
			scanf("%d",&a);
			split(rt,a,L,R),split(L,a-1,L,M);
			v[M]=-1,rt=merge(L,R);
		} else if(c[1]=='R'){
			scanf("%d%d",&a,&b);
			split(rt,b,L,R),split(L,a-1,L,M);
			mk[M]^=1,rt=merge(merge(L,M),R);
		} else if(c[1]=='P'){
			scanf("%d",&a);
			if(v[o[a]]==-1) puts("0");
			else printf("%d\n",frank(o[a]));
		} else if(c[1]=='T'){
			scanf("%d",&a);
			split(rt,a,L,R),split(L,a-1,L,M);
			printf("%c\n",'a'+v[M]);
			rt=merge(merge(L,M),R);
		} else if(c[1]=='Q'){
			scanf("%d%d",&a,&b);
			split(rt,b,L,R),split(L,a-1,L,M);
			printf("%d\n",bit(sm[M])),rt=merge(merge(L,M),R);
		}
//		puts("now---");
//		Print(rt); 
//		puts("");
//		puts("++++++");
	}
	return 0;
}

---

祝大家学习愉快！