题解：P2787 语文1（chin1）- 理理思维

xyx4042025-06-062025-06-06

引用站外地址，不保证站点的可用性和安全性

洛谷文章链接

xyx404

发现题解区的线段树题解都是建 $26$ 棵线段树的方法，来一个不建 $26$ 棵线段树的线段树题解。_{本题思路其实来源于上课老师讲了这题，并且用的是本题解的方法。}

思路：

线段树。

本题除了操作三以外是模版，本题解主要讲操作三，没学过线段树出门右转线段树模版。

我们知道线段树把区间全部修改成同一个值是很简单的，但是本题操作三是要求排序，很可能是修改成不同的值，怎么办呢？我们可以想到既然是要求排序，那么排序后的值是不是连续的，既然是连续的，那是不是可以把它转换为一个普通的区间修改。

考虑把要排序的范围里的所有字母的数量求出来，然后按顺序枚举每个字母，确定排序后被排到了哪个范围，然后正常区间修改就好了。

如何确定被排序后在哪个范围内？首先设现在的起点为 $st$ ，有 $num$ 个这个字母，那么修改的这个区间大小也是 $num$ ，但是因为起点也算是占了区间的一个大小，所以终点是 $st+num-1$ 。

完整代码：

// 本代码经过 devc++ 自带的格式化格式化
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
struct node {
	int cnt[40];// 保存字母出现个数
	int tag;// 懒标记标记要换成什么字母
	int l,r;
	node()
	{
		l=r=0;
		tag=-1;
		memset(cnt,0,sizeof cnt);
	}
} tree[(55000)*4];
int n,m;
string s;
int op;
int x,y;
char k;
int cnt[40];// 保存字母出现个数，用于操作三，定义全局变量，函数内也可以访问
int szid(char s)
{
	return toupper(s)-'A';   // 把字母转换为 cnt 内对应下标
}
void push_up(int now)
{
	for(int i=0; i<=27; i++) {
		tree[now].cnt[i]=tree[now*2].cnt[i]+tree[now*2+1].cnt[i];
	}
	return;
}
void push_down(int now)
{
	if(tree[now].tag!=-1) {
		memset(tree[now*2].cnt,0,sizeof tree[now*2].cnt);
		memset(tree[now*2+1].cnt,0,sizeof tree[now*2+1].cnt);
		tree[now*2+1].tag=tree[now*2].tag=tree[now].tag;
		tree[now*2+1].cnt[tree[now].tag]=tree[now*2+1].r-tree[now*2+1].l+1;
		tree[now*2].cnt[tree[now].tag]=tree[now*2].r-tree[now*2].l+1;
		tree[now].tag=-1;
	}
}
void build(int now,int l,int r)
{
	if(l>r)return;
	tree[now].l=l;
	tree[now].r=r;
	if(l==r) {
		tree[now].cnt[szid(s[l])]++;
		return;
	}
	int mid=(l+r)>>1;
	build(now*2,l,mid);
	build(now*2+1,mid+1,r);
	push_up(now);
	return;
}
void query_cx(int now,int nl,int nr)
{
	int l=tree[now].l,r=tree[now].r;
	if(nl<=l&&nr>=r) {
		for(int i=0; i<=27; i++) {
			cnt[i]+=tree[now].cnt[i];
		}
		return;
	}
	push_down(now);
	int mid=(l+r)>>1;
	if(mid>=nl)query_cx(now*2,nl,nr);// l,mid
	if(mid<nr)query_cx(now*2+1,nl,nr);// mid+1 r
	return;
}
void change(int now,int nl,int nr,int k)
{
	int l=tree[now].l,r=tree[now].r;
	if(nl<=l&&nr>=r) {
		memset(tree[now].cnt,0,sizeof tree[now].cnt);
		tree[now].cnt[k]=r-l+1;
		tree[now].tag=k;
		return;
	}
	push_down(now);
	int mid=(l+r)>>1;
	if(mid>=nl)change(now*2,nl,nr,k);
	if(mid<nr)change(now*2+1,nl,nr,k);
	push_up(now);
	return;
}
void change_px(int nl,int nr)
{
	int start=nl;
	for(int i=0; i<=27; i++) {
		if(cnt[i]==0)continue;
		change(1,start,start+cnt[i]-1,i);// 确定修改范围，使用 change 函数
		start+=cnt[i];// 更新起点
	}
	return;
}
int query(int now,int nl,int nr,int k)
{
	int l=tree[now].l,r=tree[now].r;
	if(nl<=l&&nr>=r) {
		return tree[now].cnt[k];
	}
	push_down(now);
	int mid=(l+r)>>1;
	int ans=0;
	if(mid>=nl)ans+=query(now*2,nl,nr,k);// l,mid
	if(mid<nr)ans+=query(now*2+1,nl,nr,k);// mid+1 r
	return ans;
}
int main()
{
	cin>>n>>m>>s;
	s=" "+s;
	build(1,1,n);
	while(m--) {
		cin>>op;
		if(op==1) {
			cin>>x>>y>>k;
			cout<<query(1,x,y,szid(k))<<"\n";
		} else if(op==2) {
			cin>>x>>y>>k;
			change(1,x,y,szid(k));
		} else {
			cin>>x>>y;
			memset(cnt,0,sizeof cnt);
			query_cx(1,x,y);// 查询每个字母出现的次数
			change_px(x,y);
		}
	}
	return 0;
}