思路：

输入字符串，sort 获得字典序，就变成了区间最大值查询问题。

样例过了，但是全 WA。

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

const int kMaxN = 5e5 + 7, kMaxM = kMaxN << 2;

int n, m, a[kMaxN], seg[kMaxN];
string s[kMaxN];
map<string, int> mp;

void Build(int l, int r, int p) {
    if (l == r) {
        seg[p] = a[l]; return;
    }
    int mid = l + r >> 1a;
    Build(l, mid, p << 1), Build(mid + 1, r, p << 1 | 1);
    seg[p] = max(seg[p << 1], seg[p << 1 | 1]);
}

int Query(int l, int r, int p, int s, int t) {
    int res = 0;
    if (s <= l && r <= t) {
        return seg[p];
    }
    int mid = l + r >> 1;
    if (s <= mid) {
        res = max(res, Query(l, mid, p << 1, s, t));
    }
    if (mid + 1 <= t) {
        res = max(res, Query(mid + 1, r, p << 1 | 1, s, t));
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        mp[s[i]] = i;
    }
    sort(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++) {
        a[mp[s[i]]] = i;
    }
    Build(1, n, 1);
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        cout << s[Query(1, n, 1, x, y)] << '\n';
    }

    return 0;
}