目录
显示
题目链接
https://www.luogu.org/problem/P4588
题解
因为有除法+取模操作,直接去计算结果并不可行。
我们考虑按时间建立一棵线段树,一个节点代表时间 \([l,r]\) 所有值的乘积。
对于 \(1\) 操作,将当前时间对应的节点乘上 \(m\) 即可。
对于 \(2\) 操作,将 \(pos\) 时间对应的节点值变为 \(1\)(代表除这个数)。
最后只需要查询根节点的值即可。
#include <iostream> using namespace std; long long s[400005],q,mod; void pushup(int root) { s[root]=s[root<<1]*s[root<<1|1]%mod; } void build(int root,int l,int r) { if(l==r) { s[root]=1; return; } int mid=(l+r)>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); pushup(root); } void update(int root,int cl,int cr,int pos,int x) { if(pos<cl||cr<pos)return; if(cl==cr&&cl==pos) { s[root]=x; return; } int mid=(cl+cr)>>1; update(root<<1,cl,mid,pos,x); update(root<<1|1,mid+1,cr,pos,x); pushup(root); } int main() { int t; cin>>t; while(t--) { cin>>q>>mod; build(1,1,q); for(int i=1;i<=q;i++) { int op,num; cin>>op>>num; if(op==1)update(1,1,q,i,num); else update(1,1,q,num,1); cout<<s[1]<<endl; } } return 0; }