这是一道RMQ水题，因为本蒟蒻居然一A

题目描述

　　 张大牛：“我是天才！”

大肥熊：“你为什么是天才？”

张大牛：“你随便给我一个单词(大小写字母组成)长度为NN，去掉MM个字符后，我能知道字典序最小的字符串是什么样子的”

大肥熊：“换过来，现在假设这个字典序最小的字符串中第aiai个字符在原串中的位置为pospos，那么原串中区间[pos−ki,pos+ki][pos−ki,pos+ki]中字典序最大的字符是什么？”

张大牛又被难倒了。现在这个难倒天才的题目交到你手上了。

注：区间[pos−ki,pos+ki][pos−ki,pos+ki]超过原字符串的边界，按照原字符串的边界处理。原串的整个区间为[1,N][1,N]，如果pospos可以取多个值，按照最靠前的位置计算。

 

输入格式

第一行M,T。MM,T。M如题意，TT为TT组询问。

第二行为一个由大、小写字母组成的字符串。串的长度N（N>M>0）N（N>M>0）。

接下来TT行每行两个正整数ai，ki（1≤ai≤N−M），（1≤ki≤N）ai，ki（1≤ai≤N−M），（1≤ki≤N）。

输出格式

T行，每行对询问给出一个答案。

样例一

input

20 2abcdefghijklmnopqrstuvwxyz5 203 3

output

yf

限制与约定

对于100%的数据,N≤105,T≤105N≤105,T≤105

时间限制：1s1s

空间限制：256MB

这道题呢，涉及到两个知识点

1.单调栈+贪心

这个比较好理解，但是本蒟蒻还是询问了同桌大佬，才明白，这个的思路就是，每次来一个字符串，就从最顶上开始弹，只要顶上比当前大，就弹，然后维护一个cnt，使之只弹m次，最后剩下的一定是最优解，这个是比较纯粹的单调栈

这个的模板好像没有，我写的习惯就是用while循环维护

2.RMQ

RMQ适合于维护区间最值，预处理O（n），询问O（1）

这个属于ST（倍增）算法，就是一次跳2的j次个，和lca比较像，f[i][j]表示的是以i为起点，跳2的j次个，这个区间的最值，询问的时候只要从两个方向覆盖就OK

注意有的地方是否要+1-1，这个也比较好理解

 

然后呢这道题在单调栈弹栈入栈时候维护下位置就OK，然后再询问，是不是很水？

模板在此

1 for(int i=1;i<=n;i++)f[i][0]=a[1];2 for(int j=1;j<=log2(n);j++)3     for(int i=1;(i+(1<
     
      <=n;i++)4         f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);5 lg=log2(r-l+1);6 printf("%c\n",max(f[l][lg],f[r-(1<
     

代码在此，

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 int n,m,t,top,cnt,a,k; 7 int pos[100111]; 8 char s[100111],stk[100111],f[100111][20]; 9 int main()10 {11     //freopen("misaki.in","r",stdin);12     scanf("%d%d%s",&m,&t,s+1);13     n=strlen(s+1),stk[++top]=s[1],pos[1]=1,f[1][0]=s[1];14     for(int i=2;i<=n;i++)15     {16         while(top-1>=0 && stk[top]>s[i] && cnt+1<=m)top--,cnt++;17         stk[++top]=s[i],pos[top]=i;18         f[i][0]=s[i];19     }20     for(int j=1;j<=log2(n);j++)21         for(int i=1;(i+(1<
         
          <=n;i++)22             f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);23     for(int i=1;i<=t;i++)24     {25         scanf("%d%d",&a,&k);26         int l=max(1,pos[a]-k),r=min(n,pos[a]+k),lg=log2(r-l+1);27         printf("%c\n",max(f[l][lg],f[r-(1<