P4588 [TJOI2018] 数学计算

· · 题解

P4588 [TJOI2018] 数学计算

思路：

这次题目很简单，应该都看得懂 QwQ
这道题因为数据很大，要取模，但在操作中要进行除法运算，对一个已经取了模的数进行除法运算会使它不正确，还有可能变为小数。因此不能用普通思路。
但我们发现它每一次除的都是之前乘过的树，换句话说就可以将之前乘的树变为一即可，这时我们就可以构造一线段树，维护每一次操作，做区间乘。若此次操作为乘，就将这次操作对应的节点变为这个数；若此次操作为除，就将第pos次的树变为一即可，输出就输出根节点。

完整代码：

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define int long long
using namespace std;
const int N=1e5+5;
int tr[N*4],M;
void update(int p,int l,int r,int num,int q){
    if(l==r){
        tr[p]=q;
        return;
    }
    int mid=(l+r)>>1;
    if(num<=mid)update(lc,l,mid,num,q);
    if(num>mid)update(rc,mid+1,r,num,q);
    tr[p]=(tr[lc]*tr[rc])%M;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        int q;
        cin>>q>>M;
        for(int i=1;i<=4*q;i++)tr[i]=1;
        for(int i=1;i<=q;i++){
            int op;
            cin>>op;
            if(op==1){
                int m;
                cin>>m;
                update(1,1,q,i,m%M);
                cout<<tr[1]<<endl;
            }
            if(op==2){
                int pos;
                cin>>pos;
                update(1,1,q,pos,1);
                cout<<tr[1]<<endl;
            }
        }
    }

}

线段树讲解