【题目】

传送门

题目描述：

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

$1$ $m$：$x=x\times m$ 输出 $x\%mod$；

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

输入格式：

一共有 $t$ 组输入$(t\le 5)$；

对于每一组输入,第一 行是两个数字 $Q,mod(Q\le 100000,mod\le 100000000)$，

接下来 $Q$ 行，每一行为操作类型 $op$，操作编号或所乘的数字 $m$（保证所有的输入都是合法的）。

输出格式：

对于每一个操作，输出一行，包含操作执行后的 $x\%mod$ 的值

样例数据：

输入 1 10 1000000000 1 2 2 1 1 2 1 10 2 3 2 4 1 6 1 7 1 12 2 7

输出 2 1 2 20 10 1 6 42 504 84

说明：

对于 $20\%$ 的数据，$1\le Q\le 500$ 对于 $100\%$ 的数据，$1\le Q\le 100000$

【分析】

其实这道题一开始想用模拟，但是由于模数不一定和被除数互质，所以不能快速求逆元，也就不能模拟了

这道题的正解是线段树，记录一下区间的乘积，那么每次 $1$ 操作就在 $i$ 位置乘 $m$，$2$ 操作就把 $pos$ 位置的数变为 $1$

由于是单点修改，连懒标记都不用写

最后询问输出根节点的乘积就可以了

【代码】

#include<bits/stdc++.h> #define N 100005 using namespace std; int n,P,prod[N<<2]; #define mid ((l+r)>>1) void build(int root,int l,int r){ prod[root]=1; if(l==r) return; build(root<<1,l,mid); build(root<<1|1,mid+1,r); } void Modify(int root,int l,int r,int x,int val){ if(l==r) {prod[root]=val;return;} if(x<=mid) Modify(root<<1,l,mid,x,val); else Modify(root<<1|1,mid+1,r,x,val); prod[root]=1ll*prod[root<<1]*prod[root<<1|1]%P; } #undef mid int main(){ int T; scanf("%d",&T); while(T--){ int op,x; scanf("%d%d",&n,&P),build(1,1,n); for(int i=1;i<=n;++i){ scanf("%d%d",&op,&x); if(op==1) Modify(1,1,n,i,x),printf("%d\n",prod[1]); else Modify(1,1,n,x,1),printf("%d\n",prod[1]); } } return 0; }