题目背景

滚粗了的HansBug在收拾旧英语书，然而他发现了什么奇妙的东西。

题目描述

udp2.T3如果遇到相同的字符串，输出后面的

蒟蒻HansBug在一本英语书里面找到了一个单词表，包含N个单词（每个单词内包含大小写字母）。现在他想要找出某一段连续的单词内字典序最大的单词。

输入输出格式

输入格式：

第一行包含两个正整数N、M，分别表示单词个数和询问个数。

接下来N行每行包含一个字符串，仅包含大小写字母，长度不超过15，表示一个单词。

再接下来M行每行包含两个整数x、y，表示求从第x到第y个单词中字典序最大的单词。

输出格式：

输出包含M行，每行为一个字符串，分别依次对应前面M个询问的结果。

输入输出样例

输入样例#1：

5 5

absi

hansbug

lzn

kkk

yyy

1 5

1 1

1 2

2 3

4 4

输出样例#1：

yyy

absi

hansbug

lzn

kkk

说明

样例说明：

第一次操作：在{absi,hansbug,lzn,kkk,yyy}中找出字典序最大的，故为yyy

第二次操作：在{absi}中找出字典序最大的，故为absi

第三次操作：在{absi,hansbug}中找出字典序最大的，故为hansbug

第四次操作：在{hansbug,lzn}中找出字典序最大的，故为lzn

第五次操作：在{kkk}中找出字典序最大的，故为kkk

数据规模：

洛谷P2412 查单词 [trie树 RMQ]

注意事项：1.该题目单词字典序比对过程中大小写不敏感，但是输出必须输出原单词

2.该题目时间限制为0.2s

此题暴力给字符串比较大小是玄学，80~AC

正解：trie树给字符串排序，st表做RMQ

先序遍历就是排序

一堆RE，结果发现len打成n了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=,L=;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,l,r;

char s[N][],a[];

int ch[N*L][],size=,val[N*L];

void insert(char s[],int n,int id){

    int u=;

    for(int i=;i<=n;i++){

        int v=s[i]-'a';

        if(!ch[u][v]) ch[u][v]=++size;

        u=ch[u][v];

    }

    val[u]=id;//printf("ins %d %d\n",u,id);

}

int rank[N],p=;

void dfs(int u){//printf("dfs %d\n",u);

    if(val[u]) rank[val[u]]=++p;

    for(int i=;i<;i++) if(ch[u][i]) dfs(ch[u][i]);

}

int mx[N][];

inline int maxs(int i,int j){return rank[i]>rank[j]?i:j;}

void initRMQ(){

    for(int i=;i<=n;i++) mx[i][]=i;

    for(int j=;j<=;j++)

        for(int i=;i+(<<j)-<=n;i++)

            mx[i][j]=maxs(mx[i][j-],mx[i+(<<(j-))][j-]);

}

inline int query(int l,int r){

    int k=log(r-l+)/log();

    return maxs(mx[l][k],mx[r-(<<k)+][k]);

}

int main(){

    n=read();m=read();

    for(int i=;i<=n;i++){

        scanf("%s",s[i]+);

        int len=strlen(s[i]+);

        for(int j=;j<=len;j++) a[j]=s[i][j]<'a'?s[i][j]+'a'-'A':s[i][j];

        insert(a,len,i);

    }

    dfs();//sort

    //for(int i=1;i<=n;i++) printf("%d %d\n",i,rank[i]);

    initRMQ();

    for(int i=;i<=m;i++){

        l=read();r=read();

        printf("%s\n",s[query(l,r)]+);

    }

}

秒客网