题解 | 转化

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

int main() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    // upL[c]: 从小写开始，最终是否为大写；初始为小写(false)
    // upU[c]: 从大写开始，最终是否为大写；初始为大写(true)
    array<char, 26> upL{}, upU{};
    upL.fill(0);
    upU.fill(1);
    for (int i = 0; i < m; ++i) {
        int op;
        char L, R;
        cin >> op >> L >> R;
        if (op == 1) {
            int l = L - 'a', r = R - 'a';
            for (int c = l; c <= r; ++c) {
                // 只有当前是小写的才会被转成大写
                if (!upL[c]) upL[c] = 1;
                if (!upU[c]) upU[c] = 1; // 起始为大写的路径若曾被降小写，也会被此操作升回大写
            }
        } else { // op == 2
            int l = L - 'A', r = R - 'A';
            for (int c = l; c <= r; ++c) {
                // 只有当前是大写的才会被转成小写
                if (upL[c]) upL[c] = 0;
                if (upU[c]) upU[c] = 0;
            }
        }
    }
    // 将最终状态应用到字符串
    for (char& ch : s) {
        int idx = (ch >= 'a' ? ch - 'a' : ch - 'A');
        bool startUpper = isupper(static_cast<unsigned char>(ch));
        bool finalUpper = startUpper ? upU[idx] : upL[idx];
        ch = finalUpper ? char('A' + idx) : char('a' + idx);
    }
    cout << s << '\n';
    return 0;
}