codeforce Gym - 101061E (ST 表)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define d(x) cout<<(x)<<endl
const int N = 1e5 + 10;

int t, n, len, c1, c2;
char a[N];
int st1[N][30], st2[N][30];

void init(){
    memset(st1, 0, sizeof(st1));
    memset(st2, 0, sizeof(st2));
    for(int i = 1; i <= len; i++){
        st1[i][0] = st2[i][0] = i;
    }
    for(int j = 1; (1<<j) <= len; j++){
        for (int i = 1; i + (1 << j) - 1 <= len; i++){
            int x = st1[i][j - 1], y = st1[i + (1 << (j-1))][j - 1];
            st1[i][j] = a[x] <= a[y] ? x : y;   // 最小
            x = st2[i][j - 1], y = st2[i + (1 << (j-1))][j - 1];
            st2[i][j] = a[x] >= a[y] ? x : y;   // 最大
        }
    }
}

int ask1(int l, int r){
    int k = log2(r-l+1);
    int x = st1[l][k], y = st1[r - (1 << (k)) + 1][k];
    return a[x] <= a[y] ? x : y;
}

int ask2(int l, int r){
    int k = log2(r-l+1);
    int x = st2[l][k], y = st2[r - (1 << (k)) + 1][k];
    return a[x] >= a[y] ? x : y;
}

void cal1(){
    if(n >= c2){
        for(int i = 1; i <= len-n; i++){
            printf("%c", a[i]);
        }
    }else{
        for(int i = 1; i <= c1; i++){
            printf("%c", a[i]);
        }
        int num = c2 - n;
        int s = c1 + 1;
        int e = len - num + 1;
        while(e <= len){
            int k = ask1(s, e);
            // cout << s << " " << e << endl;
            printf("%c", a[k]);
            s = k+1;
            e++;
        }
    }
    printf("\n");
}

void cal2(){
    if(n <= c1){
        for(int i = n+1; i <= len; i++){
            printf("%c", a[i]);
        }
    }else{
        n -= c1;
        int s = c1 + 1;
        int e = c1+n+1;
        while(e <= len){
            int k = ask2(s, e);
            // cout << s << " " << e << endl;
            printf("%c", a[k]);
            s = k+1;
            e++;
        }
    }
    printf("\n");
}

int main()
{
    scanf("%d", &t);
    getchar();
    while(t--){
        scanf("%s%d", a+1, &n);
        len = strlen(a+1);
        init();
        int k = 0;              // 最后一个 0
        for (int i = 1; i <= len; i++){
            if(a[i] != '0'){
                k = i - 1;
                break;
            }
        }
        c1 = k - 0, c2 = len - c1;
        cal1();
        cal2();
    }
    return 0;
}