线段树

对于单点修改区间查找，考虑线段树，维护最大字符在区间的最大位置和最小位置，和最大字符之间的位置最大值。最大字符之间的字符每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)
#define rs(i) (i<<1|1)
const int mod=998244353;
int a[N];
struct node
{	int l,r,mx,w,len;
}tr[N << 4];
node merge(node x,node y){
	if(x.mx==y.mx){
		x.len=max({x.len,y.l-x.r,y.len});
		x.r=y.r;
		return x;
	}
	else if(x.mx>y.mx){
		return x;
	}
	else{
		return y;
	}
}
struct st{
	void build(int l,int r,int i){
		if(l==r){
			tr[i].w=a[l];
			tr[i].mx=a[l];
			tr[i].l=l;
			tr[i].r=l;
			tr[i].len=0;
			return ;
		}
		int mid=(l+r)>>1;
		build(l,mid,ls(i));
		build(mid+1,r,rs(i));
		tr[i]=merge(tr[ls(i)],tr[rs(i)]);
	}
	void update(int pos,int w,int l,int r,int i){
		if(l==r){
			tr[i].w=w;
			tr[i].mx=w;
			tr[i].l=l;
			tr[i].r=l;
			tr[i].len=0;
			return;
		}
		int mid=(l+r)/2;
		if(pos<=mid) update(pos,w,l,mid,ls(i));
		else update(pos,w,mid+1,r,rs(i));
		tr[i]=merge(tr[ls(i)],tr[rs(i)]);
	}
	node query(int ql,int qr,int l,int r,int i){
		if(ql<=l&&r<=qr){
			return tr[i];
		} 
		int mid=(l+r)>>1;
		if(ql<=mid&&qr>mid){
			return merge(query(ql,qr,l,mid,ls(i)),query(ql,qr,mid+1,r,rs(i)));
		}
		if(ql<=mid){
			return query(ql,qr,l,mid,ls(i));
		}
		if(qr>mid){
			return query(ql,qr,mid+1,r,rs(i));
		}
	}
}zy;
void solve() {
	int n,q;
	cin>>n>>q;
	string s;
	cin>>s;
	s=' '+s;
	for(int i=1;i<=n;i++){
		a[i]=s[i]-'a'+1;
	}
	zy.build(1,n,1);
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			int id;
			char c;
			cin>>id>>c;
			int w=c-'a'+1;
			zy.update(id,w,1,n,1);
		}
		else{
			int l,r;
			cin>>l>>r;
			node ans=zy.query(l,r,1,n,1);
			cout<<max({ans.l-l,r-ans.r,ans.len/2})<<'\n';
		}
	}

}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	cin>>t;
	while(t--){
		solve();
	}
}

题目内容

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

具体表现为：每过一个单位时间，当前商家会被替代为和其相邻位置的最大商家。商家的大小根据$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$。