题意:
如题。
思路:
这是一道关于 倍增(倍增算法讲解) 的一道典型例题,同时还涉及到了 数论中 对于 模 的概念,是一道好题。
我们注意到 起始分数若在 % 3
意义下相等(即这些起始分值 模 3
结果一致),则 经历 [l, r]
一段后分数的变化量是一个定值(重要)
关于查询ask
:
-
假设我们 已经预处理出了
st
, -
则对于 每一次询问
ask
,可以 先将某初始分数start
对3
取模,然后按照 倍增的套路 从l
跳 若干个2
的次幂 跳到r
, -
(解释:由于 任意正整数 都能由 若干个
2
的次幂 表达,显然 一个长度为正整数的区间 也可以由 若干长度为2
的若干次幂 的 区间 组合而成,代码中有体现) -
注意:跳的时候 要按照 分数对
3
取模的结果 来决定访问 哪个st
值。(具体见代码)
关于 st
表的预处理 init
:(关于 预处理 可以参考:倍增算法讲解 + 例题,两者类似)
st[i][j][k]
状态表示:
- 定义
st[3][200010][21]
之中,st[k][i][j]
表示 在初始分数为k
的情况下 经历了[i, i + 2 ^ j - 1]
一段游戏后 分数的 变化量;
st[i][j][k]
状态计算:
-
首先,按照字符串内容初始化
j = 0
的情况; -
之后,
st[k][i][0]
由st[k][i][j - 1]
和st[k][mid][j - 1]
计算得到,之中mid = i + 2 ^ (j - 1)
状态转移方程:
-
st[k][i][j] = st[k][i][j - 1] + st[(k + st[k][i][j - 1]) % 3][mid][j - 1]
(k = 0、1、2
) -
其中
(k + st[k][i][j - 1]) % 3
表示:如果在i
处初始分数为k
,那么到了mid
处时分数对3
取模得多少
时间复杂度:
$O(nlogn + q)$
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10, M = 21;
int n;
int q;
char s[N];
int st[3][N][M];
void init()
{
for(int j=0; j<M; ++j)
{
for(int i=1; i+(1<<j)-1<=n; ++i)
{
if(!j)//根据字符串的内容,我们要对 st 数组进行初始化,根据定义以及题意出发即可
{
if(s[i]=='W')//赢 情况
{
st[0][i][j] = st[1][i][j] = st[2][i][j] = 1;
}
else if(s[i]=='L')//输 情况 按照题意要根据分数模 3 的结果进行赋值
{
st[0][i][j] = 0;
st[1][i][j] = -1;
st[2][i][j] = -1;
}
else//平局 情况
{
st[0][i][j] = st[1][i][j] = st[2][i][j] = 0;
}
}
else
{
int mid = i+(1<<(j-1));//设置 mid 为区间 [i, j] 的中点,这是倍增算法的套路
for(int k=0; k<3; ++k)//依据推出来的状态转移方程
{
st[k][i][j] = st[k][i][j-1] + st[((k+st[k][i][j-1])%3+3)%3][mid][j-1];
}
}
}
}
}
int ask(int l, int r, int start)
{
int len = r - l + 1;
//将长度为 len 的区间划分为若干 长度为 2 的若干次幂 的区间
while(len)
{
int k = log(len) / log(2);
start += st[start%3][l][k];//跳的时候 根据题意一定要根据 模数 来跳
len -= (1<<k), l += (1<<k);
}
return start;
}
int main()
{
cin>>n>>q;
cin>>s+1;
init();
while(q--)
{
int l, r, start;
scanf("%d%d%d", &l, &r, &start);
printf("%d\n", ask(l, r, start));
}
return 0;
}