炸鸡块君与FIFA22

题意

我们的分数有以下的规则

• 胜利 +1 分
• 平局 不变
• 失败 -1 分，如果我们此时是 3 的倍数那么分数不变

现在我们得到一个字符串，表示其游戏的情况。

现在我们要求每次询问时的游戏状况为 [l,r] 区间的最终得分

思路

对于该题目，我们假设我们在这个区间的初始值分别为 0,1,2 那么也就对应了三种情况，其中 0 的状况对我们来说稍微有点特殊，因为对于这个点而言它的分数并不会降低。因此我们依照这样的情况分别写出对于该点而言，经历一个区间其分数的增减情况。

如果我们想要算出一个区间的增减情况的话，那么我们不免的需要遍历一遍。

但是，由于我们已经求出来每个操作区间长度为 1 的情况的值，那么我们可以根据操作完这个区间长度之后值的情况将两个区间合并。例如我在 1 号位值 %3 = 2 的位置进行了一次 'W' 的操作，同时我们也在 2 号位置进行了一次 'W' 操作，因此对于我们这两个区间合并完之后。我们就可以得到在 1 号开始，做了两次 'W' 操作。

那么想到每次可以进行两两合并的话，那么我们可以轻易发现，我们的操作区间可以成倍增长。因此我们考虑使用倍增的思想来进行操作。

我们定义 f[n][i][j] 表示我在 n 号位置 ，初始状况为 %3 = j 的情况下，往后计算了 $2^{i}2^i$ 长度的区间的增减情况。

那么对于两个区间合并情况遵循如下几个步骤。

1. f[n][i][j] 的第一个部分为 f[n][i - 1][j]。
2. 对于这个区间操作结束后，我们的 %3 操作情况为 (f[n][i - 1][j] + j + 3)% 3， 设该值为 k
3. f[n][i][j] 的第二个部分的值为 f[n + 1 << (i - 1)][i - 1][k]。

进行这样的运算完之后，我们就得到一个成倍增长的操作区间。

那么对于 [l , r , val]。

的情况而言，我们从最大的区间往小区间合并即可。

for (int i = 19 ; i >= 0 ; i --) {
  if(l + (1 << i) > r) continue;
  val += f[l][i][val % 3];
  l += 1 << i;
}
val += f[l][i][val % 3];

code