游游的字母翻倍【牛客tracker 每日一题】

游游的字母翻倍

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

游游拿到了一个长度为n nn的字符串，她每次操作会选择一个区间[ l , r ] [l,r][l,r]，将第l ll个字母到第r rr个字母各重复一次，插入到该字母的后面。

例如，对于字符串"a b c d abcdabcd“，若选择区间[ 2 , 3 ] [2,3][2,3]进行操作，字符串将变成”a b b c c d abbccdabbccd"

游游将进行q qq次操作。她想知道，q qq次操作结束后，最终的字符串是什么样子？

输入描述：

第一行输入两个正整数n nn和q qq，分别代表字符串长度和操作次数。
第二行输入一个仅由小写英文字母组成的字符串，代表初始的字符串。
接下来的q qq行，每行输入两个正整数l , r l,rl,r，代表操作的区间。
1 ≤ n ≤ 1000 1≤n≤10001≤n≤1000
1 ≤ q ≤ 10 1≤q≤101≤q≤10
1 ≤ l ≤ r ≤ 1 0 6 1≤l≤r≤10^61≤l≤r≤106
保证每次操作时，r rr不大于当前的字符串长度。

输出描述：

一个字符串，代表所有操作结束后形成的字符串。

示例1

输入：

6 2 abcdef 2 4 3 6

输出：

abbbccccdddef

说明：

第一次操作后，字符串变成a b b c c d d e f abbccddefabbccddef
第二次操作后，字符串变成a b b b c c c c d d d e f abbbccccdddefabbbccccdddef

解题思路

首先读取初始字符串的长度n nn、操作次数q qq及初始字符串，对于每次操作的区间[ l , r ] [l,r][l,r]，先转换为0 − b a s e d 0-based0−based的起始位置k s = l − 1 ks=l-1ks=l−1和结束位置e n d = r − 1 end=r-1end=r−1，计算区间长度l e n lenlen，随后从区间末尾向前遍历每个位置（逆序遍历可避免正向插入时字符位置偏移导致的遍历错误），在每个位置p o s pospos的下一个位置插入与p o s pospos处相同的字符；由于n ≤ 1000 n≤1000n≤1000、q ≤ 10 q≤10q≤10，即使多次插入操作使字符串长度增长，该直接模拟的方式时间复杂度仍在可控范围内，能精准还原每次区间字符翻倍的操作效果，最终输出所有操作完成后的字符串，高效且准确地解决问题。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;intmain(){ll n,q;cin>>n>>q;string s;cin>>s;while(q--){ll l,r;cin>>l>>r;ll ks=l-1,end=r-1;ll len=end-ks+1;for(ll i=len-1;i>=0;i--){ll pos=ks+i;charc=s[pos];s.insert(pos+1,1,c);}}cout<<s<<endl;return0;}