P4588 [TJOI2018]数学计算

线段树板子题。

#include<iostream>
#include<cstring>
using namespace std;
#define int long long
const int N=8e5+1;
int mod;
int q,m;
namespace st{
    int tree[N];
    void init(){fill(tree+1,tree+N,1);}
    void update(int k,int l,int r,int x,int y)
    {
        if(l==r){
            tree[k]=y;
            //cout<<tree[k]<<endl;
            return;
        }
        int mid=l+r>>1;
        if(x<=mid)update(k<<1,l,mid,x,y);
        else update(k<<1|1,mid+1,r,x,y);
        tree[k]=tree[k<<1]*tree[k<<1|1]%mod;
        //cout<<tree[k]<<endl;
    }
    int query(){return tree[1];}
}
void Main(){
    st::init();
    cin>>q>>mod;
    for(int i=1; i<=q; i++){
        static int x,y;
        cin>>x>>y;
        if(x==1)st::update(1,1,q,i,y);
        else st::update(1,1,q,y,1);
        cout<<st::query()<<endl;
    }
}
signed main(){
    int T;
    cin>>T;
    while(T--)Main();
}

原文地址：http://www.cnblogs.com/dadidididi/p/16804461.html