Solution - AT5323

本文主要是介绍Solution - AT5323，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

分块好像不会被卡。

Solution.

我们可以用一个 \(b\) 数组来记录该块的每种字母的数量。
在每次查询的时候，我们可以新建一个桶，根据分块的基本思想，如果 \(l\) 和 \(r\) 在同一块，就直接将 \(l \sim r\) 之间的字母加入桶。否则就把 \(l\) 和 \(r\) 之间的块中的字母加入桶。最后枚举一下桶中有多少个不同的字母即可。

时间复杂度 \(O(26 × n \sqrt{n})\)

Code.

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int maxn = 1e6 + 5;
int n, q;
char s[maxn];
int op, l, r;
int pos[maxn], L[maxn], R[maxn];
int b[maxn][301];
int len, tot;
void init() {//分块
	len = sqrt(n);
	for (int i = 1; i + len <= n; i += len) {
		L[++tot] = i;
		R[tot] = i + len - 1;
	}
	if (R[tot] < n) {
		tot++;
		L[tot] = R[tot - 1] + 1;
		R[tot] = n;
	}
	for (int i = 1; i <= tot; i++) {
		for (int j = L[i]; j <= R[i]; j++) {
			pos[j] = i;
			b[i][s[j]]++;
		}
	}
}
void updata(int x, char c) {//单点修改
	b[pos[x]][s[x]]--;	
	s[x] = c;
	b[pos[x]][c]++; 
} 
bool p[301];
int ask(int l, int r) {
	int t1 = pos[l], t2 = pos[r], ans = 0;
	if (t1 == t2) {//如果在同一块
		memset(p, 0, sizeof(p));
		for (int i = l; i <= r; i++) {//直接将 l-r 加入
			if (!p[s[i]]) {
				p[s[i]] = true;
				ans++;
			}
		}
	} else {
		memset(p, 0, sizeof(p));
		for (int i = l; i <= R[t1]; i++) {
			if (!p[s[i]]) {
				p[s[i]] = true;
				ans++;
			}
		}
		for (int i = t1 + 1; i <= t2 - 1; i++) {//将块中的字母加入桶
			for (int j = 'a'; j <= 'z'; j++) {
				if (b[i][j] != 0) {
					if (!p[j]) {
						ans++;
						p[j] = true;
					}
				}
			}
		}
		for (int i = L[t2]; i <= r; i++) {
			if (!p[s[i]]) {
				p[s[i]] = true;
				ans++;
			}
		}
	}
	return ans;
}
signed main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> s[i];
	init();
	cin >> q;
	while (q--) {
		cin >> op;
		if (op == 1) {
			char c;
			cin >> l >> c;
			updata(l, c);
		} else if (op == 2) {
			cin >> l >> r;
			printf("%d\n", ask(l, r));
		}
	}
	return 0;
} 

这篇关于Solution - AT5323的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！