线段树

对于单点修改区间查找，考虑线段树，维护最大字符在区间的最大位置和最小位置，和最大字符之间的位置最大值。最大字符之间的字符每1秒有两个变成最大字符也就是长度/2，及其最大字符的最小及其最大位置左边和右边是1秒变一个，对于每个区间询问也就是回答上面三种最大值即可

代码如下

cpp

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+3 ;
#define int long long
#define ls(i) (i<<1)

题目内容

字符串中的字母可以形象的看作小美公司里的商家，有实力的商家能够不断的取代小的商家。

具体表现为：每过一个单位时间，当前商家会被替代为和其相邻位置的最大商家。商家的大小根据$Ascii$码顺序排序：$a<b<...<z$

为了提前制定防范措施，小美需要知道字符串$s$变为只含单个商家的最少单位时间。但是这样似乎难不倒你，所以小美会提出多个区间[l,r]的操作空间或询问，格式如下；

• 操作一：将字母串$s$的第$i$个商家替代为商家$p$；

• 操作二：询问当前字符串$s$的[$l,r$]这个区间变成单个商家需要的最少单位时间；每次操作二的询问均相互独立、互不影响；

  小美需要你帮助他完成这个任务

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤100$)代表数据组数，每组测试数据描述如下:

第一行输入两个整数$n,q$($1≤n,q≤2×10^5$)，字符串长度、操作次数。

第二行输入一个长度为$n$、且仅由小写字母构成的字符串$s$

此后$q$行,先输入一个整数$op$($1≤op≤2$)表示操作类型，随后：

• 当$op=1$时，在同一行上输入一个整数$i$和一个字符$p$($1≤i≤n;a≤p≤z$)表示把字符$s_i$修改为字符$P$

• 当$op=2$时，在同一行上输入两个整数$l,r$($1≤l≤r≤n$)表示询问的字符串区间。

  除此之外，保证所有的$n,q$之和均不超过$2×10^5$

输出描述

对于每个操作二，在一行上输出一个整数，代表当前询问区间内变成单个字符需要的最少单位时间。

样例1

输入

2
7 5
adbfdca
2 5 7
1 4 d
2 1 7
2 1 4
2 4 7
5 3
aaaaa
2 1 4
1 2 f
2 1 4

输出

2 
2
1
2
0
2

说明

对于第一组测试数据的第一次询问，区间为[$5,7$]：第一个单位时间，$s=ddc$、第二个单位时间，$s=ddd$。故最少单位时间为$2$。