8.6晚 st表+树状数组

#include<bits/stdc++.h>
#define int long long  
using namespace std;

const int maxn=1e6+10;
int n,m;
int f[maxn][25];
int a[maxn];
int lg[maxn];
void q(){
	for(int i=1;i<=n;i++){
		f[i][0]=a[i];
	}
	for(int i=2;i<=n;i++){
		lg[i]=lg[i/2]+1;
	}
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	return ;
}
int get_ans(int l,int r){
	int len=r-l+1;
	int k=lg[len];
	return max(f[l][k],f[r-(1<<k)+1][k]);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	q();
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		cout<<get_ans(l,r)<<'\n';
	}
	return 0;
} 			

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn=5e4+10;
int n,m;
string  f[maxn][25];
string a[maxn],b[maxn];
int lg[maxn];
string daxiao(string s){
	int len=s.size();
	for(int i=0;i<len;i++){
		if(s[i]>='a'&&s[i]<='z'){
			s[i]-=32;
		}
	}
	return s;
}
void q(){
	for(int i=1;i<=n;i++){
		f[i][0]=a[i];
	}
	for(int i=2;i<=n;i++){
		lg[i]=lg[i/2]+1;
	}
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			if(daxiao(f[i][j-1])<=daxiao(f[i+(1<<(j-1))][j-1])){
				f[i][j]=f[i+(1<<(j-1))][j-1];
			}else{
				f[i][j]=f[i][j-1];
			}
		}
	}
	return ;
}
string get_ans(int l,int r){
	int len=r-l+1;
	int k=lg[len];
	if(f[l][k]<=f[r-(1<<k)+1][k]){
		return f[r-(1<<k)+1][k];
	}
	else return f[l][k];
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		a[i]=s;
	}
	q();
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		cout<<get_ans(l,r)<<'\n';
	}
	return 0;
} 			

string get_ans(int l,int r){
	int len=r-l+1;
	int k=lg[len];
	if(f[l][k]<=f[r-(1<<k)+1][k]){
		return f[r-(1<<k)+1][k];
	}
	else return f[l][k];
}

string get_ans(int l,int r){
	int len=r-l+1;
	int k=lg[len];
	if(daxiao(f[l][k])<=daxiao(f[r-(1<<k)+1][k])){//问题所在
		return f[r-(1<<k)+1][k];
	}
	else return f[l][k];
}