[TJOI2018]数学计算

题目：[TJOI2018]数学计算
小数不能取模
树状数组的tr[p]表示包含a[p]（位置p上的元素）的属性和（可能是和、乘..）
树状数组的性质：查前改后

线段树的形：边改边查
区间修改要有懒标记，若每个区间单点修改，它很慢
单点修改可以直接修改 O(lgn),不用懒标记
懒标记就是为区间修改而设计的，表示其子区间的待操作数

线段树就是要考虑维护什么东西
懒标记存什么样的操作数

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
ll tr[N<<2];
int t,m,mod;
void bulid(int p,int l,int r){
    if(l==r){
        tr[p]=1;return ;
    }
    int mid=(l+r) >> 1;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    tr[p]=tr[p*2]*tr[p*2+1];
}
void add(int p,int l,int r,int pos,int w){
    if(l==r){
        if(l==pos) tr[p]=w;
        tr[p]%=mod;
        return ;
    }
    int mid=(l+r) >> 1;
    if(pos<=mid) add(p*2,l,mid,pos,w);
    if(mid+1<=pos) add(p*2+1,mid+1,r,pos,w);
    tr[p]=tr[p*2]*tr[p*2+1]; 
    tr[p]%=mod;
}
ll ask(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y) return tr[p];
    int mid=(l+r) >> 1;
    ll res=1;
    if(x<=mid) res*=ask(p*2,l,mid,x,y);
    if(mid+1<=y) res*=ask(p*2+1,mid+1,r,x,y);
    return res;
}
int main(){
    cin >> t;
    while(t--){
        cin >> m >> mod;
        bulid(1,1,m);
        int op,x;
        for(int i=1;i<=m;++i){
            cin >> op >> x;
            if(op==1){
                add(1,1,m,i,x);
                //cout << ask(1,1,m,1,i)%mod << "\n";
                cout << tr[1] << "\n";
            }
            else {
                add(1,1,m,x,1);
                //cout << ask(1,1,m,1,i)%mod << "\n";
                cout << tr[1] << "\n";
            }
        }  
    }
    return 0;
}