解题思路

直接模拟每次操作的过程：

1. 每次操作先将 1-based 的区间 [l, r] 转换为 0-based 索引
2. 计算区间长度，从区间末尾向前遍历（避免插入操作影响后续字符的位置）

假设区间是 [2,4]（0-based 是 [1,3]），字符是 b、c、d

如果从左到右插入：插入 b 后字符串变长，c 和 d 的位置会后移，导致后续索引计算错误

从右到左插入：先处理 d，再处理 c，最后处理 b，插入操作不会影响未处理字符的位置，保证索引准确

3.对每个字符，在其原位置后插入一个相同字符

4.重复 q 次操作后输出最终字符串

上代码

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

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

    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    while (q--) 
    {
        int l, r;
        cin >> l >> r;
        int ks = l - 1;  // 转换为0-based起始索引
        int end = r - 1; // 转换为0-based结束索引
        int len = end - ks + 1;  // 区间长度
        // 从区间末尾向前遍历，避免插入影响后续位置
        for (int i = len - 1; i >= 0; i--)
        {
            int pos = ks + i;  // 当前处理的字符位置
            char c = s[pos];   // 获取当前字符
            // 在pos+1位置插入一个字符c
            s.insert(pos + 1, 1, c);
        }
    }
    cout << s << endl;
    return 0;
}

复杂度分析

时间复杂度

• 每次操作：区间长度为 k，插入 k 个字符，每个插入操作的时间复杂度是 O (m)（m 是当前字符串长度）
• 总时间复杂度：O (q * k * m)
• 由于 q≤10，初始 n≤1000，每次操作后字符串长度最多翻倍（q=10 时最大长度是 1000*2^10=1e6）不会超时

空间复杂度

• O (m)：存储最终字符串，最大不超过 1e6