【算法精讲】洛谷P2412 区间最大字典序查询：ST表高效解法与C++实现

一、SEO化题目解读

洛谷P2412是一道字符串处理与区间查询结合的题目，要求在多个查询区间内找到字典序最大的字符串（不区分大小写）。题目考察ST表（稀疏表）数据结构的应用，是学习高效区间查询算法的典型案例。

二、解题思路（参考代码分析）

1. ‌ST表预处理‌：构建二维数组存储区间最值信息

2. ‌字典序比较‌：预处理小写版本字符串统一比较标准

3. ‌查询优化‌：利用ST表实现O(1)时间复杂度的区间查询

4. ‌边界处理‌：相同字典序时选择位置靠后的字符串

三、解题步骤详解

1. ‌输入处理‌：读取字符串数量和查询数量

2. ‌预处理阶段‌：

• 构建所有字符串的小写版本

• 初始化ST表第一层

• 动态填充ST表各层

3. ‌查询阶段‌：

• 计算查询区间的长度

• 分解区间为两个已知区间

• 比较并返回结果

4. ‌结果输出‌：直接输出查询结果

四、完整代码实现

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespACe std;

// 构建ST表
vector<vector<int>> buildST(const vector<string>& words) {
    int n = words.size();
    int k = log2(n) + 1;
    vector<vector<int>> st(n, vector<int>(k));
    
    // 预处理小写版本避免重复转换
    vector<string> lower_words(n);
    for(int i = 0; i < n; ++i) {
        lower_words[i].resize(words[i].size());
        transform(words[i].begin(), words[i].end(), 
                 lower_words[i].begin(), ::tolower);
    }

    for(int i = 0; i < n; ++i) st[i][0] = i;
    
    for(int j = 1; (1<<j) <= n; ++j) {
        for(int i = 0; i + (1<<j) - 1 < n; ++i) {
            int x = st[i][j-1];
            int y = st[i+(1<<(j-1))][j-1];
            st[i][j] = (lower_words[x] > lower_words[y] || 
                       (lower_words[x] == lower_words[y] && x > y)) ? x : y;
        }
    }
    return st;
}

// ST表查询函数
int query(const vector<vector<int>>& st, const vector<string>& words, 
          const vector<string>& lower_words, int l, int r) {
    int len = r - l + 1;
    int j = log2(len);
    int x = st[l][j];
    int y = st[r - (1<<j) + 1][j];
    return (lower_words[x] > lower_words[y] || 
           (lower_words[x] == lower_words[y] && x > y)) ? x : y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<string> words(n);
    
    for(int i = 0; i < n; ++i) {
        cin >> words[i];
    }
    
    auto st = buildST(words);
    vector<string> lower_words(n);
    for(int i = 0; i < n; ++i) {
        lower_words[i].resize(words[i].size());
        transform(words[i].begin(), words[i].end(), 
                 lower_words[i].begin(), ::tolower);
    }
    
    while(m--) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        int pos = query(st, words, lower_words, x, y);
        cout << words[pos] << '\n';
    }
    
    return 0;
}

五、总结

本文详细解析了洛谷P2412的ST表解法，通过预处理和空间换时间的策略，将区间查询时间复杂度优化到O(1)。该算法特别适合处理静态数据的多次区间查询问题，是竞赛编程中常用的高效算法之一。