BZOJ5334：[TJOI2018]数学计算—

BZOJ5334：[TJOI2018]数学计算——题解

阅读量：7231 次

发布时间：2019-06-29

本文共 1341 字，大约阅读时间需要 4 分钟。

小豆现在有一个数x，初始值为1. 小豆有Q次操作，操作有两种类型:

1 m: x = x * m ，输出 x%mod;

2 pos: x = x / 第pos次操作所乘的数（保证第pos次操作一定为类型1，对于每一个类型1 的操作至多会被除一次），输出x%mod

都懒得写题解了……就对着时间建一个线段树，区间维护乘积即可。

真·大水题。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int Q=1e5+5;inline ll read(){ ll X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}int q;ll p,tr[Q*4];inline void upt(int a){tr[a]=tr[a<<1]*tr[a<<1|1]%p;}void build(int a,int l,int r){ if(l==r){ tr[a]=1;return; } int mid=(l+r)>>1; build(a<<1,l,mid);build(a<<1|1,mid+1,r); upt(a);}void mdy(int a,int l,int r,int x,ll y){ if(l==r){ tr[a]=y; return; } int mid=(l+r)>>1; if(x<=mid)mdy(a<<1,l,mid,x,y); else mdy(a<<1|1,mid+1,r,x,y); upt(a);}int main(){ int T=read(); while(T--){ q=read(),p=read(); build(1,1,q); for(int i=1;i<=q;i++){ int op=read(); if(op==1){ ll m=read(); mdy(1,1,q,i,m); }else{ int pos=read(); mdy(1,1,q,pos,1); } printf("%lld\n",tr[1]); } } return 0;}