*：梦熊联盟 2024 CSP-S全真模拟 competition-2 A

不知道是思路错了还是写错了，反正我认识的人就我没 。

思路：

维护 $cntl_i$ 分别表示 $1\sim i$ 中满足 $x<y,s_x=s_y$ 且 $x+1\sim y-1$ 中没有小于 $s_x$ 的字符的二元组 $(x,y)$ 数量。

另维护类似的 $cntr_i$，表示 $i\sim n$ 中 $(x,y)$ 数量。

单次询问答案为 $n-(r-l+1)-cntl_{l-1}-cntr{r+1}$。

代码：

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
cll n=read();
ll q=read(),cnt[26],cntl[N],cntr[N];
char s[N];
int main()
{
	scanf("%s",s+1);
	for(rll i=1;i<=n;i++)
	{
		for(rll j=s[i]-'A'+1;j<26;j++)
			cnt[j]=0;
		cntl[i]=cntl[i-1]+cnt[s[i]-'A'];
		cnt[s[i]-'A']++;
	}
	for(rll i=0;i<26;i++)
		cnt[i]=0;
	for(rll i=n;i>=1;i--)
	{
		for(rll j=s[i]-'A'+1;j<26;j++)
			cnt[j]=0;
		cntr[i]=cntr[i+1]+cnt[s[i]-'A'];
		cnt[s[i]-'A']++;
	}
	while(q--)
	{
		cll l=read(),r=read();
		write(n-(r-l+1)-cntl[l-1]-cntr[r+1]),putchar('\n');
	}
    return 0;
}