题目内容

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

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

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

线段树

对于单点修改区间查找，考虑线段树，维护最大字符在区间的最大位置和最小位置，和最大字符之间的位置最大值。最大字符之间的字符每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)