经计算器计算得出，在 $n=50000,m=300000$ 时，此程序大约执行 $27386127$ 次操作，感觉可以卡卡常......

求大佬帮忙卡个常吧/kk/kk

另外，cincout已经关了缓冲区，应该和 scanf printf差不多(?)

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#define MAXN 50005
using namespace std;
int f[MAXN];
string a[MAXN],b[MAXN];
int n,m,sq;
struct node{
    int id;
    string st;
}maxx[MAXN];
bool operator<(string p,string q){
    int len1=p.length();
    int len2=q.length();
    int len=len1>len2?len2:len1;
    for(int i=0;i<len;i++){
        if(p[i]<q[i]){
            return true;
        }
        else if(p[i]>q[i]){
            return false;
        }
    }
    return len1<len2;
}
string change(string s){
    string r=s;
    int len=s.length();
    for(int i=0;i<len;i++){
        if(r[i]>='A'&&r[i]<='Z'){
            r[i]+='a'-'A';
        }
    }
    return r;
}
int query(int l,int r){
    string ans="";
    int res=-1;
    for(int i=l;i<=min(f[l]*sq,r);i++){
        if(ans<b[i]){
            ans=b[i];
            res=i;
        }
    }
    for(int i=f[l]+1;i<=f[r]-1;i++){
        if(ans<maxx[i].st){
            ans=maxx[i].st;
            res=maxx[i].id;
        }
    }
    if(f[l]!=f[r]){
        for(int i=(f[r]-1)*sq+1;i<=r;i++){
            if(ans<b[i]){
                ans=b[i];
                res=i;
            }
        }
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    sq=sqrt(n);
    for(int i=1;i<=n;i++){
        f[i]=(i-1)/sq+1;
        cin>>a[i];
        b[i]=change(a[i]);
        if(maxx[f[i]].st<b[i]){
            maxx[f[i]].st=b[i];
            maxx[f[i]].id=i;
        }
    }
    //print();
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<a[query(l,r)]<<endl;
    }
    return 0;
}

记录