小豆现在有一个数x，初始值为1. 小豆有Q次操作，操作有两种类型:
1 m: x = x * m ，输出 x%mod;
2 pos: x = x / 第pos次操作所乘的数（保证第pos次操作一定为类型1，对于每一个类型1 的操作至多会被除一次），输出x%mod
题目链接：
http://www.lydsy.com/JudgeOnline/problem.php?id=5334
都2018年了，居然还有省选出模板题的吗？
对询问建一颗线段树，直接维护。。。
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
const int N=1e5+50;
LL mod;
int n;
struct node{
int l,r;
LL sum;
}d[N<<2];
void build(int l,int r,int t){
d[t].l=l;d[t].r=r;d[t].sum=1;
if(l==r)return;
int mid=l+r>>1;
build(l,mid,t<<1);
build(mid+1,r,t<<1|1);
}
void update(int l,int t,LL val){
if(d[t].l==d[t].r){
d[t].sum=val%mod;
return;
}
if(l<=d[t<<1].r) update(l,t<<1,val);
else update(l,t<<1|1,val);
d[t].sum=d[t<<1].sum*d[t<<1|1].sum%mod;
}
int main(){
int T;scanf("%d",&T);
LL x;
int pos,op;
while(T--){
scanf("%d%lld",&n,&mod);
build(1,n,1);
for(int i=1;i<=n;++i){
scanf("%d",&op);
if(op==1){
scanf("%lld",&x);
update(i,1,x);
}
else{
scanf("%d",&pos);
update(pos,1,1);
}
printf("%lld\n",d[1].sum);
}
}
return 0;
}
This passage is made by Iscream-2001.
BZOJ 5334--[Tjoi2018]数学计算（线段树）
原文：https://www.cnblogs.com/Yuigahama/p/9652694.html