E 奏绝

显然在计算m次答案时无法进行遍历，所以要预处理一些东西。

用cnt0[i]和cnt1[i]表示从1到i中0的个数和1的个数，s0[i]和s1[i]表示从1到i中0的下标总和与1的下标总和，ans[i]表示1到i总影响值

更新上述列表是简单的，遍历一边序列即可全部更新完成。

最后是计算答案，对于每一个l, r，答案首先为ans[r] - ans[l - 1]，不过l前面的数仍然对剩余的答案有影响，所以要减去l前面的0与l至r中的1的下标的组合，以及l前面的1与l~r中的0的下标的组合。

import sys, random
input = lambda: sys.stdin.readline().rstrip("\r\n")
mii = lambda: map(int, input().split())
mod = 998244353

n, m = mii()
c = input()

cnt0, cnt1 = [0] * (n + 1), [0] * (n + 1)
ans = [0] * (n + 1)
s0, s1 = [0] * (n + 1), [0] * (n + 1)

for i in range(1, n + 1):
    cnt0[i], cnt1[i] = cnt0[i - 1], cnt1[i - 1]
    s0[i], s1[i] = s0[i - 1], s1[i - 1]
    if c[i - 1] == '0':
        cnt0[i] += 1
        s0[i] += i
        ans[i] = (ans[i - 1] + cnt1[i - 1] * i - s1[i - 1]) % mod
    else: 
        cnt1[i] += 1
        s1[i] += i
        ans[i] = (ans[i - 1] + cnt0[i - 1] * i - s0[i - 1]) % mod
    
for _ in range(m):
    l, r = mii()
    tmp1 = (s1[r] - s1[l - 1]) * cnt0[l - 1] - s0[l - 1] * (cnt1[r] - cnt1[l - 1])
    tmp0 = (s0[r] - s0[l - 1]) * cnt1[l - 1] - s1[l - 1] * (cnt0[r] - cnt0[l - 1])
    print((ans[r] - ans[l - 1] - tmp1 - tmp0 + mod) % mod)