题目分析

给定两种操作：

1. 插入操作：记录一个字符串的所有可能通配模式（通过将若干字符替换为*）对应的最小数值。
2. 查询操作：查找与目标字符串匹配的所有通配模式中的最小数值，匹配度越高（替换*越少）的模式优先返回。

解决思路

利用字符串长度最多为$5$的特性，通过状态压缩枚举所有可能的通配模式：

1. 状态定义：每个字符可以是a-z或*（共27种可能），5个字符的状态可表示为27进制数，总状态数为27^5 ≈ 1.5×10^6，可通过数组直接存储。
2. 通配模式生成：通过$DFS$枚举将原字符串中$0 - 5$个字符替换为*的所有可能模式，每种模式对应一个唯一的$27$进制状态码。
3. 插入操作：对每个模式，记录其对应的最小数值。
4. 查询操作：按替换*的次数从小到大（即匹配度从高到低）枚举模式，找到第一个存在的有效状态并返回其最小数值。

关键步骤

1. 字符串转状态码：
   将字符a-z映射为0-25，*映射为26，按27进制累加生成唯一状态码，例如"a*b"转换为0*27² + 26*27 + 1。

2. DFS生成通配模式：
   递归替换字符串中的字符为*，确保每个位置仅处理一次（避免重复模式），生成所有可能的通配模式（替换0到5个字符）。

3. 状态存储与查询：

   • 插入时，对每个生成的模式更新其最小数值（避免重复存储较大值）。
   • 查询时，优先检查替换次数少的模式（即原字符串保留更多字符，匹配度更高），一旦找到有效状态立即返回，确保高效性。

复杂度分析

• 时间复杂度：每次操作的时间复杂度为O(2^5 × 5 × q)（枚举5个字符的替换状态，每个状态处理5层递归），由于n=5，实际复杂度为O(32 × 5 × q) = O(q)，完全满足题目要求。
• 空间复杂度：状态数组state_values大小为27^5 ≈ 1.5×10^6，占用常数级空间，可忽略不计。

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

// 定义最大状态数：每个位置有27种可能（a-z对应0-25，*对应26），5个位置的总状态数为27^5
const int MAX_STATES = 27 * 27 * 27 * 27 * 27;
// state_values数组记录每个状态对应的最小val值，初始化为0表示未赋值
int state_values[MAX_STATES] = {0};

// 将字符串转换为27进制状态码（a-z→0-25，*→26）
int stringToState(const string &s) {
    int state = 0;
    for (char c : s) {
        state = state * 27 + ((c == '*') ? 26 : (c - 'a')); // 按27进制累加字符值
    }
    return state;
}

// dfs生成所有可能的替换*的状态
// s: 当前处理的字符串（含*）
// index: 当前处理位置（避免重复替换同一位置）
// remaining: 还需将多少个非*字符替换为*
// fg: 1表示插入操作（更新state_values），0表示查询操作（查找最小val）
// val: 插入时的目标值（查询时无意义，传0）
// ans: 查询时存储结果的引用（插入时无意义，传val占位）
void dfs(string &s, int index, int remaining, int fg, int val, int &ans) {
    if (remaining == 0) { // 无剩余替换次数，生成状态码
        int state = stringToState(s);
        if (fg == 1) { // 插入操作：更新最小val
            if (state_values[state] == 0 || state_values[state] > val) {
                state_values[state] = val; // 记录当前状态的最小val
            }
        } else { // 查询操作：查找有效状态的最小val
            if (state_values[state] != 0) { // 0表示未赋值，跳过
                ans = min(ans, state_values[state]); // 更新最小结果
            }
        }
        return;
    }
    // 遍历当前位置之后的字符（避免重复替换，保证每个位置只处理一次）
    for (int i = index; i < s.length(); ++i) {
        if (s[i] != '*') { // 仅处理非*字符（*已表示通配符，无需再替换）
            char original = s[i]; // 保存原始字符
            s[i] = '*'; // 替换为*，生成新的匹配模式
            dfs(s, i + 1, remaining - 1, fg, val, ans); // 递归处理下一个位置
            s[i] = original; // 恢复原始字符，回溯
        }
    }
}

void solve() {
    int q;
    cin >> q;
    while (q--) {
        int op;
        string s2;
        cin >> op >> s2;
        // 统一处理为5长度字符串，不足补*（*表示通配符，不参与实际字符匹配）
        while (s2.length() < 5) s2.push_back('*');
        
        if (op == 1) { // 插入操作：记录某模式的最小val
            int val;
            cin >> val;
            // 枚举替换0~5个字符为*（生成所有可能的通配模式）
            for (int i = 0; i <= 5; i++) {  
                dfs(s2, 0, i, 1, val, val); // 第三个参数val为占位符，无实际作用
            }
        } else { // 查询操作：查找匹配模式的最小val（优先匹配度高的模式）
            int ans = 1e9 + 1; // 初始化结果为无穷大
            // 按替换次数从小到大枚举（替换0次即原字符串，匹配度最高）
            for (int i = 0; i <= 5; i++) {
                dfs(s2, 0, i, 0, 0, ans); // 查找所有替换i次生成的状态
                if (ans != 1e9 + 1) { // 找到有效结果（非初始无穷大）
                    cout << ans << endl; // 输出结果
                    break; // 优先匹配替换次数少的模式（长匹配优先）
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0); 
    
    int tcase = 1;
    while (tcase--) solve(); 
    
    return 0;
}