题解

为了方便表示，我将以 $x$ 开头，$y$ 结尾的子串数量称为 $\{x,y\}$，数组 $a$ 中大于数 $x$ 的个数称为 $a.LB(x)$.

个人认为本次巅峰赛最难的一题！

认真读题，可发现题目实际让我们找的是如下的代码：

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        if(c[i] == c[j]) ct++;
    }
}

首先，我想到两个块合并只需要把左右两个块的 $\{x,y\}$ 相加再加上第一个块内 $x$ 的数量乘第二个块内 $y$ 的数量即可.

于是我轻松地打了个线段树代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#define int long long
using namespace std;
char c[100005];
int n, q;
int sum[26][262149];
int sum2[26][26][262149];
//sum[0] 记录数量 sum2块内值  
int size, depth;
void build(){//给出最后一层，O(n)建树 
	for(int i = size - 1; i; i--){
		for(int j = 0; j < 26; j++){
			sum[j][i] = sum[j][i * 2] + sum[j][i * 2 + 1];
		}
		for(int j = 0; j < 26; j++){
			for(int k = 0; k < 26; k++){
				sum2[j][k][i] = sum2[j][k][i * 2] + sum2[j][k][i * 2 + 1] + sum[j][i * 2] * sum[k][i * 2 + 1];//合并
			}
		}
	}
}

void modify(int i, int val){//O(logn)单点加 
	val -= 'a';
	sum[c[i] - 'a'][i + size] = 0;
	sum2[c[i] - 'a'][c[i] - 'a'][i + size] = 0;
	sum[val][i + size] = 1;
	sum2[val][val][i + size] = 1;
	c[i] = val + 'a';
	i += size;
	for(i >>= 1; i; i >>= 1){
		for(int j = 0; j < 26; j++){
			sum[j][i] = sum[j][i * 2] + sum[j][i * 2 + 1];
		}
		for(int j = 0; j < 26; j++){
			for(int k = 0; k < 26; k++){
				sum2[j][k][i] = sum2[j][k][i * 2] + sum2[j][k][i * 2 + 1] + sum[j][i * 2] * sum[k][i * 2 + 1];
			}
		}
	}
}

int query(char x, char y){
	return sum2[x - 'a'][y - 'a'][1];
}

signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	cin >> n >> q >> c;
	size = 1 << (depth = ceil(log2(n)) + 1e-5);
	for(int i = 0; i < n; i++){
		sum[c[i] - 'a'][i + size] = 1;
		sum2[c[i] - 'a'][c[i] - 'a'][i + size] = 1;
	}
	build();
	while(q--){
		int tmp;
		cin >> tmp;
		if(tmp == 1){
			int idx;
			char val;
			cin >> idx >> val;
			modify(idx - 1, val);
		}else{
			char c1, c2;
			cin >> c1 >> c2;
			cout << query(c1, c2) << '\n';
		}
	}

	return 0;
}

然后内存爆了.

后来我尝试用分块做，TLE了.

最后我使劲想想想，终于想出来了：

我们不需要维护整个线段树，真正需要维护的只是 $676$ 个结果.

我们可以换个角度考虑，如$aababb$，将第 $5$ 个字符改成 $a$：

先统计负贡献：

1. 在前四个字符与第五个字符的关系中，$\{a,b\}-=3$，$\{b,b\}-=1$.
2. 在第六个字符与第五个字符的关系中，$\{b,b\}-=1$.

再统计正贡献：

1. 在前四个字符与第五个字符的关系中，$\{a,a\}+=3$，$\{b,a\}+=1$.
2. 在第六个字符与第五个字符的关系中，$\{a,b\}+=1$.

我们发现，如果把这个字符串拆开，分为 $a$ 字符串与 $b$ 字符串：

aa a
  b bb

那么贡献就与 $5$ 在 $a$ 字符串与 $b$ 字符串的相对位置，即 $\sum\limits_{i\in b} a.LB(i)$ 有关.

其它的字符串也有这个性质，自行验证.

可以亮代码了……吗？

