洛谷P4588

抄题解好手？mark一下

#include<bits/stdc++.h>
#define int long long
using namespace std;
int d[4000009];
int n,M,T,mod,p;
signed main(){
    for(scanf("%lld",&T);T;--T){
        scanf("%lld%lld",&n,&mod);
        for(M=1;M<=n;M<<=1);
        fill(d+1,d+M+n+2,1);//注意！！！一定要多fill一个，否则QAQ行可能有问题。
        for(int i=1,a=0,b=0;i<=n;++i){
            scanf("%lld%lld",&a,&b);
            a==1?d[p=i+M]=b%mod:d[p=b+M]=1;
            while(p>>=1)d[p]=d[p<<1]*d[p<<1|1]%mod;//QAQ
            printf("%lld\n",d[1]);
        }
    }
    return 0;
}