题解 | #游游的字母翻倍#

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

int main() {
    int n, q, l, r;
    cin >> n >> q;
    string str;
    cin >> str;
    while (q--) {
        cin >> l >> r;

        for (int i = l-1, j = 0; i < r; i++, j++) {
            str.insert(i+j, 1, str[i+j]);//从str[l-1]开始，每次偏移1位为下一次插入
        }
    }
    cout << str;
}
// 64 位输出请用 printf("%lld")
/*
#include <iostream>
#include<string>
using namespace std;

int main() {
    int n,q,l,r;
    cin>>n>>q;
    string str;
    cin>>str;
    while(q--){
        cin>>l>>r;
        string a;
        a+=str[l-1];
        for(int i=l;i<r-1;i++){
            a+=str[i];
            a+=str[i];
        }a+=str[r-1];
        string strl(str,0,l),strr(str,r-1,str.size()-r+1);
        //cout<<"strl="<<strl<<" strr="<<strr<<endl;
        //cout<<"str="<<str<<" a="<<a<<endl;
        str=strl+a+strr;
        //cout<<str<<endl;
    }
    cout<<str;
}
*/

这次是第二版，第一次写的时候直接用string的拼接，但是会用很多内存和字符串拷贝，这次搞insert，可以提前申请空间够，然后insert就不需要移动，每次就o(r-l)好了，总和大概是o(q^(r-l))