等等，还有两件事没讲清楚.

1.如何快速求 $a.LB(x)$:

如果按正常的数组处理的话，修改时间复杂度就得退化至 $O(n)$；

而 $set$ 只会给你返回迭代器，转换成数值又得花费 $O(n)$ 的时间.

怎么办呢？

机智的我想到了用树状数组模拟数组！只要每次加入元素在该元素的下标增加 $1$，删除元素在该元素的下标增加 $-1$，那么查询某个下标的结果就是 $a.LB(x)$！

使用这种方法也可以以 $O(n\log n)$​ 的时间复杂度求得一个数组的逆序对.

struct fenwickarray{//树状“数组” 
	int a[100005];
	int size = 0;
	void insert(int idx){//加入元素 
		size++;//修改元素数量
		for(; idx <= n; a[idx]++, idx += (idx & (-idx)));
	}
	void erase(int idx){//删除元素 
		size--;
		for(; idx <= n; a[idx]--, idx += (idx & (-idx)));
	}
	int lower_bound(int idx){//获取这个的相对位置 
		int ct = 0;
		for(; idx; ct += a[idx], idx -= (idx & (-idx)));
		return ct;
	}
};

2.初始化时间复杂度问题：

确实，通过上面的办法可以让修改变为 $O(\log n)$，查询变为 $O(1)$，但是要初始化. 而如果按照上面的代码初始化，时间复杂度是 $O(n^2)$！

没关系，稍微推导一下，就可以推出 $\{x,y\}=\sum\limits_{i\in y} x.LB(i)+(i\in x)$.

该题代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#define int long long
#pragma GCC optimize(2)
using namespace std;
char c[100005];
int ans[26][26];
int n, q;
struct fenwickarray{//树状“数组” 
	int a[100005];
	int size = 0;
	void insert(int idx){//加入元素 
		size++;//修改元素数量
		for(; idx <= n; a[idx]++, idx += (idx & (-idx)));
	}
	void erase(int idx){//删除元素 
		size--;
		for(; idx <= n; a[idx]--, idx += (idx & (-idx)));
	}
	int lower_bound(int idx){//获取这个的相对位置即lower_bound
		int ct = 0;
		for(; idx; ct += a[idx], idx -= (idx & (-idx)));
		return ct;
	}
}a[26];
vector <int> orgin[26];//记录初始的元素 
void modify(int idx, char val){
	val -= 'a';

	for(int i = 0; i < 26; i++) ans[i][c[idx] - 'a'] -= a[i].lower_bound(idx);//计算贡献
	for(int i = 0; i < 26; i++) ans[c[idx] - 'a'][i] -= a[i].size - a[i].lower_bound(idx);
	
	a[c[idx] - 'a'].erase(idx);//删除
	a[val].insert(idx);//加入
	
	for(int i = 0; i < 26; i++) ans[i][val] += a[i].lower_bound(idx);
	for(int i = 0; i < 26; i++) ans[val][i] += a[i].size - a[i].lower_bound(idx);
	 
	c[idx] = val + 'a';//最后别忘了修改！
}
int query(char x, char y){
	return ans[x - 'a'][y - 'a'];//直接返回答案即可
}
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	cin >> n >> q >> c + 1;
	for(int i = 1; i <= n; i++){
		a[c[i] - 'a'].insert(i);//加入进去 
		orgin[c[i] - 'a'].push_back(i);
	}
	for(int i = 0; i < 26; i++){
		for(int j = 0; j < 26; j++){
			for(int k:orgin[i]){//直接遍历原来的，减少常数项大小
				ans[i][j] += (a[j].size - a[j].lower_bound(k) + (c[k] == j + 'a'));//初始化
			}
		}
	}
	
	while(q--){
		int tmp;
		cin >> tmp;
		if(tmp == 1){
			int idx;
			char val;
			cin >> idx >> val;
			modify(idx, val);
		}else{
			char c1, c2;
			cin >> c1 >> c2;
			cout << query(c1, c2) << '\n';
		}
	}

	return 0;
}