[洛谷 4588,loj 2543][TJOI2018]数学计算

题目链接

https://www.luogu.org/problem/P4588

https://loj.ac/problem/2573

题解

因为有除法+取模操作，直接去计算结果并不可行。

我们考虑按时间建立一棵线段树，一个节点代表时间 \([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;
}