解题思路

• 操作并不是对字符串中的“区间位置”生效，而是对字母表中的一个字母区间生效（如 [a,c]），把所有出现的这些字母统一大小写转换。

• 因此，我们不需要一遍遍扫描字符串；只要记录每个字母最近一次被“转成大写”的操作时间与最近一次被“转成小写”的操作时间即可。

• 设：

  • last_up[c]：字母 c（0~25）最近一次被“转大写”的操作编号（没有则为 0）
  • last_low[c]：字母 c最近一次被“转小写”的操作编号（没有则为 0）

• 读入每个操作 [letter1, letter2]（保证 letter1 <= letter2），把这个闭区间内对应字母的 last_up 或 last_low 更新为该操作的编号 i。

  • 注意：op=1 输入给的是小写范围，op=2 输入给的是大写范围，但我们统一把端点转成小写来算索引即可。

• 全部操作读完后，逐个遍历原串字符 ch：

  • 令 idx = tolower(ch) - 'a'

  • 比较 last_up[idx] 与 last_low[idx]：

    • 若二者都为 0：该字母不受影响，保持原样
    • 否则谁时间戳更大就说明最后一次操作决定它是大写或小写

• 复杂度：每个操作最多更新 26 个字母，所以总计 O(m * 26 + n)，对于约束 m,n ≤ 2e5 十分安全。

代码实现

import sys

def main():
    # 读取输入并分割为列表，使用迭代器方便依次取值
    data = sys.stdin.read().strip().split()
    it = iter(data)

    # 读取 n（字符串长度）和 m（操作次数）
    n = int(next(it))
    m = int(next(it))

    # 原始字符串转成 list，方便后面修改
    s = list(next(it))

    # last_up[i]：字母 i（0~25）最后一次被转成大写的操作编号
    # last_low[i]：字母 i（0~25）最后一次被转成小写的操作编号
    last_up = [0] * 26
    last_low = [0] * 26

    # 处理 m 次操作
    for i in range(1, m + 1):
        op = int(next(it))  # 操作类型
        l1 = next(it)       # 左端字母
        l2 = next(it)       # 右端字母

        # 统一转成小写来计算字母在 0~25 的索引
        a = ord(l1.lower()) - ord('a')
        b = ord(l2.lower()) - ord('a')

        # 保证 a <= b
        if a > b:
            a, b = b, a

        if op == 1:
            # 将区间 [a, b] 的字母记录“最后一次转大写”的时间戳为当前操作编号 i
            for x in range(a, b + 1):
                last_up[x] = i
        else:
            # 将区间 [a, b] 的字母记录“最后一次转小写”的时间戳为当前操作编号 i
            for x in range(a, b + 1):
                last_low[x] = i

    res = []
    # 遍历原始字符串的每个字符
    for ch in s:
        idx = ord(ch.lower()) - ord('a')  # 找到字符对应的字母索引
        if 0 <= idx < 26:
            u = last_up[idx]   # 最后一次转大写的操作编号
            d = last_low[idx]  # 最后一次转小写的操作编号

            if u == 0 and d == 0:
                # 该字母从未被修改过，保持原样
                res.append(ch)
            elif u > d:
                # 最近一次修改是转大写
                res.append(ch.upper())
            else:
                # 最近一次修改是转小写
                res.append(ch.lower())
        else:
            # 非字母字符，直接保留
            res.append(ch)

    # 输出最终结果
    print(''.join(res))

if __name__ == "__main__":
    main()

题目内容

小美有一个长度为$n$，仅由大小写英文字母组成的字符串$s$。小美将对字符串执行以下$m$次操作:

• 当操作类型$op=1$且给定两个小写字母$letter1,letter2$(满足$letter1≦letter2$)时，将字符串中所有位于字母表中$[letter1,letter2]$的小写字母转换为对应的大写字母;

• 当操作类型$op=2$且给定两个大写字母$letter1,letter2$(满足$letter1≦letter2$)时，将字符串中所有位于字母表中$[letter1,letter2]$的大写字母转换为对应的小写字母。

输入描述

在一行上输入两个整数$n,m (1 ≦n,m ≦ 2×105)$，分别表示字符串长度和操作次数;

在一行上输入一个长度为$n$，仅由大小写英文字母组成的字符串s;

接下来$m$行，每行输入三个元素:整数$op$和两个字符$letter1,letter2$，满足:

• 若$op = 1$,则$letter1,letter2$为小写字母，且$letter1≦letter2$;
• 若$op = 2$，则$letter1,letter2$为大写字母，且$letter1≦letter2$。

输出描述

输出执行完所有操作后得到的最终字符串。

样例1

输入

3 1
abc
1 a c

输出

ABC

说明

在此样例中，初始字符串"$abc$"，将区间$[a,c]$的小写字母统一转换成大写，得到"$ABC$"。

样例2

输入

6 2
aAbBcC
1 a b
2 B C

输出

AAbbcc

说明

在此样例中，

• 第一次操作将字符串中所有满足字母表区间$[a,b]$所有小写字母的变为大写字母，得到"$AABBcC$";
• 第二次操作将字符串中所有满足字母表区间$[B,C]$所有大写字母的变为小写字母，最终得到"$AAbbcc$"。