解题思路

这是一道字符串模拟题。关键在于高效地处理区间重复操作：

  1. 每次操作会将指定区间内的每个字符重复一次
  2. 由于字符串会不断变长，我们需要：
    • 正确计算新的插入位置
    • 高效处理字符串插入操作
  3. 使用StringBuilder/string/vector来实现高效的字符串操作

代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n, q;
    string s;
    cin >> n >> q >> s;
    
    while(q--) {
        int l, r;
        cin >> l >> r;
        l--; r--; // 转换为0-based索引
        
        // 计算插入位置的偏移量
        int offset = 0;
        string temp = s;
        for(int i = l; i <= r; i++) {
            // 在当前位置后插入相同字符
            s.insert(i + 1 + offset, 1, temp[i]);
            offset++;
        }
    }
    
    cout << s << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        StringBuilder sb = new StringBuilder(sc.next());
        
        while(q-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int len = r - l + 1;  // 区间长度
            
            // 计算实际的起始和结束位置
            int start = l - 1;  // 转换为0-based索引
            int end = r - 1;
            
            // 保存当前区间的字符
            String temp = sb.substring(start, end + 1);
            
            // 从左到右插入字符
            for(int i = 0; i < len; i++) {
                sb.insert(start + 2 * i + 1, temp.charAt(i));
            }
        }
        
        System.out.println(sb.toString());
    }
}

n, q = map(int, input().split())
s = list(input())  # 转换为列表以便高效操作

for _ in range(q):
    l, r = map(int, input().split())
    l -= 1  # 转换为0-based索引
    r -= 1
    
    # 计算插入位置的偏移量
    offset = 0
    temp = s.copy()  # 保存当前状态
    for i in range(l, r + 1):
        # 在当前位置后插入相同字符
        s.insert(i + 1 + offset, temp[i])
        offset += 1

print(''.join(s))

算法及复杂度

  • 算法：字符串模拟。对每次操作，计算正确的插入位置并进行字符插入。
  • 时间复杂度： ，其中q是操作次数，n是字符串长度。每次操作可能需要处理长度为n的区间，且字符串插入操作的复杂度为O(n)。
  • 空间复杂度： ，需要存储字符串。