[C++知识库]牛客寒假1 B炸鸡块君与FIFA22 ST表，log查询

int f[3][N][21];

int qsm(int l,int r,int st){
    int t = (st%3 + 3) % 3;
    int ans = st;   
    for (int k = lg(r - l + 1); k >= 0;k--){
        if(l + (1<<k) - 1 <=r){
           ans += f[t][l][k];
           t = (ans%3 +3) % 3;
           l = l + (1 << k);
        }
    }
    return ans;
}

char s[N];
void sov()   
{
    int n, q;
    cin >> n >> q;
    cin >> (s + 1);
    for (int i = 1; i <= n;i++){
        if(s[i]=='W'){
            for (int j = 0; j <= 2;j++)
                f[j][i][0] = 1;
        }
        if(s[i]=='L'){
            f[1][i][0] = f[2][i][0] = -1;
        }
    }

    for (int i = 1; i <= 20;i++){
        for (int j = 1; j + (1 << i) - 1 <= n;j++){
            for (int k = 0; k <= 2;k++){
                int t = f[k][j][i - 1];// s
                f[k][j][i] = t + f[((t+k)%3+3) % 3][j + (1 << (i-1))][i - 1];
            }
        }
    }
    for (int i = 1; i <= q;i++){
        int a, b,st;
        cin >> a >> b>>st;
        cout << qsm(a,b,st)  << endl;
    }
}