题解 P4588 【[TJOI2018]数学计算】

说实话第一眼没看出来这是个线段树题 仔细一想就算是你把每次操作计算出来，每次除去找数，然后除掉，那样就只能最 后取mod，或求很多逆元，不取模你会炸$longlong$。 如何解决？ 我们以时间为轴，建立线段树，叶子结点维护该操作时间的乘数，非叶子结点维护 区间乘，叶子结点一开始都为$1$ 然后每次乘，进行单点修改，将该次操作时间的位置修改为该乘数，最后输出$tr[1]$. 每次除的话，就将询问的操作位置的乘数改为$1$。最后输出$tr[1]$ 然后这题就做完了 ```cpp #include<iostream> #include<cstdio> #define LL long long #define lson k<<1,l,mid #define rson k<<1|1,mid+1,r #define ls k<<1 #define rs k<<1|1 #define mid ((l+r)>>1) using namespace std; const int maxn=100005; LL tr[maxn<<2]; int mod,t,q; inline void update(int k){ tr[k]=(tr[ls]*tr[rs])%mod; } void build(int k,int l,int r){ tr[k]=1; if(l==r) return ; build(lson);build(rson); } void change(int k,int l,int r,int x,int val){ if(l==r){ tr[k]=(val==0)?1:val; return ; } if(x<=mid)change(lson,x,val); else change(rson,x,val); update(k); } int main(){ scanf("%d",&t); while(t--){ scanf("%d%d",&q,&mod); build(1,1,q); int opt,x; for(int i=1;i<=q;++i){ scanf("%d%d",&opt,&x); if(opt==1)change(1,1,q,i,x),printf("%lld\n",tr[1]%mod); else change(1,1,q,x,0),printf("%lld\n",tr[1]%mod); } } return 0; } ```