luogu P2412 【查单词】

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
inline int read(){
    register int x=0,v=1,ch=getchar();
    while(!isdigit(ch)){if(ch==‘-‘)v=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^‘0‘);ch=getchar();}
    return x*v;
}
const int MAX=50005;
int n,m,op[MAX];
struct Node{
    string s;
    int p,t;//分别表示原来的位置和字典序排名
}a[MAX];

//两个cmp过程，第一个是获取字典序的排名，第二个是将序列还原

inline bool cmp(Node x,Node y){return x.s<y.s;}
inline bool comp(Node x,Node y){return x.p<y.p;}

int tree[MAX<<2];
inline int Max(int a,int b){
    return a>b?a:b;
}

//以下至58行是线段树的过程

inline void pushup(int x){
    tree[x]=Max(tree[x<<1],tree[x<<1|1]);
}
void build(int x,int l,int r){
    if(l==r){
        tree[x]=a[l].t;
        return ;
    }
    register int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
int query(int x,int l,int r,int s,int t){
    if(s<=l&&r<=t)return tree[x];
    register int mid=l+r>>1,res=-0x7fffffff;
    if(s<=mid)res=Max(res,query(x<<1,l,mid,s,t));
    if(mid<t)res=Max(res,query(x<<1|1,mid+1,r,s,t));
    return res;
}
int l,r;
string c[MAX];
int main(){
    n=read();m=read();
    for(register int i=1;i<=n;++i){
        cin>>a[i].s;
        c[i]=a[i].s;
        a[i].p=i;   
    }
    for(register int i=1;i<=n;++i){//字典序大小转换
        for(register int j=0;j<a[i].s.length();++j){
            if(‘a‘<=a[i].s[j]&&a[i].s[j]<=‘z‘)a[i].s[j]-=32;
        }
    }
    sort(a+1,a+1+n,cmp);
    for(register int i=1;i<=n;++i)a[i].t=i;
    sort(a+1,a+1+n,comp);
    for(register int i=1;i<=n;++i)op[a[i].t]=i,a[i].s=c[i];
   //op将查询到的最大排名映射回原来的查询字符串，c用于将a的字符串还原
    build(1,1,n);
    while(m--){
        l=read(),r=read();
        printf("%s\n",a[op[query(1,1,n,l,r)]].s.c_str());//输出字符串
    }
    return 0;
}