LR-remainder题解

这道题目非常简单，因为每当我们看到求区间问题的时候，我们就可以想起
@复仇者_仲达 在 他的帖子中写的一句话：

“我12岁就可以手搓线段树”

正如作者今年才11岁，所以这道题目可以通过写线段树来解决
先复习一下线段树：
接着，我们读题。我们发现我们一直会处理一个连续区间（本题本应用双指针做，但作者没想出来），所以我们会预处理一个线段树:

void build(int l , int r , int x){
    if(l == r){
        tree[x] = a[l] % m ;
        return ;
    }
    build(l , (l + r) >> 1 , x << 1) ;
    build(((l + r) >> 1) + 1 , r , (x << 1) + 1) ;
    tree[x] = (tree[x * 2] * tree[x * 2 + 1]) % m ;
}

接着，我们手搓线段树的查询部分：

int find(int l , int r , int x , int y , int u){
    if(l <= x && r >= y)return tree[u] % m ;
    if(y < l || x > r)return 1 ;
    return find(l , r , x , (x + y) >> 1 , u * 2) * find(l , r , ((y + x) >> 1) + 1 , y , u * 2 + 1) % m ;
}

在搓这道题的时候突然忘记查找怎么写了，于是随便写里一个find，见谅
主函数就直接模拟就可以了：
这是本体完整代码：

#include<bits/stdc++.h>
using namespace std ;
#define int long long
int t , n , m , a[1000010] , tree[1000010] ;
void build(int l , int r , int x){
    if(l == r){
        tree[x] = a[l] % m ;
        return ;
    }
    build(l , (l + r) >> 1 , x << 1) ;
    build(((l + r) >> 1) + 1 , r , (x << 1) + 1) ;
    tree[x] = (tree[x * 2] * tree[x * 2 + 1]) % m ;
}
int find(int l , int r , int x , int y , int u){
    if(l <= x && r >= y)return tree[u] % m ;
    if(y < l || x > r)return 1 ;
    return find(l , r , x , (x + y) >> 1 , u * 2) * find(l , r , ((y + x) >> 1) + 1 , y , u * 2 + 1) % m ;
}
signed main(){
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    cout.tie(nullptr) ;
    cin >> t ;
    while(t --){
        cin >> n >> m ;
        for(int i = 1 ; i <= n ; i ++){
            cin >> a[i] ;
        }
        build(1 , n , 1) ;
        string s ;
        cin >> s ;
        int l = 1 , r = n ;
        for(int i = 0 ; i < s.size() ; i ++){
            cout << find(l , r , 1 , n , 1) % m << ' ' ;
            if(s[i] == 'L'){
                l ++ ;
            } else {
                r -- ;
            }
        }
        cout << endl ;
    }
    return 0 ;
}

@复仇者_仲达 你看我11岁就可以手搓线段树，我是不是很棒呀！
@big light star
@.҈̊̔柠.҈̊̔̇̊͐七
@八级大狂风
@182
@布什戈门
@不做python
@编程爱好者