题解 | 游游的字母翻倍

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  string s;
  size_t size;
  int q;
  cin >> size >> q;
  cin >> s;
  vector<int> a(size, 1);//-------给每个字母一个位置，上面的字母个数初始为1
  int len, l, r;
  while(q--){
    cin >> l >> r;
    len = r - l + 1;//--------一共可以复制几份
    l--;
    int ls = 0;
    while(l > 0){//--------转化索引
      l -= a[ls];
      ls++;
    }
    if (ls > 0){//---------纠正，主要正对前面减多了（l<0）(没有刚刚好踩在两个字母之间)
      a[ls - 1] -= l;
      len += l;
    }
    while(len > 0){//----------------翻倍
      if (a[ls] <= len){
        len -= a[ls];
        a[ls] *= 2;
      }
      else{
        a[ls] += len;
        len = 0;
      }
      ls++;
    }
  }
  for (int i = 0; i < size; i++){
    while(a[i]--){
      cout << s[i];
    }
  }
}