游游的字母翻倍

更新

被降维打击了。原来模拟能做。。。orz

可以将字符串按照区间位置进行切片，将[l, r]的切片中的每个字符都复制一遍就好了，完全不需要差分来做，想想也是这道题用差分也只用了一次，完全没有必要，还是我太菜了。

n, m = map(int, input().split())
s = input()
for _ in range(m):
    l, r = map(int, input().split())
    a, b, c = s[:l-1], s[l-1:r], s[r:]
    new = ""
    for each in b: # 将[l, r]中的每个字符都复制一遍
        new += each * 2
    s = a + new + c
print(s)

原思路

这道题一开始想用模拟来做，发现太麻烦了，所以换一种思路，仔细看了看题目，在区间[l, r]中使每个字母都重复一遍，这不是区间加吗？

我们完全可以将字符串中的字母个数都初始化为1，然后转化为差分数组进行区间加法操作，操作q次即可。

在操作过程中，我们需要更新每个区间中字符出现的次数，统计完后，按照每个字符出现的次数进行拼接，得到新的字符串，对新的字符串再求长度，并再次初始化差分数组。

由于操作数仅为10，区间长度最大为10^6级别，因此时间复杂度最差为10^7，完全能过。

N = 10 ** 6 + 10
n, m = map(int, input().split())
s = ' ' + input()
b = [1] * N
b[0] = 0
d = [0] * N
for i in range(1, N):
    d[i] = b[i] - b[i-1]

for _ in range(m):
    l, r = map(int, input().split())
    d[l] += 1
    d[r+1] -= 1
    for i in range(1, n+1):
        d[i] = d[i] + d[i-1]
        b[i] = d[i]
    t = ' '
    for i in range(1, n+1):
        t += s[i] * b[i]
    s = t
    n = len(t) - 1
    
    b = [1] * N
    b[0] = 0
    d = [0] * N
    for i in range(1, n+1):
        d[i] = b[i] - b[i-1]
    
print(t[1::])