炸鸡块君与FIFA22(st表)

https://ac.nowcoder.com/acm/contest/23106/B
#include

using namespace std;
typedef long long ll;
const int log1 = 21;
const int N = 2e5 + 1;

int logn[N];
int f[3][N][log1 + 1];
int n, q;

int mod (int x) {
	return (x % 3 + 3) % 3;
}

signed main () {
    cin >>n >> q;
    char s[N  +1];
    cin >> (s + 1);
    for (int j = 0; j <= 20; j++)
    for (int i = 1; i<= n; i ++) {
        int t;
        	if (j == 0) {
        		if (s[i] == 'W')  {
        			f[0][i][j] = f[1][i][j] = f[2][i][j] = 1; 
				}
				else if (s[i] == 'L') {
					f[0][i][j] = 0;
					f[1][i][j] = f[2][i][j] = -1;
				}
				else f[0][i][j] = f[1][i][j] = f[2][i][j] = 0;
			}
			else {
				int p1 = i, p2 = i + (1 << (j - 1)); 
				if (p2 > n) {
					f[0][p1][j] = f[0][p1][j - 1];
					f[1][p1][j] = f[1][p1][j - 1];
					f[2][p1][j] = f[2][p1][j - 1];
				}
				else {
					f[0][p1][j] = f[0][p1][j - 1] + f[mod(f[0][p1][j - 1])][p2][j - 1];
					f[1][p1][j] = f[1][p1][j - 1] + f[mod(1 + f[1][p1][j - 1])][p2][j - 1];
					f[2][p1][j] = f[2][p1][j - 1] + f[mod(2 + f[2][p1][j - 1])][p2][j - 1];
				}
			}
         
    }
   
    while (q --) {
        int l, r, c;
        cin >> l >> r >> c;

        int pos = l;
        int ans = c;
        while (pos <= r) {
        	int j = 0;
        	while (pos + (1 << j) - 1<= r) j ++;
        	j --;
        	ans += f[ans % 3][pos][j];
        	pos += (1 << j);
		}
		cout << ans << endl;
    }
}

[l, l + (1 << (j - 1)) - 1] [l + (1 << (j - 1)), r].需要遍历哪些部分就一个倍增的增加就行了。