寻找区间最大字典序

一个优化小技巧。

题意很简单：

解法也很直观：ST表 or 线段树

但是无论是ST表还是线段树，直接做，这题都只能过掉 7/10 个点，卡常。
考虑到在线段树中，每一个位置存的都是 string 类型，每次都进行复制操作，时间复杂度常数大。于是考虑让线段树里存下 string 类型的地址，重写 str_max 函数，这样复制过程就大大减少了时间。

线段树代码：

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

const int N = 1e6 + 10;
int n, m;
string *tr[N << 2], a[N], init;

inline string* str_max(string *a, string *b){
    if(*a > *b) return a;
    return b;
}

void build(int u = 1, int cl = 1, int cr = n){
    if(cl == cr) return void(tr[u] = &a[cl]);
    int mid = cl + cr >> 1;
    build(u << 1, cl, mid);
    build(u << 1 | 1, mid + 1, cr);
    tr[u] = str_max(tr[u << 1], tr[u << 1 | 1]);
}

string* query(int l, int r, int u = 1, int cl = 1, int cr = n){
    if(l <= cl && cr <= r) return tr[u];
    int mid = cl + cr >> 1;
    string *mx = &init;
    if(mid >= l) mx = str_max(mx, query(l, r, u << 1, cl, mid));
    if(mid < r) mx = str_max(mx, query(l, r, u << 1 | 1, mid + 1, cr));
    return mx;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build();
    
    cin >> m;
    while(m--){
        int l, r; cin >> l >> r;
        for(auto &ch : *query(l, r)) putchar(ch);
        putchar('\n');
    } 
    
    return 0;
}

ST表优化同理，代码如下：

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

const int N = 1e6 + 10;
int log_2[N], n, m;
string* st[N][20], a[N];

inline string* str_max(string *a, string *b){
    if(*a > *b) return a;
    return b;
}

void initlog() {
    for (int i = 2; i < N; i++) log_2[i] = log_2[i >> 1] + 1;
}

void initst() {
    for(int i = 1; i <= n; i++){
        st[i][0] = &a[i];
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = str_max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
        }
    }
}

string* query(int l, int r) {
    int x = log_2[r - l + 1];
    return str_max(st[l][x], st[r - (1 << x) + 1][x]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    initlog(), initst();

    cin >> m;
    while (m--) {
        int l, r; cin >> l >> r;
        for(auto &ch : *query(l, r)) putchar(ch);
        putchar('\n');
    }

    return 0;
}