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

这是一道可癌的线段树题目。

前置知识

线段树

思路

先把所有字符都变成小写。

这道题线段树节点可以维护每个字符出现的次数之和，操作

1

和

2

是简单的区间查询和区间修改，操作

3

可以转化为区间查询和区间修改，设该区间每个小写字母的出现次数为

cnt_{字符序 - 97}

，那么前

cnt_{0}

个位置改成 a，

cnt_{0} + 1

到

cnt_{0} + cnt_{1}

改成 b，接下来以此类推。

时间复杂度

O(n \log n)

，还有个

26

的常数。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int n,Q;
string str;
namespace SegmentTree{
	struct node{
		int cnt[26];
		char tag;
	} tri[N << 2];
	int cnt[26];
	void build(int p,int l,int r){
		if(l == r){
			tri[p].cnt[str[l] - 'a'] ++;
			return;
		}
		int mid = (l + r) >> 1;
		build(p << 1,l,mid);
		build(p << 1 | 1,mid + 1,r);
		for(int i = 0;i < 26;i ++){
			tri[p].cnt[i] = tri[p << 1].cnt[i] + tri[p << 1 | 1].cnt[i];
		}
	}
	void pushdown(int p,int l,int r){
		if(tri[p].tag != 0 and l < r){
			int mid = (l + r) >> 1;
			memset(tri[p << 1].cnt,0,sizeof(tri[p << 1].cnt));
			memset(tri[p << 1 | 1].cnt,0,sizeof(tri[p << 1 | 1].cnt));
			tri[p << 1].cnt[tri[p].tag - 'a'] = mid - l + 1;
			tri[p << 1 | 1].cnt[tri[p].tag - 'a'] = r - mid;
			tri[p << 1].tag = tri[p].tag;
			tri[p << 1 | 1].tag = tri[p].tag;
			tri[p].tag = 0;
		}
	}
	void update(int p,int ql,int qr,int l,int r,char c){
		if(ql <= l and r <= qr){
			memset(tri[p].cnt,0,sizeof(tri[p].cnt));
			tri[p].cnt[c - 'a'] = r - l + 1;
			tri[p].tag = c;
			return;
		}
		pushdown(p,l,r);
		int mid = (l + r) >> 1;
		if(ql <= mid){
			update(p << 1,ql,qr,l,mid,c);
		}
		if(qr > mid){
			update(p << 1 | 1,ql,qr,mid + 1,r,c);
		}
		for(int i = 0;i < 26;i ++){
			tri[p].cnt[i] = tri[p << 1].cnt[i] + tri[p << 1 | 1].cnt[i];
		}
	}
	void query(int p,int ql,int qr,int l,int r){
		if(ql <= l and r <= qr){
			for(int i = 0;i < 26;i ++){
				cnt[i] += tri[p].cnt[i];
			}
			return;
		}
		pushdown(p,l,r);
		int mid = (l + r) >> 1;
		if(ql <= mid){
			query(p << 1,ql,qr,l,mid);
		}
		if(qr > mid){
			query(p << 1 | 1,ql,qr,mid + 1,r);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> Q >> str;
	str = ' ' + str;
	for(int i = 1;i <= n;i ++){
		str[i] = tolower(str[i]);
	}
	SegmentTree::build(1,1,n);
	while(Q --){
		int op;
		cin >> op;
		if(op == 1){
			int l,r;
			char c;
			cin >> l >> r >> c;
			c = tolower(c);
			memset(SegmentTree::cnt,0,sizeof(SegmentTree::cnt));
			SegmentTree::query(1,l,r,1,n);
			cout << SegmentTree::cnt[c - 'a'] << '\n';
		}else if(op == 2){
			int l,r;
			char c;
			cin >> l >> r >> c;
			c = tolower(c);
			SegmentTree::update(1,l,r,1,n,c);
		}else{
			int l,r;
			cin >> l >> r;
			memset(SegmentTree::cnt,0,sizeof(SegmentTree::cnt));
			SegmentTree::query(1,l,r,1,n);
			int pos = l;
			for(int i = 0;i < 26;i ++){
				if(SegmentTree::cnt[i] > 0){
					SegmentTree::update(1,pos,pos + SegmentTree::cnt[i] - 1,1,n,i + 'a');
					pos += SegmentTree::cnt[i];
				}
			}
		}
	}
	return 0;
}

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

文章操作

前置知识

思路

Code

相关推荐

评论

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