给定只含 B 与 R 的字符串 S,将其无限重复得到无限串 T = SSSS...。题目要求计数1-based 下标闭区间 [L, R] 中字符 'B' 的数量。
核心做法:前缀计数 + 整除分解(数学分块)
n = |S|,cntB = S 中 'B' 的总数。pref[i] (0≤i≤n):pref[i] 表示 S[0..i-1] 中 'B' 的数量(pref[0]=0)。F(x):无限串 T 的前 x 个字符中 'B' 的数量在遥远的神之大陆上,流传着一种神秘的语言,它由两个字符构成——'R’(代表红色魔力)和‘B’(代表蓝色魔力)。据说,这种语言的每一个短句都蕴含着无穷的力量,
一位名叫“闻像者”的古老法师,发现将一个句子无限循环展开后,会在某些特定区间产生强大的能量波动。他记录下了这些波动,并希望后人能够通过智慧推算出任意一段区间中“蓝色魔力”即字符 'B'的数量。
你作为新一代的闻律学徒,要要解决这个问题: