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

1. 题意解释

给出一个字符串，你可以对其进行以下三种操作：

获取第 $x$ 到第 $y$ 个字符中字母 $k$ 出现了多少次。
将第 $x$ 到第 $y$ 个字符全部赋值为字母 $k$ 。
将第 $x$ 到第 $y$ 个字符按照 $a∼z$ 的顺序排序。

2. 题意解释

把字符串看错一个由字符组成的数组，这道题就成了区间覆盖+区间排序问题。

容易想到用线段树解决。

每个线段维护一个

cnt

数组和

tag

标记，

cnt_i

表示第

i

个字母出现的次数，

tag

表示这个区间内的所有字母都为同一个值，即编号为

tag

的字母。

这样一来操作一和操作二就是区间查询和区间覆盖，重点考虑操作三。

由于值域是有限的，我们不难想到桶排序。

而且我们的线段树已经维护了区间内的桶。

于是我们也就可以区间查询+区间覆盖解决区间排序问题。

到现在，这道题就成线段树板子题了。

不理解的同学看代码注释噻。

3. 代码实现

一个需要注意的点：输入中可能同时出现大小写字母，记住把它们全部转化为统一的大写或小写！

AC code：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,op,x,y;
char k;
string s;
struct segtree{
	int l,r,cnt[30],tag;
}t[200200];
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].tag=0;
	if(l==r){
		t[p].cnt[s[l-1]-'A'+1]=1;
		return ;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	for(int i=1;i<=26;i++){
		t[p].cnt[i]=t[p*2].cnt[i]+t[p*2+1].cnt[i];
	}
}
void pushdown(int p){//懒标记下传
	if(t[p].tag){
		t[p*2].cnt[t[p].tag]=t[p*2].r-t[p*2].l+1;
		t[p*2+1].cnt[t[p].tag]=t[p*2+1].r-t[p*2+1].l+1;//子节点计数更新，将编号为 tag 的字母数更新为区间长度（因为区间被这个字母覆盖了）
		for(int i=1;i<=26;i++){
			if(i!=t[p].tag){
				t[p*2].cnt[i]=0;
				t[p*2+1].cnt[i]=0;
			}
		}////子节点计数更新，其余字母数量全部为0
		t[p*2].tag=t[p].tag;
		t[p*2+1].tag=t[p].tag;//标记下传
		t[p].tag=0;//父节点标记清空
	}
}
void change(int p,int l,int r,int c){//区间覆盖
	if(l>r){
		return ;
	}
	if(l<=t[p].l&&t[p].r<=r){
		t[p].tag=c;
		t[p].cnt[c]=t[p].r-t[p].l+1;
		for(int i=1;i<=26;i++){
			if(i!=c){
				t[p].cnt[i]=0;
			}
		}//更新标记和计数，原有的标记直接覆盖
		return ; 
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid){
		change(p*2,l,r,c);
	}
	if(r>mid){
		change(p*2+1,l,r,c);
	} 
	for(int i=1;i<=26;i++){
		t[p].cnt[i]=t[p*2].cnt[i]+t[p*2+1].cnt[i];
	}
}
int ask(int p,int l,int r,int c){//区间查询
	if(l<=t[p].l&&t[p].r<=r){
		return t[p].cnt[c];
	}
	pushdown(p); 
	int mid=(t[p].l+t[p].r)>>1,val=0;
	if(l<=mid){
		val+=ask(p*2,l,r,c);
	}
	if(r>mid){
		val+=ask(p*2+1,l,r,c);
	}
	return val;
}
int main(){
	cin>>n>>m;
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]>='a'&&s[i]<='z'){
			s[i]=s[i]+'A'-'a';
		}
	}//记得把字符串统一转换为大写或小写，我这里用的是大写
	build(1,1,n);
	for(int i=1;i<=m;i++){
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			if(k>='a'&&k<='z'){
				k=k+'A'-'a';//把字母转换为大写
			}
			cout<<ask(1,x,y,k-'A'+1)<<endl;
		}
		if(op==2){
			cin>>x>>y>>k;
			if(k>='a'&&k<='z'){
				k=k+'A'-'a';//把字母转换为大写
			}
			change(1,x,y,k-'A'+1);
		}
		if(op==3){
			cin>>x>>y;
			int num[30];
			memset(num,0,sizeof num);
			for(int i=1;i<=26;i++){
				num[i]=num[i-1]+ask(1,x,y,i);
			}//查询前i个字母的数量总和，方便下面更新
			for(int i=1;i<=26;i++){
				change(1,x+num[i-1],x+num[i]-1,i);
			}//更新整个区间内的字母，第i个字母的范围为x+num[i-1]至x+num[i]-1
		}
	}
	return 0;
}

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

文章操作

1. 题意解释

2. 题意解释

3. 代码实现

相关推荐

评论

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